매트로이드 마이너 문서 원본 보기

{{위키데이터 속성 추적}}
[[매트로이드 이론]]에서 '''매트로이드 마이너'''({{llang|en|matroid minor}})는 주어진 [[매트로이드]]에서 일부 [[원소 (수학)|원소]]를 “삭제”하거나, 일부 원소를 “축약”하여 얻어지는 매트로이드이다. [[그래프 마이너]]의 일반화이다.

== 정의 ==
(유한 또는 무한) [[매트로이드]] <math>(X,\mathcal I)</math>가 주어졌다고 하자. 그렇다면, 그 부분 집합 <math>S\subseteq X</math>에 대하여,
:<math>X\restriction S=(S,\{I\cap S\}_{I\in\mathcal I})</math>
역시 [[매트로이드]]를 이룬다.<ref name="BDKPW"/>{{rp|Theorem 3.4}} 이를 <math>X</math>의 <math>S</math>로의 '''제한'''이라고 한다. (즉, 이 과정은 <math>X\setminus S</math>의 '''삭제'''({{llang|en|deletion}})이다.)
<div class="mw-collapsible mw-collapsed toccolours">
'''증명:'''
<div class="mw-collapsible-content">
<math>\mathcal I_S=\{I\cap S\}_{I\in\mathcal I}=\{I\in\mathcal I\colon I\subseteq S\}</math>로 놓자.
(유한 또는 무한) [[매트로이드]]의 네 공리들<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|§1.1}}은 다음과 같이 확인할 수 있다.
* (I1) <math>\varnothing\in\{I\cap S\}_{I\in\mathcal I}</math>: 자명하게 참이다.
* (I2) 만약 <math>J\subseteq I\in\mathcal I</math>일 때, <math>J\cap S\subseteq I\cap S\in\mathcal I_S</math>이므로 <math>J\cap S\in\mathcal I_S</math>이다.
* (IM) 임의의 <math>I\in\mathcal I_S\subseteq\mathcal I</math> 및 <math>I\subseteq T\subseteq S\subseteq X</math>에 대하여, <math>\{J\in\mathcal I_S\colon I\subseteq J\subseteq T\}
=\{J\in\mathcal I\colon I\subseteq J\subseteq T\}
</math>는 매트로이드의 공리에 따라 [[극대 원소]]를 갖는다.

유일하게 자명하지 않은 것은 공리 (I3)이다.

임의의 <math>I\in\mathcal I_S</math>, <math>J\in\max\mathcal I_S</math>가 주어졌다고 하자. 그렇다면, (IM) 공리를 사용하여,
:<math>J\subseteq J'\in\max\mathcal I</math>
를 찾을 수 있으며, <math>J\in\max\mathcal I_S</math>이므로
:<math>J'\cap S=J</math>
이다.

(I3) 공리를 거듭 사용하여,
:<math>I\subseteq I'\subseteq I\cup J'</math>
:<math>I'\in\max\mathcal I</math>
인 <math>I'</math>을 찾을 수 있다.

