쾨니그의 정리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 역사
- 3.1. 쾨니그-에게르바리 정리 (확장)
4. 증명
- 4.1. 구성적 증명
- 4.2. 선형 계획법 쌍대성을 이용한 증명
5. 관련 정리
6. 응용
- 6.1. 알고리즘
7. 완전 그래프와의 관계
8. 비이분 그래프
참조

1. 개요

쾨니그의 정리는 이분 그래프의 최대 매칭의 크기가 최소 정점 덮개의 크기와 같다는 정리이다. 이 정리는 쾨니그 데네시에 의해 1931년에 증명되었으며, 이분 그래프에서 최대 매칭에 있는 변의 수는 최소 정점 덮개에 있는 정점의 수와 같다. 쾨니그의 정리는 홀의 결혼 정리, 딜워스 정리와 동치이며, 최대 흐름 최소 절단 정리로부터 도출된다. 쾨니그의 정리는 구성적 증명과 선형 계획법 쌍대성을 이용하여 증명할 수 있으며, 최대 매칭을 찾는 알고리즘을 통해 이분 그래프에서 정점 덮개 문제를 효율적으로 해결하는 데 활용된다. 쾨니그의 정리는 이분 그래프의 여 그래프가 완전 그래프라는 명제와 동치이며, 쾨니그의 선 채색 정리와도 관련이 있다. 이분 그래프가 아닌 일반적인 그래프에서는 최소 정점 덮개가 최대 매칭보다 클 수 있으며, 최소 정점 덮개 문제는 NP-완전 문제이다.

더 읽어볼만한 페이지

조합적 집합론 - 딜워스의 정리
딜워스의 정리는 부분 순서 집합의 너비와 사슬 분할의 최소 크기 간의 관계를 설명하며, 유한한 너비를 갖는 부분 순서 집합은 너비와 같은 수의 사슬로 분할될 수 있다고 말한다.
조합적 집합론 - 반사슬
반사슬은 부분 순서 집합에서 임의의 두 원소가 비교 불가능한 원소들의 부분 집합으로, 딜워스 정리, 미르스키 정리, 슈페르너 정리 등과 연관되어 있으며, 사슬과 대비되는 개념으로 부분 순서 집합 분할 문제에서 중요한 역할을 하는 수학적 개념이다.
그래프 이론 정리 - 램지의 정리
램지의 정리는 주어진 조건을 만족하는 램지 수가 존재한다는 정리로, 그래프 이론으로 해석되며, 특정 크기의 동색 클릭이 존재함을 보장하고, 램지 이론의 시초로 여겨진다.
그래프 이론 정리 - 4색 정리
4색 정리는 평면을 나눈 영역을 인접한 영역과 다른 색으로 칠할 때 필요한 최소 색의 수가 4개라는 정리로, 그래프 이론을 통해 추상화되어 평면 그래프의 4-채색 가능성을 나타내며, 컴퓨터를 이용한 증명과 그에 대한 논란, 그리고 재증명이 이루어졌다.

쾨니그의 정리
그래프 이론
일반 정보
이름	쾨니그의 정리
분야	그래프 이론
설명	이분 그래프에서 최대 부합의 크기는 최소 정점 덮개의 크기와 같다.
명명 유래	데네시 쾨니그
내용
공식 명칭	이분 그래프에서 최대 부합의 크기는 최소 정점 덮개의 크기와 같다.
관련 개념	이분 그래프 최대 부합 최소 정점 덮개
중요성
응용 분야	다양한 조합 최적화 문제 해결에 활용됨.
의미	이분 그래프의 구조적 특성을 보여주는 중요한 정리.

2. 정의

최대 부합의 변(청색) 수는 최소 꼭짓점 덮개의 꼭짓점(적색) 수와 같다.

어떤 그래프

\Gamma

의 '''꼭짓점 덮개'''(vertex cover^영어)

C\subset V(\Gamma)

는 다음 조건을 만족시키는 집합이다.

모든 변 $e\in E(\Gamma)$ 에 대하여, $e$ 와 접하는 $c\in C$ 가 존재한다.

'''최소 꼭짓점 덮개'''는 크기가 최소인 꼭짓점 덮개이다.^[1]

그래프에서 '''매칭'''은 두 개 이상의 변이 공통된 끝점을 공유하지 않는 변 집합이며, 다른 매칭에 더 많은 변이 없는 경우 매칭은 '''최대'''이다.^[2]

