쾨니그의 정리
보이기
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Disambig_grey.svg/23px-Disambig_grey.svg.png)
그래프 이론 및 조합론에서 쾨니그의 정리(Kőnig의定理, 영어: Kőnig’s theorem)는 이분 그래프에 대한 최소 꼭짓점 덮개 문제와 최대 부합 문제가 서로 동치라는 정리다.
정의
[편집]![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2e/Koenigs-theorem-graph.svg/220px-Koenigs-theorem-graph.svg.png)
어떤 그래프 의 꼭짓점 덮개(영어: vertex cover) 는 다음을 만족시키는 집합이다.
- 모든 변 에 대하여, 와 접하는 가 존재한다.
최소 꼭짓점 덮개는 크기가 최소인 꼭짓점 덮개이다.
쾨니그의 정리에 따르면, 이분 그래프 의 최대 부합 및 최소 꼭짓점 덮개 에 대하여,
이다.
조합적 집합론에서는 쾨니그의 정리를 일반화하는 홀 결혼 정리가 존재한다. 쾨니그의 정리와 홀의 정리는 서로 동치이며, 이들은 딜워스의 정리와도 동치이다.
역사
[편집]헝가리의 수학자 쾨니그 데네시가 1931년에 증명하였다.[1][2]:289
각주
[편집]- ↑ Kőnig Dénes (1931). “Gráfok és mátrixok”. 《Matematikai és Fizikai Lapok》 (헝가리어) 38: 116–119. Zbl 0003.32803.
- ↑ 윤영진 (2007). 《새로운 조합수학》. 교우사. ISBN 978-89-8172-379-8.
외부 링크
[편집]- “König theorem”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
- Weisstein, Eric Wolfgang. “König's Line Coloring Theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research.