이제,
:<math>I'\cap S\in\max\mathcal I_S</math>
:<math>I\subseteq I'\cap S\subseteq I\cup J</math>
를 보이면 족하다. 이 가운데 유일하게 자명하지 않은 것은 <math>I'\cap S\subseteq I\cup J</math>이며, 그 증명은
:<math>I'\cap S\subseteq (I\cup J')\cap S=(I\cap S)\cup (J'\cap S)=I\cup J</math>
이다.
</div></div>

(유한 또는 무한) [[매트로이드]] <math>(X,\mathcal I)</math>가 주어졌다고 하자. 그렇다면, 그 부분 집합 <math>S\subseteq X</math>에 대하여, 쌍대 매트로이드의 제한의 쌍대 매트로이드
:<math>X.S = (X^*\restriction S)^*=\left(S,\bigcup_{B\in\max\mathcal I}\operatorname{Pow}(S\setminus B)\right)</math>
를 정의할 수 있다. (<math>\operatorname{Pow}(-)</math>는 [[멱집합]]이다.) 이는 매트로이드를 이루며, 이를 <math>X</math>의, <math>S</math>로의 '''축약'''({{llang|en|contraction}})하여 얻는 매트로이드라고 한다.<ref name="BDKPW"/>{{rp|§3}} (즉, 이 과정은 <Math>X\setminus S</math>의 '''축약'''이라고 한다.)

축약과 제한을 거듭 사용하여 얻는 매트로이드
:<math>(X',\mathcal I')</math>
:<math>X'\subseteq X</math>
를 <math>X</math>의 '''마이너'''라고 한다.

== 성질 ==
=== 그래프와의 관계 ===
[[그래프 마이너]]는 매트로이드 마이너의 특수한 경우이다. 구체적으로, (유한 또는 무한) [[그래프]] <math>\Gamma</math>의 (유한형) [[순환 매트로이드]]를 <math>\operatorname M(\Gamma)</math>라고 하자.

또한, 임의의 변의 집합
:<math>S\subseteq\operatorname M(\Gamma)</math>
이 주어졌다고 하자.

그렇다면, 다음이 성립한다.
:<math>\operatorname M(\Gamma\restriction S)=\operatorname M(\Gamma)\restriction S</math>
:<math>\operatorname M(\Gamma.S)=\operatorname M(\Gamma).S</math>
:<math>\operatorname M(\Gamma\sqcup K_0) = \operatorname M(\Gamma)</math>
즉,
* [[그래프]]에서 <math>S</math>에 속하지 않는 변들의 삭제는 순환 매트로이드에서 <math>S</math>에 속하지 않는 원소들의 삭제와 같다.
* [[그래프]]에서 <math>S</math>에 속하지 않는 변들의 축약은 순환 매트로이드에서 <math>S</math>에 속하지 않는 원소들의 축약과 같다.
* [[그래프]]에서, 홑 꼭짓점(아무 변과 결합하지 않는 꼭짓점)의 삭제는 그 순환 매트로이드에 영향을 주지 않는다.

이에 따라, 그래프의 순환 매트로이드의 매트로이드 마이너는 [[그래프 마이너]]의 순환 매트로이드이다.

=== 정렬 원순서가 아님 ===
[[유한 그래프]]의 [[그래프 마이너]] 관계는 [[정렬 원순서]]를 이룬다 (로버트슨-시모어 정리). 즉, [[유한 그래프]]의 순환 매트로이드들로 국한하였을 때, 매트로이드 마이너 관계는 [[정렬 원순서]]를 이룬다.

그러나 모든 유한 매트로이드의 [[집합]] 위에서, 매트로이드 마이너 관계는 [[정렬 원순서]]를 이루지 못한다.

== 각주 ==
{{각주}}
* {{서적 인용|장=Structure in minor-closed classes of matroids
|이름=Jim|성=Geelen|이름2=Bert|성2=Gerards|이름3=Geoff|성3=Whittle|장url=http://homepages.mcs.vuw.ac.nz/~whittle/pubs/preprint-structure-in-minor-closed-classes-of-matroids.pdf |쪽=327–362|제목=Surveys in combinatorics 2013|editor1-first=Simon R.|editor1-last=Blackburn|editor2-first=Stefanie|editor2-last=Gerke|editor3-first=Mark|editor3-last=Wildon|isbn=978-1-107-65195-1|doi=10.1017/CBO9781139506748.009|출판사=Cambridge University Press|날짜=2013-07|총서=London Mathematical Society Lecture Note Series|권=409|언어=en}}
* {{서적 인용|last=Truemper|first=Klaus|title=Matroid decomposition|publisher=Academic Press|location=Boston|날짜=1992|isbn=0-12-701225-7|url=http://www.emis.de/monographs/md/index.html|mr=1170126|zbl=0760.05001|언어=en|access-date=2017-07-09|archive-date=2017-11-07|archive-url=https://web.archive.org/web/20171107151220/http://www.emis.de/monographs/md/index.html}}

== 외부 링크 ==
* {{웹 인용|url=http://matroidunion.org/?p=139|제목=Matroids with no ''M''(''K''<sub>4</sub>)-minor|이름=Jim|성=Geelen|날짜=2013-09-02|웹사이트=Matroid Union|언어=en}}

[[분류:매트로이드 이론]]