'''쾨니그의 정리'''에 따르면, 이분 그래프

\Gamma

의 최대 부합

M\subset E(\Gamma)

및 최소 꼭짓점 덮개

C\subset V(\Gamma)

에 대하여, 다음이 성립한다.

:

|M|=|C|

정의상 모든 정점 덮개 집합은 모든 매칭 집합보다 적어도 크거나 같아야 한다(매칭의 모든 변에 대해 덮개에 적어도 하나의 정점이 필요하기 때문). 특히, 최소 정점 덮개 집합은 최대 매칭 집합보다 크거나 같다. 쾨니그의 정리는 모든 이분 그래프에서 최소 정점 덮개 집합과 최대 매칭 집합의 크기가 실제로 같다고 명시한다.^[3]

>어떤 이분 그래프에서, 최대 매칭에 있는 변의 수는 최소 정점 덮개에 있는 정점의 수와 같다.^[3]

위 그림에 표시된 이분 그래프는 14개의 정점을 가지고 있다. 6개의 변을 가진 매칭은 파란색으로 표시되어 있고, 6개의 정점을 가진 정점 덮개는 빨간색으로 표시되어 있다. 더 작은 정점 덮개는 존재할 수 없다. 왜냐하면 모든 정점 덮개는 각 매칭된 변(그리고 다른 모든 변)의 적어도 하나의 끝점을 포함해야 하기 때문이며, 따라서 이것이 최소 정점 덮개이기 때문이다. 마찬가지로, 더 큰 매칭은 존재할 수 없다. 왜냐하면 모든 매칭된 변은 정점 덮개에 적어도 하나의 끝점을 포함해야 하기 때문이며, 따라서 이것이 최대 매칭이기 때문이다. 쾨니그의 정리는 매칭과 덮개의 크기 사이의 등식(이 예에서 두 숫자는 모두 6)이 모든 이분 그래프에 더 일반적으로 적용된다고 명시한다.

3. 역사

헝가리의 수학자 쾨니그 데네시가 1931년에 증명하였다.^[12]^[13] 쾨니그의 정리는 쾨니그 데네시의 이름을 따서 명명되었다. 쾨니그는 1914년에 발표하고 1916년에 출판했는데, 모든 정규 이분 그래프는 완전 매칭을 가지며,^[8] 이분 그래프의 채색 지수는 최대 차수와 같다는 결과를 발표했다.^[9] 후자의 명제는 '''쾨니그의 선 채색 정리'''로 알려져 있다.

쾨니그는 이분 그래프의 매칭 연구에 대한 아이디어를 그의 아버지인 수학자 쾨니그 줄러에게서 얻었다고 한다. 헝가리어에서 쾨니그의 이름은 이중 급성 악센트를 갖지만, 그의 정리는 때때로 독일 문자로 움라우트와 함께 표기되기도 한다.

3. 1. 쾨니그-에게르바리 정리 (확장)

가중 그래프로 확장될 수 있는 쾨니그의 정리는 에게르바리 예뇌 (1931)가 연구하였다. 에게르바리는 각 변 ''e''에 음이 아닌 정수 가중치 ''w_e''가 부여된 그래프를 고려했다. 가중치 벡터는 '''w'''로 표기된다. '''w-'''매칭의 '''가중치'''는 매칭에 참여하는 변들의 가중치의 합이다. '''''w-'''정점 덮개''는 (각 정점이 여러 번 나타날 수 있다는 의미의) 정점들의 멀티셋으로, 각 변 ''e''는 최소한 ''w_e''개의 정점에 인접한다. 에게르바리의 정리는 다음과 같다:

모든 변 가중치 이분 그래프에서, 최대 '''w-'''매칭의 '''가중치'''는 '''w-'''정점 덮개에 있는 정점의 가장 작은 수와 같다.

분수 매칭의 최대 '''''w-'''가중치'''는 다음과 같은 선형 계획법(LP)으로 주어진다.

최대화 '''''w''''' ''·'' '''x'''

제약 조건: '''x''' ≥ '''0'''''_E''

__________ '''A'''_''G'' · '''x''' ''≤ '''1'''_V.''

그리고 분수 '''''w-'''정점 덮개'''에 있는 정점의 최소 수는 다음과 같은 쌍대 LP로 주어진다.

