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

140 바이트 제거됨 ,  7년 전
어떤 그래프 <math>\Gamma</math>의 '''꼭지점 덮개''' <math>C\subset V(\Gamma)</math>는 다음을 만족시키는 집합이다.
* 모든 변 <math>e\in E(\Gamma)</math>에 대하여, <math>e</math>와 접하는 <math>c\in C</math>가 존재한다.
<math>\Gamma</math>의 꼭지점 덮개들의 집합은 포함 관계에 따라서 [[부분 순서 집합]]을 이루며, '''최소 꼭지점 덮개'''는 크기가 부분 순서에 대한 최소최소인 꼭지점 덮개'''이다덮개이다.
 
'''쾨니그의 정리'''에 따르면, [[이분 그래프]] <math>\Gamma</math>의 최대 매칭 <math>M\subset E(\Gamma)</math> 및 최소 꼭지점 덮개 <math>C\subset V(\Gamma)</math>에 대하여,