쾨니그의 정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

쾨니그의 정리(헝가리어: Kőnig-tétel, Kőnig's theorem, -定理) 또는 홀의 정리(Hall's theorem)는 그래프 이론조합적 집합론의 기본적이며 중요한 정리로, 헝가리의 수학자 쾨니그 데네시(Kőnig Dénes)가 1931년 처음 제시하였다.[1] 이 정리는 어떤 집합의 적당한 부분집합들이 이루는 집합이 변별 대표원계를 가질 필요충분조건을 제시하고 있다. 그 내용 때문에 이 정리는 결혼정리(結婚定理)라고 불리기도 한다.[1]

그래프 이론[편집]

최대 매칭의 변(청색) 수는 최소 꼭지점 덮개의 꼭지점(적색) 수와 같다.

쾨니그가 1931년 제시한 정리는 원래 그래프 이론에서의 용어를 사용한 다음과 같은 형태였다.

이 정리는 나중에 영국필립 홀(Philip Hall)에 의해 1935년 다음과 같은 더 일반적인 집합론적 형태로 표현되었다. 두 표현은 동치이며, 이들은 딜워스의 정리와도 동치이다.

집합론[편집]

변별 대표원계[편집]

이 정리의 집합론적 공식화를 서술하기 전에 먼저 변별 대표원계(system of distinct representatives, 辨別代表元系)의 개념을 설명할 필요가 있다. 어떤 집합 S가 있고, 그 부분집합 A_1, A_2, .., A_m 이 이루는 집합족 T가 있다고 하자. 그러면 T에 대해 어떤 집합 s가 변별 대표원계라는 것은 다음과 같이 정의된다.[1]

  • S의 서로 다른 원소 a_1, a_2, .., a_ra_i \in A_i (i = 1, 2, .., r) 일 때, T의 원소를 정의역으로 하고 S를 공역으로 하며 s(A_i) = a_i 를 만족하는 함수 s를 T에 대한 변별 대표원계라 한다.

집합 S에서 얻을 수 있는 집합족 T는 변별 대표원계를 가질 수도, 가지지 않을 수도 있다. 또 변별 대표원계를 갖는 경우 유일하지 않을 수도 있다. 여기서 T가 변별 대표원계를 가지는 필요충분조건이 바로 이하의 정리로 주어지는 것이다.

이 변별 대표원계의 개념에서 왜 이 정리가 결혼정리로 불리는지를 알 수 있다. r명의 남자(혹은 r명의 여자)가 결혼했으면 하는 여자(혹은 남자)의 표를 만들 때, 각 사람이 자기 표에 있는 이성과 결혼하는 것이 가능할 필요충분조건은 그 표가 변별 대표원계를 갖는 것이기 때문이다.[1]

공식화[편집]

이 꼴의 쾨니그의 정리는 다음과 같이 공식화할 수 있다.[1] 일반적으로 이는 '홀의 정리'로 불린다.

  • 앞에서와 같이 정의된 S, T에 대하여 T가 변별 대표원계를 가질 필요충분조건은 각각의 r≤m에 대해 r개 A_i합집합이 적어도 r개의 원소를 가지는 것이다.

여기서 →의 방향은 변별 대표원계의 정의에 따라 자명하므로, 홀의 정리에서 실제로 증명할 것은 ←의 방향이다.

주석[편집]

  1. 윤영진, 《새로운 조합수학》, 교우사, 2007, 289쪽.
  2. 어떤 그래프에서 꼭지점의 집합으로서 그 그래프에 속하는 모든 변이 그 집합에 속하는 하나 이상의 원소와 접하는 경우 그 집합을 꼭지점 덮개(vertex cover)라 한다. 최소 꼭지점 덮개(minimum vertex cover)는 가장 원소의 수가 적은 꼭지점 덮개를 말한다.

참고 문헌[편집]

  • 윤영진, 《새로운 조합수학》, 교우사, 2007