최소화 '''1'''_''V'' ''·'' '''y'''

제약 조건: '''y''' ≥ '''0'''''_V''

__________ '''A'''_''G''^T · '''y''' ≥ '''''w'''.''

쾨니그의 정리 증명에서와 같이, LP 쌍대성 정리는 최적 값이 같음을 의미하며 (모든 그래프에 대해), 그래프가 이분 그래프라는 사실은 이 프로그램들이 모든 값이 정수인 최적 해를 갖는다는 것을 의미한다.

그래프의 각 꼭짓점 ''v''가 음이 아닌 정수 가중치 ''b_v''를 갖는 그래프를 고려할 수 있다. 가중치 벡터는 '''b'''로 표시한다. 꼭짓점 덮개의 '''''b'''-가중치''는 덮개에 있는 모든 ''v''에 대한 ''b_v''의 합이다. '''''b'''-매칭''은 각 변에 음이 아닌 정수 가중치를 할당하여, 임의의 꼭짓점 ''v''에 인접한 변의 가중치 합이 최대 ''b_v''가 되도록 하는 것이다. 에게르바리 정리는 비슷한 논리를 사용하여 변 가중치 '''w'''와 꼭짓점 가중치 '''b'''를 모두 갖는 그래프로 확장할 수 있다:

어떤 변 가중치 꼭짓점 가중치 이분 그래프에서, 최대 '''w-'''가중치의 '''b'''-매칭은 '''w-'''꼭짓점 덮개에 있는 꼭짓점의 최소 '''b'''-가중치와 같다.

4. 증명

쾨니그의 정리는 어떤 이분 그래프에서 최대 매칭에 있는 변의 수와 최소 정점 덮개에 있는 정점의 수가 같다는 것을 의미한다.^[3]

쾨니그의 정리는 구성적 증명과 선형 계획법 쌍대성을 이용한 증명, 두 가지 방법으로 증명할 수 있다. 구성적 증명은 최대 매칭으로부터 최소 정점 덮개를 직접 구성하는 방법을 제시한다. 선형 계획법 쌍대성을 이용한 증명은 분수 매칭과 분수 정점 덮개 개념을 도입하고, 선형 계획법의 쌍대성을 이용하여 증명한다.

4. 1. 구성적 증명

다음은 최대 매칭으로부터 최소 정점 덮개를 구성하는 방법을 제공하는 증명이다. 이분 그래프

G=(V,E)

에서

A,B

를 정점 집합

V

의 두 부분이라고 하고,

M

을

G

의 최대 매칭이라고 가정한다.

최소 컷 $(S, T)$ in the flow network $G'_\infty$

G

에서 파생된 흐름 네트워크

G'_\infty

를 구성한다. 이때, 소스

s

에서 모든 정점

a \in A

로, 그리고 모든 정점

b \in B

에서 싱크

t

로 용량

1

의 간선이 있고, 모든

(a, b) \in E

에 대해

a

에서

b

로 용량

+\infty

의 간선이 있다.

G

에서 최대 매칭의 크기

|M|

은

G'_\infty

에서 최대 흐름의 크기이며, 이는 최대 흐름 최소 컷 정리에 따라 네트워크

G'_\infty

의 최소 컷의 크기와 같다.

(S, T)

를 최소 컷이라고 하자.

A = A_S \cup A_T

및

B = B_S \cup B_T

이고,

A_S, B_S \subset S

및

A_T, B_T \subset T

라고 하자. 그러면 최소 컷은

s

에서

A_T

로 또는

B_S

에서

t

로 가는 간선으로만 구성되는데,

A_S

에서

B_T

로 가는 간선은 컷의 크기를 무한대로 만들기 때문이다.

따라서 최소 컷의 크기는

|A_T|+|B_S|

와 같다. 한편,

A_T \cup B_S

는 정점 덮개인데,

A_T

와

B_S

의 정점에 인접하지 않은 모든 간선은

A_S

와

B_T

의 정점 쌍에 인접해야 하며, 이는

A_S

와

B_T

사이에 간선이 없다는 사실과 모순되기 때문이다.

결과적으로,

A_T \cup B_S

는

G

의 최소 정점 덮개이다.^[4]

정점 덮개에 있는 어떤 정점도

M

의 둘 이상의 변을 덮을 수 없다(변의 절반 겹침은

M

이 애초에 매칭이 되는 것을 방지하기 때문이다). 따라서

