매트로이드 마이너
매트로이드 이론에서 매트로이드 마이너(영어: matroid minor)는 주어진 매트로이드에서 일부 원소를 “삭제”하거나, 일부 원소를 “축약”하여 얻어지는 매트로이드이다. 그래프 마이너의 일반화이다.
정의
[편집](유한 또는 무한) 매트로이드 가 주어졌다고 하자. 그렇다면, 그 부분 집합 에 대하여,
역시 매트로이드를 이룬다.[1]:Theorem 3.4 이를 의 로의 제한이라고 한다. (즉, 이 과정은 의 삭제(영어: deletion)이다.)
증명:
로 놓자. (유한 또는 무한) 매트로이드의 네 공리들[1]:§1.1은 다음과 같이 확인할 수 있다.
- (I1) : 자명하게 참이다.
- (I2) 만약 일 때, 이므로 이다.
- (IM) 임의의 및 에 대하여, 는 매트로이드의 공리에 따라 극대 원소를 갖는다.
유일하게 자명하지 않은 것은 공리 (I3)이다.
임의의 , 가 주어졌다고 하자. 그렇다면, (IM) 공리를 사용하여,
를 찾을 수 있으며, 이므로
이다.
(I3) 공리를 거듭 사용하여,
인 을 찾을 수 있다.
이제,
를 보이면 족하다. 이 가운데 유일하게 자명하지 않은 것은 이며, 그 증명은
이다.
(유한 또는 무한) 매트로이드 가 주어졌다고 하자. 그렇다면, 그 부분 집합 에 대하여, 쌍대 매트로이드의 제한의 쌍대 매트로이드
를 정의할 수 있다. (는 멱집합이다.) 이는 매트로이드를 이루며, 이를 의, 로의 축약(영어: contraction)하여 얻는 매트로이드라고 한다.[1]:§3 (즉, 이 과정은 의 축약이라고 한다.)
축약과 제한을 거듭 사용하여 얻는 매트로이드
를 의 마이너라고 한다.
성질
[편집]그래프와의 관계
[편집]그래프 마이너는 매트로이드 마이너의 특수한 경우이다. 구체적으로, (유한 또는 무한) 그래프 의 (유한형) 순환 매트로이드를 라고 하자.
또한, 임의의 변의 집합
이 주어졌다고 하자.
그렇다면, 다음이 성립한다.
즉,
- 그래프에서 에 속하지 않는 변들의 삭제는 순환 매트로이드에서 에 속하지 않는 원소들의 삭제와 같다.
- 그래프에서 에 속하지 않는 변들의 축약은 순환 매트로이드에서 에 속하지 않는 원소들의 축약과 같다.
- 그래프에서, 홑 꼭짓점(아무 변과 결합하지 않는 꼭짓점)의 삭제는 그 순환 매트로이드에 영향을 주지 않는다.
이에 따라, 그래프의 순환 매트로이드의 매트로이드 마이너는 그래프 마이너의 순환 매트로이드이다.
정렬 원순서가 아님
[편집]유한 그래프의 그래프 마이너 관계는 정렬 원순서를 이룬다 (로버트슨-시모어 정리). 즉, 유한 그래프의 순환 매트로이드들로 국한하였을 때, 매트로이드 마이너 관계는 정렬 원순서를 이룬다.
그러나 모든 유한 매트로이드의 집합 위에서, 매트로이드 마이너 관계는 정렬 원순서를 이루지 못한다.
각주
[편집]- ↑ 가 나 다 Bruhn, Henning; Diestel, Reinhard; Kriesell, Matthias; Pendavingh, Rudi A.; Wollan, Paul (2013년 6월 1일). “Axioms for infinite matroids”. 《Advances in Mathematics》 (영어) 239: 18–46. arXiv:1003.3919. Bibcode:2010arXiv1003.3919B. doi:10.1016/j.aim.2013.01.011. Zbl 1279.05013.
- Geelen, Jim; Gerards, Bert; Whittle, Geoff (2013년 7월). 〈Structure in minor-closed classes of matroids〉 (PDF). Blackburn, Simon R.; Gerke, Stefanie; Wildon, Mark. 《Surveys in combinatorics 2013》. London Mathematical Society Lecture Note Series (영어) 409. Cambridge University Press. 327–362쪽. doi:10.1017/CBO9781139506748.009. ISBN 978-1-107-65195-1.
- Truemper, Klaus (1992). 《Matroid decomposition》 (영어). Boston: Academic Press. ISBN 0-12-701225-7. MR 1170126. Zbl 0760.05001. 2017년 11월 7일에 원본 문서에서 보존된 문서. 2017년 7월 9일에 확인함.
외부 링크
[편집]- Geelen, Jim (2013년 9월 2일). “Matroids with no M(K4)-minor”. 《Matroid Union》 (영어).