매트로이드

[목차]

매트로이드 Matroid

개요

선형독립을 조합론적으로 정의한 개념. 보다 자세히 알고 싶은 사람은 다음 링크를 참고하자.

정의

어떤 유한 집합 $E$와 ${\mathcal {I}}\subseteq 2^{E}$($2^{E}$는 $E$의 멱집합을 의미한다.)에 대해 $(E,{\mathcal {I}})$가 매트로이드 임은 다음을 만족함을 의미한다:

1. $\emptyset \in {\mathcal {I}}$
2. (유전성, hereditary) $X\in {\mathcal {I}}$이고 $Y\subseteq X$이면 $Y\in {\mathcal {I}}$
3. (추가성, augmentation property) $X,Y\in {\mathcal {I}}$이고, $|X|<|Y|$이면, 어떤 $e\in Y-X$가 존재해 $X\cup \{e\}\in {\mathcal {I}}$

매트로이드도 그래프와 마찬가지로 가중치를 부여해 생각할 수도 있다. 이 경우, $E$의 각 원소에 실수만큼 가중치를 주고, $E$의 각 부분집합의 가중치는 해당 부분집합의 원소들의 가중치의 합으로 생각해주면 된다. 대개 $e\in E$의 가중치를 $w(e)$로 표기한다.

예시

벡터 매트로이드

체 $\mathbb {F}$ 상의 $m\times n$ 행렬 $A$가 있다고 하자. $[n](=\{1,2,\cdots ,n\})$의 부분집합 $X$에 대해 $A[X]$를 $X$에 속하는 열만을 택해 만든 새로운 ($m\times |X|$ 크기의) 행렬이라 하자. ${\mathcal {I}}=\{X\in 2^{[n]}:A[X]{\text{의 열벡터들이 선형독립}}\}$으로 정의할 경우, $([n],{\mathcal {I}})$는 매트로이드가 된다.

증명은 추가 바람.

그래프 매트로이드

그래프 $G=(V,E)$[* 단순 그래프일 필요는 없다.]가 주어졌을 때, ${\mathcal {I}}=\{X\in 2^{E}:X{\text{에 속하는 간선들에 의한 유도 부분 그래프가 사이클을 포함하지 않음}}\}$ 로 정의하면, $(E,{\mathcal {I}})$가 매트로이드가 된다.