|M|

개의 정점을 가진 정점 덮개를 구성할 수 있다면, 그것은 최소 덮개여야 한다.^[4]

이러한 덮개를 구성하기 위해,

U

를

A

에서 매칭되지 않은 정점의 집합(비어 있을 수도 있음)이라고 하고,

Z

를

U

에 있거나 교대 경로(매칭에 있는 변과 매칭에 없는 변을 번갈아 가는 경로)로

U

에 연결된 정점의 집합이라고 하자. 다음을 정의한다.

:

K=(A\setminus Z)\cup (B\cap Z).

E

에 있는 모든 변

e

는 교대 경로에 속하거나(오른쪽 끝점이

K

에 있음), 왼쪽 끝점이

K

에 속한다. 그 이유는 다음과 같다. 만약

e

가 매칭되었지만 교대 경로에 속하지 않는다면, 왼쪽 끝점은 교대 경로에 속할 수 없다(두 개의 매칭된 변은 정점을 공유할 수 없기 때문에). 따라서

A\setminus Z

에 속한다. 또는

e

가 매칭되지 않았지만 교대 경로에 속하지 않는다면, 왼쪽 끝점은 교대 경로에 속할 수 없다. 왜냐하면 그러한 경로는

e

를 추가하여 확장될 수 있기 때문이다. 따라서

K

는 정점 덮개를 형성한다.^[5]

또한

K

의 모든 정점은 매칭된 변의 끝점이다. 그 이유는 다음과 같다.

A\setminus Z

의 모든 정점은 매칭되는데,

Z

는 매칭되지 않은 왼쪽 정점의 집합인

U

의 상위 집합이기 때문이다. 그리고

B\cap Z

의 모든 정점도 매칭되어야 한다. 왜냐하면 매칭되지 않은 정점으로 가는 교대 경로가 있다면, 이 경로에서 매칭된 변을 제거하고 그 자리에 매칭되지 않은 변을 추가하여 매칭을 변경하면 매칭의 크기가 증가하기 때문이다. 그러나, 매칭된 변은 두 개의 끝점이 모두

K

에 있을 수 없다. 따라서

K

는

M

과 동일한 기수를 가진 정점 덮개이며, 최소 정점 덮개여야 한다.^[5]

4. 2. 선형 계획법 쌍대성을 이용한 증명

이 증명을 설명하기 위해 먼저 분수 매칭의 개념을 확장해야 한다. 분수 매칭은 각 모서리에 [0,1] 범위의 가중치를 할당하여 각 정점 근처의 가중치 합이 최대 1이 되도록 하는 것이다(정수 매칭은 가중치가 {0,1}인 분수 매칭의 특수한 경우이다). 유사하게, 분수 정점 커버를 정의한다. 분수 정점 커버는 각 정점에 음이 아닌 가중치를 할당하여 각 모서리의 가중치 합이 1 이상이 되도록 하는 것이다(정수 정점 커버는 가중치가 {0,1}인 분수 정점 커버의 특수한 경우이다).

그래프

G=(V,E)

에서 최대 분수 매칭 크기는 다음 선형 계획법의 해이다.

> 최대화 '''1'''_''E'' ''·'' '''x'''

>

> 제약 조건: '''x''' ≥ '''0'''''_E''

>

> __________ '''A'''_''G'' · '''x''' ''≤ '''1'''_V.''

여기서 '''x'''는 각 요소가 분수 매칭의 모서리의 가중치를 나타내는 크기 |''E''|의 벡터이다. '''1'''_E는 |''E''|개의 1로 구성된 벡터이므로 첫 번째 줄은 매칭의 크기를 나타낸다. '''0'''''_E''는 |''E''|개의 0으로 구성된 벡터이므로 두 번째 줄은 가중치가 음이 아니어야 한다는 제약 조건을 나타낸다. '''1'''_V는 |''V''|개의 1로 구성된 벡터이고 '''A'''_''G''는 ''G''의 사건 행렬이므로 세 번째 줄은 각 정점 근처의 가중치 합이 최대 1이 되어야 한다는 제약 조건을 나타낸다.

마찬가지로,

G=(V,E)

에서 최소 분수 정점 커버 크기는 다음 LP의 해이다.

> 최소화 '''1'''_''V'' ''·'' '''y'''

>

