Matroids
Matroid는 아래의 조건을 만족하는 순서쌍 $M = (S, l)$이다.
- $S$는 공집합이 아닌 유한집합이다.
- $l$은 공집합이 아닌 $S$의 부분집합의 집합 중 다음의 조건을 만족하는 집합이다. $B \in l$ 이고 $A\subseteq B$이면 $A \in l$이다.
- $A, B \in l$이고 $\left\vert A\right\vert < \left\vert B\right\vert $이면 어떤 $x \in B - A$가 존재해서 $A \cup {x} \in l$를 만족한다.
2에서 $l$을 $S$의 independent subsets이라 부르며 2의 조건을 만족하면 $l$이 hereditary가 있다고 한다. $M$이 3의 조건을 만족하면 exchange property를 만족한다고 한다.
Matroid의 다른 예로 그래프 $G = (V, E)$에서 아래와 같이 정의되는 graphic matorid $M_G = (S_G, l_G)$를 생각해볼 수 있다.
- 집합 $S_G$는 $G$의 edge들의 집합 $E$로 정의된다.
- $A$가 $E$의 부분집합이면 $A \in l_G$인 것은 $A$가 사이클이 없는 것과 동치이다. 즉, edges의 집합 $A$가 독립인 것은 subgraph $G_A = (V, A)$가 forest을 이룬다는 것과 동치이다.
Graphic matroid $M_G$은 minimum-spanning-tree 문제와 관련이 있다.
Theorem 1.
$G = (V, E)$이 undirected graph이면 $M_G = (S_G, l_G)$는 matroid이다.
증명
$S_G = E$이므로 유한집합이다. 또한, forest의 부분집합은 forest을 이루기 때문에 $l_G$는 hereditary하다.
$M_G$가 exchange property를 만족하는지만 확인하면 된다. $G_A = (V, A)$, $G_B = (V, B)$가 $G$의 forest이면서 $\left\vert B \right\vert > \left\vert A\right\vert $라 가정하자. 즉, $A$와 $B$는 사이클이 없는 edges의 집합이며, $B$는 $A$보다 더 많은 수의 edges를 갖는다.
$\left\vert V \right\vert $개의 tree에서 edges를 하나씩 추가할 때마다 tree의 개수는 하나씩 감소하기 때문에 $k$개의 edges를 갖는 forest는 정확히 $\left\vert V \right\vert - k$개의 tree를 갖는다. 그러므로 forest $G_A$는 $\left\vert V\right\vert - \left\vert A\right\vert $개의 tree를, forest $G_B$는 $\left\vert V \right\vert - \left\vert B \right\vert$개의 tree를 갖는다.
$G_B$는 $G_A$보다 더 적은 수의 tree를 갖기 때문에, $G_B$는 $G_A$에서는 서로 다른 tree에 속하는 두 vertices $u, v$를 포함하고 있는 tree $T$를 반드시 가진다.
$T$는 서로 연결되어 있기 때문에 edge $(u, v)$가 반드시 존재한다.
$G_A$에서 edge $(u, v)$는 서로 다른 두 tree를 연결하고 있기 때문에 $G_A$에 이 edge를 사이클이 생기지 않게 추가할 수 있다. 따라서, $M_G$는 exchange property를 만족한다. ■
matroid $M=(S, l)$에 대해서 $A\in l$에 대해서 원소 $x \notin A$가 $A$에 독립성을 유지하면서 추가될 수 있으면 extension이라고 한다. 즉, $A \cup {x} \in l$이면 $x$는 $A$의 extension이다.
Graphic matorid $M_G$에서 $A$가 edge의 독립 집합일 때, edge $e$가 $A$의 extension이라는 것은 $A$에 존재하지 않는 edge $e$가 $A$에 사이클을 만들지 않고 추가될 수 있는 것과 동치이다.
$A$가 matorid $M$의 독립 부분집합이고, $A$가 더 이상 extension이 없으면 maximal이라 부른다.
Theorem 2.
Matroid의 모든 maximal independent subsets의 크기는 같다.
증명
모순을 유도하자. $A$를 $M$의 maximal independent subsets이라 하고, $B$를 $A$보다 큰 다른 $M$의 maximal independent subsets이라 하자. Exchange property에 의해 $A$는 어떤 $x \in B- A$가 있어서 더 큰 independent set $A \cup {x}$로 확장가능하다. 이는 $A$가 maximal이라는 가정에 위배된다. ■
Theorem 2.에 따르면 connected, undirected graph $G$의 graphic matroid $M_G$의 maximal independent subsets은 정확히 $\left\vert V \right\vert - 1$개의 edge를 가지면서 $G$의 모든 vertices를 연결하는 tree가 된다. 이를 $G$의 spanning tree라고 부른다.
Matorid $M=(S, l)$이 가중치가 있다는 것은 가중치 함수 $w$가 존재해서 $x \in S$에 양의 가중치 $w(x)$를 정해줄 수 있다는 것이다. 가중치 함수 $w$는 $S$의 부분집합으로 개념을 확장할 수 있다.
\[w(A) = \Sigma_{x\in A}w(x), \forall A \subseteq S\]Graph에서 $w(e)$는 edge $e$의 가중치를 의미하면, Graphic matorid $M_G$에서 $w(A)$는 $A$의 모든 edge 집합의 총 가중치 합을 의미한다.