순환 매트로이드 문서 원본 보기

{{위키데이터 속성 추적}}
[[매트로이드 이론]]에서 '''순환 매트로이드'''(循環matroid, {{llang|en|cycle matroid}})는 [[그래프]]로부터 정의될 수 있는 [[매트로이드]]이다. 순환 매트로이드의 회로는 [[순환 (그래프 이론)|그래프 순환]]이다. 순환 매트로이드의 쌍대 매트로이드는 '''접합 매트로이드'''(接合matroid, {{llang|en|bond matroid}})라고 한다.

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

=== 순환 매트로이드 ===
<math>\mathcal I(\Gamma)\subseteq\operatorname{Pow}(\operatorname E(\Gamma))</math>가 <math>\Gamma</math>의 [[나무 그래프|숲]]들의 집합이라고 하자.

그렇다면 <math>(\operatorname E(\Gamma),\mathcal I(\Gamma))</math>는 매트로이드를 이루며, 이를 <math>\Gamma</math>의 '''순환 매트로이드'''({{llang|en|cycle matroid}}) <math>\operatorname M(\Gamma)</math>라고 한다.<ref name="BDKPW"/>{{rp|§2.2}} 순환 매트로이드의 회로는 그래프의 [[순환 (그래프 이론)|순환]]들이다.

=== 접합 매트로이드 ===
[[그래프]] <math>\Gamma</math>의 '''절단'''(絶斷, {{llang|en|cut}}) <math>B\subseteq\operatorname E(\Gamma)</math>는 제거하면 [[연결 성분]]의 수가 증가하는 변의 집합이다. 즉, 다음 세 조건들을 모두 만족시키는 두 꼭짓점 <math>u,v\in\operatorname V(\Gamma)</math>가 존재하여야 한다.
* <math>u\ne v</math>이다.
* <math>u</math>와 <math>v</math> 사이의 모든 (유한) [[경로 (그래프 이론)|경로]]가 하나 이상 존재한다. 즉, <math>u</math>와 <math>v</math>는 같은 [[연결 성분]]에 속한다.
* <math>u</math>와 <math>v</math> 사이의 모든 (유한) [[경로 (그래프 이론)|경로]]들은 <math>B</math>에 속하는 변을 적어도 하나 이상 포함한다.

[[그래프]] <math>\Gamma</math>의 '''접합'''(接合, {{llang|en|bond}}) <math>B\subseteq\operatorname E(\Gamma)</math>는 절단의 집합의 ([[부분 집합]] 관계에 대한) [[극소 원소]]이다. 즉, 다음 두 조건을 만족시켜야 한다.
* <math>B</math>는 절단이다.
* 임의의 <math>e\in B</math>에 대하여, <math>B\setminus\{e\}</math>는 절단이 아니다.
<math>\Gamma</math>의 접합들의 집합을
:<math>\mathcal I^*(\Gamma)\subseteq\operatorname{Pow}(\operatorname E(\Gamma))</math>
라고 하자.

<math>\Gamma</math>의 접합을 회로로 갖는 [[매트로이드]]
:<math>\operatorname M^*(\Gamma)=(\operatorname E(\Gamma),\mathcal I^*(\Gamma))</math>
를 <math>\Gamma</math>의 '''접합 매트로이드'''라고 한다.<ref name="BDKPW"/>{{rp|§2.2}} 접합 매트로이드는 순환 매트로이드의 쌍대 매트로이드이다.

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

{| class=wikitable
! 그래프 !! 순환 매트로이드 !! 접합 매트로이드
|-
| [[순환 (그래프 이론)|순환]] || 회로 || 쌍대 회로
|-
| 접합 || 쌍대 회로 || 회로
|-
| [[나무 그래프|숲]] || 독립 집합 || 쌍대 독립 집합
|-
| [[순환 (그래프 이론)|순환]]을 포함한 변 집합 || 종속 집합 || 쌍대 종속 집합
|-
| 절단이 아닌 집합 || 쌍대 독립 집합 || 독립 집합
|-
| 절단 || 쌍대 종속 집합 || 종속 집합
|-
| 제한 그래프 마이너 || 제한 매트로이드 마이너 || 축약 매트로이드 마이너
|-
| 축약 그래프 마이너 || 축약 매트로이드 마이너 || 제한 매트로이드 마이너
|-
| [[그래프 마이너]] || [[매트로이드 마이너]] || [[매트로이드 마이너]]
|-
| [[안둘레|그래프 안둘레]] || [[안둘레|매트로이드 안둘레]] || 쌍대 [[안둘레|매트로이드 안둘레]]
|-
| [[안둘레|변 연결도]] || 쌍대 [[안둘레|매트로이드 안둘레]] || [[안둘레|매트로이드 안둘레]]
|}

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

=== 유한성 ===
순환 매트로이드는 항상 유한형 매트로이드이다.<ref name="BDKPW">{{저널 인용|제목=Axioms for infinite matroids|이름=Henning|성=Bruhn|이름2=Reinhard|성2=Diestel|이름3=Matthias|성3=Kriesell|이름4=Rudi A.|성4=Pendavingh|이름5=Paul |성5=Wollan|arxiv=1003.3919|doi=10.1016/j.aim.2013.01.011|bibcode=2010arXiv1003.3919B|저널=Advances in Mathematics|권=239|날짜=2013-06-01|쪽=18–46|zbl=1279.05013|언어=en}}</ref>{{rp|§2.2}} 즉, 그 모든 회로들은 항상 [[유한 집합]]이다. 반면, 무한 그래프의 접합 매트로이드는 일반적으로 유한형 매트로이드가 아니다. (물론, [[유한 그래프]]의 접합 매트로이드는 유한 매트로이드이다.)

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

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

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

== 각주 ==
{{각주}}
* {{서적 인용|장=On the interplay between graphs and matroids|이름=James|성=Oxley|장url=https://www.math.lsu.edu/~oxley/bcex7.pdf | zbl=0979.05030 | 제목=Surveys in combinatorics, 2001 | 날짜=2001 | doi=10.1017/CBO9780511721328.010 | editor1-first= James W. P. |editor1-last= Hirschfeld|출판사=Cambridge University Press|총서=London Mathematical Society Lecture Note Series |권=288 |isbn=978-0-521-00270-7|쪽=199–240|언어=en}}

== 외부 링크 ==
* {{매스월드|id=GraphicMatroid|title=Graphic matroid|이름=Dillon |성=Mayhew}}
* {{웹 인용|url=http://matroidunion.org/?p=266 | 제목=Graphical representations of matroids | 웹사이트=Matroid Union | 이름=Jim | 성=Geelen | 날짜=2013-09-30 | 언어=en}}

{{전거 통제}}

[[분류:그래프 이론]]
[[분류:매트로이드 이론]]
[[분류:평면 그래프]]