> 제약 조건: '''y''' ≥ '''0'''''_V''

>

> __________ '''A'''_''G''^T · '''y''' ≥ '''''1'''_E.''

여기서 '''y'''는 각 요소가 분수 커버의 정점의 가중치를 나타내는 크기 |V|의 벡터이다. 여기서 첫 번째 줄은 커버의 크기이고, 두 번째 줄은 가중치의 비음수성을 나타내며, 세 번째 줄은 각 모서리 근처의 가중치 합이 1 이상이어야 한다는 요구 사항을 나타낸다.

이제 최소 분수 커버 LP는 최대 분수 매칭 LP의 정확한 쌍대 선형 계획법이다. 따라서 LP 쌍대성 정리에 의해 두 프로그램은 동일한 해를 갖는다. 이 사실은 이분 그래프뿐만 아니라 임의의 그래프에서도 참이다.

> ''어떤 그래프에서든 분수 매칭의 최대 크기는 분수 정점 커버의 최소 크기와 같다.''

이분 그래프를 특별하게 만드는 것은 이분 그래프에서 이러한 선형 프로그램 모두 모든 변수 값이 정수인 최적의 해를 갖는다는 것이다. 이는 이분 그래프의 매칭 다면체에서 모든 극점이 정수 좌표만 가지며, 분수 정점 커버 다면체에도 동일하게 적용된다는 사실에서 비롯된다. 따라서 위의 정리는 다음을 의미한다.

> ''어떤 이분 그래프에서든 매칭의 최대 크기는 정점 커버의 최소 크기와 같다.''

Egerváry (1931)는 각 변 ''e''에 음이 아닌 정수 가중치 ''w_e''가 부여된 그래프를 고려했다. 가중치 벡터는 '''w'''로 표기된다. '''w-'''매칭의 '''가중치'''는 매칭에 참여하는 변들의 가중치의 합이다. '''''w-'''정점 덮개''는 (각 정점이 여러 번 나타날 수 있다는 의미의) 정점들의 멀티셋으로, 각 변 ''e''는 최소한 ''w_e''개의 정점에 인접한다. Egerváry의 정리는 다음과 같다.

>모든 변 가중치 이분 그래프에서, 최대 '''w-'''매칭의 '''가중치'''는 '''w-'''정점 덮개에 있는 정점의 가장 작은 수와 같다.

분수 매칭의 최대 '''''w-'''가중치'''는 다음과 같은 선형 계획법(LP)으로 주어진다.

>최대화 '''''w''''' ''·'' '''x'''

>

>제약 조건: '''x''' ≥ '''0'''''_E''

>

>__________ '''A'''_''G'' · '''x''' ''≤ '''1'''_V.''

그리고 분수 '''''w-'''정점 덮개'''에 있는 정점의 최소 수는 다음과 같은 쌍대 LP로 주어진다.

>최소화 '''1'''_''V'' ''·'' '''y'''

>

>제약 조건: '''y''' ≥ '''0'''''_V''

>

>__________ '''A'''_''G''^T · '''y''' ≥ '''''w'''.''

쾨니그의 정리의 증명에서와 마찬가지로, LP 쌍대성 정리는 최적 값이 같음을 의미하며 (모든 그래프에 대해), 그래프가 이분 그래프라는 사실은 이 프로그램들이 모든 값이 정수인 최적 해를 갖는다는 것을 의미한다.

5. 관련 정리

쾨니그의 정리는 이분 그래프에서 최대 부합과 최소 정점 덮개의 크기가 같다는 것을 보여준다.^[3]

쾨니그의 정리는 홀의 결혼 정리, 딜워스 정리와 동치이며, 최대 흐름 문제의 특수한 경우인 이분 매칭을 통해 최대 흐름 최소 절단 정리로부터 도출될 수 있다.^[3]

6. 응용

쾨니그의 정리에 따르면, 이분 그래프 $\Gamma$ 의 최대 부합 $M\subset E(\Gamma)$ 과 최소 꼭짓점 덮개 $C\subset V(\Gamma)$ 에 대하여, $|M|=|C|$ 가 성립한다. 여기서 꼭짓점 덮개는 모든 변이 덮개의 한 점과 접하는 꼭짓점의 집합을 의미하며, 최소 꼭짓점 덮개는 크기가 최소인 꼭짓점 덮개이다.

