쾨니그의 정리: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
편집 요약 없음 |
편집 요약 없음 |
||
1번째 줄:
'''쾨니그의 정리'''({{llang|hu|Kőnig-tétel}}, Kőnig's theorem, -定理) 또는 '''홀의 정리'''(Hall's theorem)는 [[그래프 이론]] 및 [[조합적 집합론]]의 기본적이며 중요한 정리로, [[헝가리]]의 수학자 [[
==
쾨니그가 1931년 제시한 정리는 원래 그래프 이론에서의 용어를 사용한 다음과 같은 형태였다.
쾨니그의 정리의 내용을 서술하기 전에 먼저 '''변별 대표원계'''(system of distinct representatives, 辨別代表元系)의 개념을 설명할 필요가 있다. 어떤 [[집합]] S가 있고, 그 [[부분집합]] <math>A_1, A_2, .., A_m</math> 이 이루는 집합 T가 있다고 하자. 그러면 T에 대해 어떤 집합 s가 변별 대표원계라는 것은 다음과 같이 정의된다.<ref name="a"/>▼
* [[이분그래프]]에서 [[최대 매칭]]의 변 수는 최소 꼭지점 덮개(minimun vertex cover)에서의 꼭지점 수와 같다.
이 정리는 나중에 [[영국]]의 [[필립 홀]](Philip Hall)에 의해 [[1935년]] 다음과 같은 더 일반적인 집합론적 형태로 표현되었다. 두 표현은 동치이며, 이들은 [[딜워스의 정리]]와도 동치이다.
== 집합론 ==
=== 변별 대표원계 ===
▲
* 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에 대한 변별 대표원계라 한다.
줄 10 ⟶ 18:
이 변별 대표원계의 개념에서 왜 이 정리가 결혼정리로 불리는지를 알 수 있다. r명의 남자(혹은 r명의 여자)가 결혼했으면 하는 여자(혹은 남자)의 표를 만들 때, 각 사람이 자기 표에 있는 이성과 결혼하는 것이 가능할 필요충분조건은 그 표가 변별 대표원계를 갖는 것이기 때문이다.<ref name="a"/>
=== 공식화 ===
쾨니그의 정리는 다음과 같이 공식화할 수 있다.<ref name="a"/> 이 꼴의 쾨니그의 정리는 일반적으로 홀의 정리로 불린다.
* 앞에서와 같이 정의된 집합 S, T에 대하여 T가 변별 대표원계를 가질 필요충분조건은 각각의 r≤m에 대해 r개 <math>A_i</math>의 [[합집합]]이 적어도 r개의 원소를 가지는 것이다.
| |||