순환 매트로이드

매트로이드 이론에서 순환 매트로이드(循環matroid, 영어: cycle matroid)는 그래프로부터 정의될 수 있는 매트로이드이다. 순환 매트로이드의 회로는 그래프 순환이다. 순환 매트로이드의 쌍대 매트로이드는 접합 매트로이드(接合matroid, 영어: bond matroid)라고 한다.

정의

(유한 또는 무한) 그래프 $\Gamma$가 주어졌다고 하자. 그렇다면, 그 변들의 집합 $\operatorname {E} (\Gamma )$위에는 다음과 같은 두 매트로이드 구조를 줄 수 있다.

순환 매트로이드

${\mathcal {I}}(\Gamma )\subseteq \operatorname {Pow} (\operatorname {E} (\Gamma ))$가 $\Gamma$의 숲들의 집합이라고 하자.

그렇다면 $(\operatorname {E} (\Gamma ),{\mathcal {I}}(\Gamma ))$는 매트로이드를 이루며, 이를 $\Gamma$의 순환 매트로이드(영어: cycle matroid) $\operatorname {M} (\Gamma )$라고 한다.^:§2.2 순환 매트로이드의 회로는 그래프의 순환들이다.

접합 매트로이드

그래프 $\Gamma$의 절단(絶斷, 영어: cut) $B\subseteq \operatorname {E} (\Gamma )$는 제거하면 연결 성분의 수가 증가하는 변의 집합이다. 즉, 다음 세 조건들을 모두 만족시키는 두 꼭짓점 $u,v\in \operatorname {V} (\Gamma )$가 존재하여야 한다.

• $u\neq v$이다.
• $u$와 $v$ 사이의 모든 (유한) 경로가 하나 이상 존재한다. 즉, $u$와 $v$는 같은 연결 성분에 속한다.
• $u$와 $v$ 사이의 모든 (유한) 경로들은 $B$에 속하는 변을 적어도 하나 이상 포함한다.

그래프 $\Gamma$의 접합(接合, 영어: bond) $B\subseteq \operatorname {E} (\Gamma )$는 절단의 집합의 (부분 집합 관계에 대한) 극소 원소이다. 즉, 다음 두 조건을 만족시켜야 한다.

• $B$는 절단이다.
• 임의의 $e\in B$에 대하여, $B\setminus \{e\}$는 절단이 아니다.

$\Gamma$의 접합들의 집합을

${\mathcal {I}}^{*}(\Gamma )\subseteq \operatorname {Pow} (\operatorname {E} (\Gamma ))$

라고 하자.

$\Gamma$의 접합을 회로로 갖는 매트로이드

$\operatorname {M} ^{*}(\Gamma )=(\operatorname {E} (\Gamma ),{\mathcal {I}}^{*}(\Gamma ))$

를 $\Gamma$의 접합 매트로이드라고 한다.^:§2.2 접합 매트로이드는 순환 매트로이드의 쌍대 매트로이드이다.

성질

그래프 성질과의 관계

그래프의 성질과 순환 매트로이드 · 접합 매트로이드의 성질들은 다음과 같이 대응된다.

그래프	순환 매트로이드	접합 매트로이드
순환	회로	쌍대 회로
접합	쌍대 회로	회로
숲	독립 집합	쌍대 독립 집합
순환을 포함한 변 집합	종속 집합	쌍대 종속 집합
절단이 아닌 집합	쌍대 독립 집합	독립 집합
절단	쌍대 종속 집합	종속 집합
제한 그래프 마이너	제한 매트로이드 마이너	축약 매트로이드 마이너
축약 그래프 마이너	축약 매트로이드 마이너	제한 매트로이드 마이너
그래프 마이너	매트로이드 마이너	매트로이드 마이너
그래프 안둘레	매트로이드 안둘레	쌍대 매트로이드 안둘레
변 연결도	쌍대 매트로이드 안둘레	매트로이드 안둘레

특히, 순환 매트로이드와 접합 매트로이드의 매트로이드 마이너는 둘 다 그래프 마이너와 대응한다.

유한성

순환 매트로이드는 항상 유한형 매트로이드이다.^:§2.2 즉, 그 모든 회로들은 항상 유한 집합이다. 반면, 무한 그래프의 접합 매트로이드는 일반적으로 유한형 매트로이드가 아니다. (물론, 유한 그래프의 접합 매트로이드는 유한 매트로이드이다.)

예

무변 그래프의 경우, 그 순환 그래프와 접합 그래프 둘 다 크기 0의 유일한 매트로이드이다.

숲 그래프 $T$의 경우, 그 순환 매트로이드는 모든 집합이 독립 집합인 균등 매트로이드 $\operatorname {Unif} (\operatorname {E} (T),0)^{*}$이며, 그 접합 매트로이드는 공집합만이 독립 집합인 균등 매트로이드 $\operatorname {Unif} (\operatorname {E} (T),0)$이다.

순환 그래프 $C_{n}$의 경우, 그 순환 매트로이드는 균등 매트로이드 $\operatorname {Unif} (\operatorname {E} (C_{n}),n-1)$이다. 즉, 전체 집합을 제외한 모든 부분 집합이 독립 집합이다. 반대로, 그 접합 매트로이드는 균등 매트로이드 $\operatorname {Unif} (\operatorname {E} (C_{n}),1)$이다.

참고 문헌

• Oxley, James (2001). 〈On the interplay between graphs and matroids〉 (PDF). Hirschfeld, James W. P. 《Surveys in combinatorics, 2001》. London Mathematical Society Lecture Note Series (영어) 288. Cambridge University Press. 199–240쪽. doi:10.1017/CBO9780511721328.010. ISBN 978-0-521-00270-7. Zbl 0979.05030. 

외부 링크

• Mayhew, Dillon. “Graphic matroid”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Geelen, Jim (2013년 9월 30일). “Graphical representations of matroids”. 《Matroid Union》 (영어).