이 정리는 홀 결혼 정리 및 딜워스의 정리와 동치이다.

6. 1. 알고리즘

위 그림의 이분 그래프는 14개의 정점으로 구성되어 있다. 파란색 선은 6개의 변을 가진 매칭을 나타내고, 빨간색 점은 6개의 정점을 가진 정점 덮개를 나타낸다. 모든 정점 덮개는 각 매칭된 변의 적어도 한쪽 끝점을 포함해야 하므로, 빨간색 정점 덮개보다 더 작은 정점 덮개는 존재할 수 없다. 따라서 이는 최소 정점 덮개이다. 마찬가지로, 모든 매칭된 변은 정점 덮개의 적어도 한쪽 끝점을 포함해야 하므로, 파란색 매칭보다 더 큰 매칭은 존재할 수 없다. 따라서 이는 최대 매칭이다. 쾨니그의 정리는 이처럼 매칭과 덮개의 크기가 같다는 사실(이 예시에서는 둘 다 6)이 모든 이분 그래프에서 일반적으로 성립함을 보여준다.^[4]

정점 덮개에 속하는 어떤 정점도

M

의 두 개 이상의 변을 덮을 수 없다. 이는 변들이 서로 겹치지 않아야

M

이 매칭이 될 수 있기 때문이다. 따라서

|M|

개의 정점을 가진 정점 덮개를 만들 수 있다면, 그것은 최소 덮개여야 한다.^[4]

최소 덮개를 구성하는 방법은 다음과 같다. 먼저,

A

에서 매칭되지 않은 정점들의 집합을

U

라고 하자(비어 있을 수도 있다). 그리고

U

에 속하거나,

U

에서 시작하는 교대 경로(매칭에 속하는 변과 속하지 않는 변을 번갈아 지나는 경로)로 연결되는 정점들의 집합을

Z

라고 하자. 마지막으로, 다음 집합을 정의한다.

:

K=(A\setminus Z)\cup (B\cap Z).

E

에 속하는 모든 변

e

는 교대 경로에 속하거나(이 경우 오른쪽 끝점이

K

에 속함), 왼쪽 끝점이

K

에 속한다. 만약

e

가 매칭되었지만 교대 경로에 속하지 않는다면, 그 왼쪽 끝점은 교대 경로에 속할 수 없으므로(

A\setminus Z

에 속함)

K

에 속한다. 만약

e

가 매칭되지 않았지만 교대 경로에 속하지 않는다면, 그 왼쪽 끝점은 교대 경로에 속할 수 없으므로(

e

를 추가하여 경로를 확장 가능) 역시

K

에 속한다. 따라서

K

는 정점 덮개를 이룬다.^[5]

또한,

K

의 모든 정점은 매칭된 변의 끝점이다.

A\setminus Z

의 모든 정점은 매칭되어 있는데,

Z

가 매칭되지 않은 왼쪽 정점들의 집합

U

를 포함하기 때문이다.

B\cap Z

의 모든 정점도 매칭되어 있어야 한다. 만약 매칭되지 않은 정점으로 가는 교대 경로가 있다면, 이 경로에서 매칭된 변을 제거하고 매칭되지 않은 변을 추가하면 매칭의 크기가 커지기 때문이다. 그러나 매칭된 변은 양쪽 끝점이 모두

K

에 있을 수 없다. 따라서

K

는

M

과 같은 크기를 가진 정점 덮개이며, 최소 정점 덮개이다.^[5]

위에서 설명한 구성적 증명은 최대 매칭이 주어졌을 때 최소 정점 덮개를 찾는 알고리즘을 제공한다. 따라서 이분 그래프에서 최대 매칭을 찾는 홉크로프트-카프 알고리즘을 사용하면, 이러한 그래프에서 정점 덮개 문제도 효율적으로 해결할 수 있다.^[6]

두 문제(최대 매칭, 최소 정점 덮개)는 정확한 해를 구하는 관점에서는 동일하지만, 근사 알고리즘의 관점에서는 다르다. 이분 최대 매칭은 분산 알고리즘을 통해 상수 시간 내에 임의로 정확하게 근사할 수 있지만, 이분 그래프의 최소 정점 덮개를 근사하려면 최소 대수 시간이 필요하다.Göös|Suomela|2014^영어

서론의 그래프에서 아래쪽 정점들을

L

, 위쪽 정점들을

R

