강태규

Introduction to Matroid Union

Matroid Matroid에 대한 기본 지식은 다른 글을 참고하는 것이 좋다. 여기서는 Matroid의 정의만 짚고 넘어가자. 정의 1. 유한집합 $S$와 $S$의 부분집합족 $\mathcal{I}$에 대해 $M=(S, \mathcal{I})$가 아래 조건을 만족할 경우 $M$을 Matroid라고 한다. ${}\in\mathcal{I}$ (Empty set is Independent set) $B\subset A\in\mathcal{I}\Rightarrow B\in\mathcal{I}$ (hereditary property) $A, B\in\mathcal{I}, \mid A\mid>\mid B\mid\Rightarrow\exists x\in A\setminus B$ $s.t.$ $B+x\in\mathcal{I}$ (augmentation property) $S$의 부분집합이 $\mathcal{I}$에 포함될 경우 독립집합(Independent set)이라고 부른다. Matroid Union Matroid Union은 Matroid의 합집합으로, 다음과 같이 정의된다. 정의 2. Matroid...