쾨니그의 정리

이 문서는 그래프의 꼭짓점 덮개와 최대 부합에 관한 것입니다. 무한 그래프에 대한 정리에 대해서는 쾨니그 보조정리 문서를, 기수에 대한 정리에 대해서는 쾨니그의 정리 (집합론) 문서를 참고하십시오.

그래프 이론 및 조합론에서 쾨니그의 정리(Kőnig의定理, 영어: Kőnig’s theorem)는 이분 그래프에 대한 최소 꼭짓점 덮개 문제와 최대 부합 문제가 서로 동치라는 정리다.

정의

최대 부합의 변(청색) 수는 최소 꼭짓점 덮개의 꼭짓점(적색) 수와 같다.

어떤 그래프 $\Gamma$의 꼭짓점 덮개(영어: vertex cover) $C\subset V(\Gamma )$는 다음을 만족시키는 집합이다.

• 모든 변 $e\in E(\Gamma )$에 대하여, $e$와 접하는 $c\in C$가 존재한다.

최소 꼭짓점 덮개는 크기가 최소인 꼭짓점 덮개이다.

쾨니그의 정리에 따르면, 이분 그래프 $\Gamma$의 최대 부합 $M\subset E(\Gamma )$ 및 최소 꼭짓점 덮개 $C\subset V(\Gamma )$에 대하여,

$|M|=|C|$

이다.

조합적 집합론에서는 쾨니그의 정리를 일반화하는 홀 결혼 정리가 존재한다. 쾨니그의 정리와 홀의 정리는 서로 동치이며, 이들은 딜워스의 정리와도 동치이다.

역사

헝가리의 수학자 쾨니그 데네시가 1931년에 증명하였다.^:289

외부 링크

• “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.