이라고 하자. 왼쪽에서 오른쪽으로, 아래쪽 정점들에 1부터 7까지, 위쪽 정점들에 8부터 14까지 번호를 매긴다.

L

에서 매칭되지 않은 정점 집합

U

는 {1}이다.

U

에서 시작하는 교대 경로는 1–10–3–13–7, 1–10–3–11–5–13–7, 1–11–5–13–7, 1–11–5–10–3–13–7이며, 이 경로들의 1에서 시작하는 모든 부분 경로도 포함한다. 따라서

Z

는 {1,3,5,7,10,11,13}이다. 결과적으로

L\setminus Z=\{2,4,6\}

,

R\cap Z=\{10,11,13\}

이므로, 최소 정점 덮개

K=\{2,4,6,10,11,13\}

을 얻는다.

7. 완전 그래프와의 관계

그래프에서 매칭은 서로 공통된 끝점을 공유하지 않는 변들의 집합이며, 다른 매칭에 더 많은 변이 없는 경우 최대 매칭이라고 한다.^[2] 최소 정점 덮개 집합은 최대 매칭 집합보다 크거나 같은데, 쾨니그의 정리에 따르면 모든 이분 그래프에서 최소 정점 덮개 집합과 최대 매칭 집합의 크기는 실제로 같다.^[3]

모든 유도된 부분 그래프에서 채색수가 가장 큰 클리크의 크기와 같으면 완전 그래프라고 한다. 모든 이분 그래프는 완전 그래프인데,^[10] 각 부분 그래프가 이분 그래프이거나 독립 집합이기 때문이다. 독립 집합이 아닌 이분 그래프와 독립 집합에서 채색수와 가장 큰 클리크의 크기는 각각 2와 1이다.

쾨니그의 정리는 이분 그래프의 여 그래프가 완전 그래프라는 명제와 동치이다. 이분 그래프의 여 그래프의 채색에서 각 색상 클래스는 크기가 최대 2이며 크기가 2인 클래스는 매칭을 형성하는데, 이는 그래프 ''G''의 여 그래프에서 클리크이다. 그래프 ''G''의 독립 집합은 ''G''의 정점 덮개의 여집합이다. 따라서 ''n''개의 정점을 가진 이분 그래프 ''G''의 매칭 ''M''은 ''n''-|''M''|개의 색으로 ''G''의 여 그래프를 채색하는 것과 대응하며, 이는 ''n''-|''M''|개의 정점을 가진 ''G''의 독립 집합, ''M''개의 정점을 가진 ''G''의 정점 덮개에 대응한다.

쾨니그의 선 채색 정리는 이분 그래프의 선 그래프와 연결할 수 있다. ''G''가 이분 그래프인 경우, ''L''(''G'')의 클리크는 ''G''에서 공통 끝점을 공유하는 변들의 집합이다. 쾨니그의 선 채색 정리는 이분 그래프의 선 그래프가 완전 그래프라고 말하는 것으로 해석할 수 있다.

8. 비이분 그래프

이분 그래프가 아닌 그래프의 경우, 최소 정점 덮개는 최대 매칭보다 클 수 있다. 또한, 두 문제는 복잡성 면에서 매우 다르다. 최대 매칭은 모든 그래프에 대해 다항 시간 안에 찾을 수 있는 반면, 최소 정점 덮개는 NP-완전 문제이다.

모든 그래프에서 정점 덮개의 여집합은 독립 집합이므로, 최소 정점 덮개는 최대 독립 집합과 상호 보완적이다. 최대 독립 집합을 찾는 것은 또 다른 NP-완전 문제이다. 쾨니그의 정리에 명시된 매칭과 덮개 사이의 등가성은 이러한 문제가 더 일반적인 그래프 집합에 대해서는 NP-완전임에도 불구하고, 이분 그래프의 경우 최소 정점 덮개와 최대 독립 집합을 다항 시간 안에 계산할 수 있게 해준다.^[7]

참조

_[1] 문헌
_[2] 문헌
_[3] 문헌
_[4] 문헌
_[5] 문헌
_[6] 문헌
_[7] 문헌
_[8] 기타
_[9] 문헌
_[10] 문헌
_[11] 문헌
_[12] 저널 Gráfok és mátrixok 1931
_[13] 서적 새로운 조합수학 http://www.kyowoo.co[...] 교우사 2007

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com