위키백과

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

입체적으로 역사 찾아보기
← 이전 편집다음 편집 →
내용 삭제됨 내용 추가됨
시각위키텍스트
편집 요약 없음
편집 요약 없음
1번째 줄:
[[그래프 이론]] 및 [[조합론]]에서, '''쾨니그의 정리'''(Kőnig의定理, {{llang|en|Kőnig’s theorem}})는 [[이분 그래프]]에 대한 최소 꼭지점 덮개 문제와 [[최대 매칭]] 문제가 서로 [[동치]]라는 정리다.
 
== 그래프 이론정의 ==
[[파일:Koenigs-theorem-graph.svg|thumb|right|최대 매칭의 변(청색) 수는 최소 꼭지점 덮개의 꼭지점(적색) 수와 같다.]]
 
어떤 그래프에서 꼭지점의 집합으로서 그 그래프에 속하는 모든 변이 그 집합에 속하는 하나 이상의 원소와 접하는 경우 그 집합을 '''꼭지점 덮개'''({{llang|en|vertex cover}})라 한다. '''최소 꼭지점 덮개'''({{llang|en|minimum vertex cover}})는 가장 원소의 수가 적은 꼭지점 덮개를 말한다. '''쾨니그의 정리'''에 따르면, [[이분 그래프]]에서 [[최대 매칭]]의 변 수는 최소 꼭지점 덮개에서의 꼭지점 수와 같다.
 
== 홀 결혼 정리 ==
조합적 집합론에서는 쾨니그의 정리를 일반화하는 '''홀 결혼 정리'''({{llang|en|Hall’s theorem}})가 존재한다. 쾨니그의 정리와 홀의 정리는 서로 [[동치]]이며, 이들은 [[딜워스의 정리]]와도 동치이다.
 
이 정리의 집합론적 공식화를 서술하기 전에 먼저 '''변별 대표원계'''(system of distinct representatives, 辨別代表元系)의 개념을 설명할 필요가 있다. 어떤 [[집합]] S가 있고, 그 [[부분집합]] <math>A_1, A_2, .., A_m</math> 이 이루는 집합족 T가 있다고 하자. 그러면 T에 대해 어떤 집합 s가 '''변별 대표원계라는대표원계'''(辨別代表元系, {{llang|en|system of distinct representatives}})라는 것은 다음과 같이 정의된다.<ref name="윤영진"/>{{rp|289}}
 
* S의 서로 다른 원소 <math>a_1, a_2, .., a_r</math> 이 <math>a_i \in A_i (i = 1, 2, .., r)</math> 일 때, T의 원소를 [[정의역]]으로 하고 S를 [[공역 (수학)|공역]]으로 하며 <math>s(A_i) = a_i</math> 를 만족하는 [[함수]] s를 T에 대한 변별 대표원계라 한다.
 
원본 주소 "https://ko.wikipedia.org/wiki/쾨니그의_정리"