"쾨니그의 정리"의 두 판 사이의 차이

잔글
편집 요약 없음
잔글
[[그래프 이론]] 및 [[조합론]]에서, '''쾨니그의 정리'''(Kőnig의定理, {{llang|en|Kőnig’s theorem}})는 [[이분 그래프]]에 대한 최소 꼭지점꼭짓점 덮개 문제와 [[최대 부합]] 문제가 서로 [[동치]]라는 정리다.
 
== 정의 ==
[[파일:Koenigs-theorem-graph.svg|thumb|right|[[최대 부합]]의 변(청색) 수는 최소 꼭지점꼭짓점 덮개의 꼭지점꼭짓점(적색) 수와 같다.]]
 
어떤 그래프 <math>\Gamma</math>의 '''꼭지점꼭짓점 덮개'''({{llang|en|vertex cover}}) <math>C\subset V(\Gamma)</math>는 다음을 만족시키는 집합이다.
* 모든 변 <math>e\in E(\Gamma)</math>에 대하여, <math>e</math>와 접하는 <math>c\in C</math>가 존재한다.
'''최소 꼭지점꼭짓점 덮개'''는 크기가 최소인 꼭지점꼭짓점 덮개이다.
 
'''쾨니그의 정리'''에 따르면, [[이분 그래프]] <math>\Gamma</math>의 [[최대 부합]] <math>M\subset E(\Gamma)</math> 및 최소 꼭지점꼭짓점 덮개 <math>C\subset V(\Gamma)</math>에 대하여,
:<math>|M|=|C|</math>
이다.