쾨니그의 정리: 두 판 사이의 차이
Osteologia (토론 | 기여) 잔글편집 요약 없음 |
Osteologia (토론 | 기여) 편집 요약 없음 |
||
| 1번째 줄: | 1번째 줄: | ||
[[그래프 이론]] 및 [[조합론]]에서, '''쾨니그의 정리'''(Kőnig의定理, {{llang|en|Kőnig’s theorem}})는 [[이분 그래프]]에 대한 최소 꼭지점 덮개 문제와 [[최대 매칭]] 문제가 서로 [[동치]]라는 정리다. |
|||
'''쾨니그의 정리'''({{llang|hu|Kőnig-tétel}}, Kőnig's theorem, -定理) 또는 '''홀의 정리'''(Hall's theorem)는 [[그래프 이론]] 및 [[조합적 집합론]]의 기본적이며 중요한 정리로, [[헝가리]]의 수학자 [[쾨니그 데네시]](Kőnig Dénes)가 [[1931년]] 처음 제시하였다.<ref name="a">윤영진, 《새로운 조합수학》, 교우사, 2007, 289쪽.</ref> 이 정리는 어떤 집합의 적당한 부분집합들이 이루는 집합이 변별 대표원계를 가질 필요충분조건을 제시하고 있다. 그 내용 때문에 이 정리는 '''결혼정리'''(結婚定理)라고 불리기도 한다.<ref name="a"/> |
|||
== 그래프 이론 == |
== 그래프 이론 == |
||
[[파일:Koenigs-theorem-graph.svg|thumb|right|최대 매칭의 변(청색) 수는 최소 꼭지점 덮개의 꼭지점(적색) 수와 같다.]] |
[[파일:Koenigs-theorem-graph.svg|thumb|right|최대 매칭의 변(청색) 수는 최소 꼭지점 덮개의 꼭지점(적색) 수와 같다.]] |
||
| ⚫ | |||
쾨니그가 1931년 제시한 정리는 원래 그래프 이론에서의 용어를 사용한 다음과 같은 형태였다. |
|||
== 홀 결혼 정리 == |
|||
| ⚫ | |||
조합적 집합론에서는 쾨니그의 정리를 일반화하는 '''홀 결혼 정리'''({{llang|en|Hall’s theorem}})가 존재한다. 쾨니그의 정리와 홀의 정리는 서로 [[동치]]이며, 이들은 [[딜워스의 정리]]와도 동치이다. |
|||
| ⚫ | |||
이 정리는 나중에 [[영국]]의 [[필립 홀]](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에 대한 변별 대표원계라 한다. |
* 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에 대한 변별 대표원계라 한다. |
||
| 18번째 줄: | 15번째 줄: | ||
집합 S에서 얻을 수 있는 집합족 T는 변별 대표원계를 가질 수도, 가지지 않을 수도 있다. 또 변별 대표원계를 갖는 경우 유일하지 않을 수도 있다. 여기서 T가 변별 대표원계를 가지는 필요충분조건이 바로 이하의 정리로 주어지는 것이다. |
집합 S에서 얻을 수 있는 집합족 T는 변별 대표원계를 가질 수도, 가지지 않을 수도 있다. 또 변별 대표원계를 갖는 경우 유일하지 않을 수도 있다. 여기서 T가 변별 대표원계를 가지는 필요충분조건이 바로 이하의 정리로 주어지는 것이다. |
||
이 변별 대표원계의 개념에서 왜 이 정리가 결혼정리로 불리는지를 알 수 있다. r명의 남자(혹은 r명의 여자)가 결혼했으면 하는 여자(혹은 남자)의 표를 만들 때, 각 사람이 자기 표에 있는 이성과 결혼하는 것이 가능할 필요충분조건은 그 표가 변별 대표원계를 갖는 것이기 때문이다.<ref name=" |
이 변별 대표원계의 개념에서 왜 이 정리가 결혼정리로 불리는지를 알 수 있다. r명의 남자(혹은 r명의 여자)가 결혼했으면 하는 여자(혹은 남자)의 표를 만들 때, 각 사람이 자기 표에 있는 이성과 결혼하는 것이 가능할 필요충분조건은 그 표가 변별 대표원계를 갖는 것이기 때문이다.<ref name="윤영진"/>{{rp|289}} |
||
| ⚫ | |||
=== 공식화 === |
|||
| ⚫ | |||
* 앞에서와 같이 정의된 S, T에 대하여 T가 변별 대표원계를 가질 필요충분조건은 각각의 r≤m에 대해 r개 <math>A_i</math>의 [[합집합]]이 적어도 r개의 원소를 가지는 것이다. |
* 앞에서와 같이 정의된 S, T에 대하여 T가 변별 대표원계를 가질 필요충분조건은 각각의 r≤m에 대해 r개 <math>A_i</math>의 [[합집합]]이 적어도 r개의 원소를 가지는 것이다. |
||
여기서 →의 방향은 변별 대표원계의 정의에 따라 자명하므로, |
여기서 →의 방향은 변별 대표원계의 정의에 따라 자명하므로, 홀 결혼 정리에서 실제로 증명할 것은 ←의 방향이다. |
||
== |
== 역사 == |
||
[[헝가리]]의 수학자 [[쾨니그 데네시]](Kőnig Dénes)가 [[1931년]]에 증명하였다.<ref>{{저널 인용 |
|||
{{reflist}} |
|||
| 저자 = Kőnig Dénes | 제목 = Gráfok és mátrixok |
|||
| journal = Matematikai és Fizikai Lapok |
|||
| volume = 38 |
|||
| 날짜 = 1931 |
|||
| pages = 116–119 | 언어고리=hu}}</ref><ref name="윤영진">{{책 인용|저자=윤영진|제목=새로운 조합수학|출판사=교우사|날짜=2007|isbn=978-89-8172-379-8|url=http://www.kyowoo.co.kr/02_sub/view.php?p_idx=334|언어고리=ko}}</ref>{{rp|289}} [[영국]]의 [[필립 홀]]({{llang|en|Philip Hall}})이 쾨니그의 정리와 [[동치]]인 홀 결혼 정리를 1935년에 증명하였다.<ref>{{저널 인용 | last=Hall | first=Philip | title=On representatives of subsets | doi=10.1112/jlms/s1-10.37.26 | 날짜=1935 | journal=Journal of the London Mathematical Society | volume=10 | issue=1 | pages=26–30 | 언어고리=en}}</ref> |
|||
== 참고 문헌 == |
== 참고 문헌 == |
||
{{주석}} |
|||
* {{책 인용|저자=윤영진|제목=새로운 조합수학|출판사=교우사|날짜=2007|isbn=978-89-8172379-8|언어고리=ko}} |
|||
== 바깥 고리 == |
|||
* {{eom|title=König theorem}} |
|||
* {{eom|title=Combinatorial analysis}} <!-- 홀 결혼 정리 포함 --> |
|||
* {{매스월드|id=KoenigsLineColoringTheorem|title=König's Line Coloring Theorem}} |
|||
* {{매스월드|id=MarriageTheorem|title=Marriage theorem}} |
|||
[[분류:그래프 이론]] |
[[분류:그래프 이론]] |
||
2014년 12월 2일 (화) 08:19 판
그래프 이론 및 조합론에서, 쾨니그의 정리(Kőnig의定理, 영어: Kőnig’s theorem)는 이분 그래프에 대한 최소 꼭지점 덮개 문제와 최대 매칭 문제가 서로 동치라는 정리다.
그래프 이론
어떤 그래프에서 꼭지점의 집합으로서 그 그래프에 속하는 모든 변이 그 집합에 속하는 하나 이상의 원소와 접하는 경우 그 집합을 꼭지점 덮개(vertex cover)라 한다. 최소 꼭지점 덮개(minimum vertex cover)는 가장 원소의 수가 적은 꼭지점 덮개를 말한다. 쾨니그의 정리에 따르면, 이분 그래프에서 최대 매칭의 변 수는 최소 꼭지점 덮개에서의 꼭지점 수와 같다.
홀 결혼 정리
조합적 집합론에서는 쾨니그의 정리를 일반화하는 홀 결혼 정리(영어: Hall’s theorem)가 존재한다. 쾨니그의 정리와 홀의 정리는 서로 동치이며, 이들은 딜워스의 정리와도 동치이다.
이 정리의 집합론적 공식화를 서술하기 전에 먼저 변별 대표원계(system of distinct representatives, 辨別代表元系)의 개념을 설명할 필요가 있다. 어떤 집합 S가 있고, 그 부분집합 이 이루는 집합족 T가 있다고 하자. 그러면 T에 대해 어떤 집합 s가 변별 대표원계라는 것은 다음과 같이 정의된다.[1]:289
집합 S에서 얻을 수 있는 집합족 T는 변별 대표원계를 가질 수도, 가지지 않을 수도 있다. 또 변별 대표원계를 갖는 경우 유일하지 않을 수도 있다. 여기서 T가 변별 대표원계를 가지는 필요충분조건이 바로 이하의 정리로 주어지는 것이다.
이 변별 대표원계의 개념에서 왜 이 정리가 결혼정리로 불리는지를 알 수 있다. r명의 남자(혹은 r명의 여자)가 결혼했으면 하는 여자(혹은 남자)의 표를 만들 때, 각 사람이 자기 표에 있는 이성과 결혼하는 것이 가능할 필요충분조건은 그 표가 변별 대표원계를 갖는 것이기 때문이다.[1]:289
이 꼴의 홀 결혼 정리는 다음과 같이 공식화할 수 있다.[1]:289 일반적으로 이는 '홀의 정리'로 불린다.
- 앞에서와 같이 정의된 S, T에 대하여 T가 변별 대표원계를 가질 필요충분조건은 각각의 r≤m에 대해 r개 의 합집합이 적어도 r개의 원소를 가지는 것이다.
여기서 →의 방향은 변별 대표원계의 정의에 따라 자명하므로, 홀 결혼 정리에서 실제로 증명할 것은 ←의 방향이다.
역사
헝가리의 수학자 쾨니그 데네시(Kőnig Dénes)가 1931년에 증명하였다.[2][1]:289 영국의 필립 홀(영어: Philip Hall)이 쾨니그의 정리와 동치인 홀 결혼 정리를 1935년에 증명하였다.[3]
참고 문헌
- ↑ 가 나 다 라 윤영진 (2007). 《새로운 조합수학》. 교우사. ISBN 978-89-8172-379-8.
- ↑ Kőnig Dénes (1931). “Gráfok és mátrixok”. 《Matematikai és Fizikai Lapok》 38: 116–119.
- ↑ Hall, Philip (1935). “On representatives of subsets”. 《Journal of the London Mathematical Society》 10 (1): 26–30. doi:10.1112/jlms/s1-10.37.26.
바깥 고리
- “König theorem”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
- “Combinatorial analysis”. 《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.
- Weisstein, Eric Wolfgang. “Marriage theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research.