Matroid Theory 1 - What is Matroid?

옛날부터 배워보고 싶었던 매트로이드를 배워봤습니다.

사실 이걸 배운다고 해서 실전 PS에 쓸 일은 없을 것 같지만

순수한 호기심, 루비를 날먹할 수 있고, 수학/정보적 소양을 기를 수 있지 않을까 하는 생각에 배워봤습니다

저는 잘 모르지만 매트로이드는 현대 조합론에서 꽤나 중요한 역할을 하고 있는 것 같습니다.

허준이 교수의 필즈상을 받게 된 연구 중에서 매트로이드와 관련된 것도 있다고 하고요.

 

기초적인 선형대수학, 그래프 이론과, 최소 스패닝 트리(MST) 알고리즘을 알고 있다는 전제 하에 작성합니다.

코드포스 글 https://codeforces.com/blog/entry/69287

MIT 강의 https://math.mit.edu/~goemans/18438.html
를 참고했습니다.

용어 정리

$A \setminus B$ : 차집합

(수학의 정석 등 교과서에선 $A-B$로 표기하지만, 전문성 있는 글에서는 대부분 이렇게 쓰는거 같아요)

$A \triangle B$ : 대칭 차집합: $(A \setminus B) \cup (B \setminus A)$

$2^S$ : $S$의 멱집합: $S$의 모든 부분집합이 원소인 집합

Matroid의 정의

Matroid는 Matrix에서 파생된 단어로, 벡터공간에서의 일차 독립을 일반화시킨 수학적인 구조입니다.

 

Matroid $M = (S, \mathcal{I}), \ \mathcal{I} \subseteq 2^S$ 는 Ground Set이라 불리는 집합 $S$로부터 정의됩니다.

$S$의 모든 부분집합 $X \subseteq S$은 Independent 하거나, Dependent 한 것으로 나뉘는데, 그중 Independent 한 것의 모임이 $\mathcal{I}$ 입니다. $\mathcal{I}$를 집합 대신, $S$의 어떤 부분집합이 Independent인지, Dependent인지 판별하는 "기준"으로 생각하면 좋습니다. Independent한 부분집합은 Independent Set, Dependent한 부분집합은 Dependent Set으로 부릅시다.

$\mathcal{I}$는 다음 3가지 공리를 만족해야 합니다.

• [I1] $\phi \in \mathcal{I}$.
• [I2] Independent Set의 부분집합은 Independent Set이다.
  $\forall A \subseteq B \subseteq S$ then $B \in \mathcal{I} \Rightarrow A \in \mathcal{I}$
• [I3] 두 Independent Set $A,B \in \mathcal{I}$ 에 대해, $A$가 $B$보다 크다면, $A$에만 있는 어떤 원소 $x$를 뽑아, $B$에 추가하고도, $B$의 Independence를 유지할 수 있다.
  $\forall A,B \subseteq S, |A| > |B|$, then $\exists x \in A \setminus B, B\cup\{x\} \in \mathcal{I}$

여기서 [I1], [I2] 만 만족한다면, Independence System이라고 한다고 합니다. 당연히 Matroid는 Independence System입니다.

[I3]이 매트로이드의 핵심인 공리입니다.

 

$M = (S, \mathcal{I})$ $S= \{x,y,z\}$ $\mathcal{I} = \{ \{ \}, \{x\}, \{y\}, \{z\}, \{x,y\}, \{x,z\} \}$

$M$이 매트로이드임을 확인해보세요.

두 가지 매트로이드, Linear Matroid와 Graphic Matroid

이것만 봐서는 너무 추상적입니다. 좋은 예시를 들어보죠. 벡터공간에서, $S$를 "벡터의 집합", $\mathcal{I}$를 "일차독립인가?" 로 생각해봅시다. 이를 Linear Matroid라고 합니다. [I1], [I2]는 자명하고, 선형대수에서 [I3]을 "기저 정리" 라는 이름으로 배웠을 것입니다. Matroid가 벡터공간에서의 일차 독립을 일반화시켰다는 것이 여기서 나온 것이라는 것을 알 수 있습니다. 

 

또 하나의 예시를 들어봅시다. 연결된 무향 그래프에서 $S$를 "간선의 집합", $\mathcal{I}$를 "사이클이 없는가?" 로 생각해봅시다. 이를 Graphic Matroid라고 합니다. 여기서 Independent Set은 항상 Spanning Forest를 이루게 됩니다. Spanning Tree가 아닌 이유는, 꼭 간선의 집합이 Connected일 필요는 없습니다. 심지어 아무 간선도 포함하지 않은 집합도 Independent입니다. 하지만 Independent Set 중, 가장 큰 것은 Spanning Tree가 되겠죠. 이 내용은 다음 문단에서 다시 다루겠습니다. [I1], [I2]는 여기서도 자명하고, [I3]는 Spanning Forest 관점에서 생각해봤을 때, $|A| > |B|$라면, $A$에는 $B$의 간선들이 지나지 않는 정점을 지나는 간선이 최소 하나 있고, 이를 $B$에 추가할 수 있으므로 Matroid가 성립함을 확인할 수 있습니다.

 

여기서 흥미로운 사실 하나는, Linear Matroid는 사실 Graphic Matroid를 포함하는 매트로이드입니다. 즉 Linear Matroid가 더 넓은 범위라는 거죠. 왜일까요? Graphic Matroid를 Linear Matroid로 바꿀 수 있다면 이를 증명할 수 있습니다. 그래프의 정점 수를 $n$이라고 하고, 각 정점에 1~$n$까지의 번호를 매기고, 벡터 공간 $\mathbb{R}^n$을 생각해봅시다. 그리고 $i$번 정점과 $j$번 정점을 잇는 간선 $\{i,j\}$에 다음과 같은 벡터를 대응해봅시다: [$i$번 원소는 1이고, $j$번 원소는 -1, 그 이외 원소는 0인 벡터]. 일차결합을 볼 것이기 때문에, $i$와 $j$의 순서는 중요하지 않습니다. 이렇게 된다면, 간선에 대응된 벡터의 집합이 일차독립이 아니라는 것은 nonzero인 일차결합을 통해 영벡터를 만들 수 있다는 것이고, 이는 사이클이 있다는 것과 동치입니다. 따라서 Graphic Matroid를 Linear Matroid로 표현했으니, Linear Matroid는 Graphic Matroid를 포함한다고 할 수 있습니다.

 

이렇게 두 가지 매트로이드가 매트로이드의 이해에 가장 중요하다고 생각하기에 먼저 소개했습니다. 매트로이드 이론은 3가지 공리에서 시작되고, 모든 증명이 집합 기호로만 이루어져 있기 때문에 많이 추상적인데, 이 두 매트로이드를 예시를 들어 생각하면 직관적입니다. 게다가 Graphic Matroid는 실제로 그려볼 수 있기 때문에, 더욱 좋은 예시라고 생각합니다. 추후 더 많은 매트로이드를 다뤄보겠습니다.