쾨니그 정리

최적설계 수치해석 마지막 수정: 2026-08-16 04:12:41

1. 개요[편집]

쾨니그 정리 Kőnig's Theorem
발표	Dénes Kőnig (1931) · Jenő Egerváry (1931, 가중 일반화)
진술	이분 그래프에서 $\nu(G)=\tau(G)$ (최대 매칭 = 최소 정점 덮개)
따름정리	최대 독립집합 $\alpha = n - \nu$
증명 도구	교대 경로 도달성 · 최대유량-최소절단 · LP 쌍대성
구성 비용	최대 매칭 이후 $O(E)$ 탐색 한 번
반례	삼각형 $K_3$ — $\nu=1,\ \tau=2$

쾨니그 정리(Kőnig’s theorem)는 이분 그래프에서 최대 매칭의 크기와 최소 정점 덮개의 크기가 언제나 같다는 최소-최대 정리다. 기호로 쓰면 이분 그래프 $G$ 에 대해

\nu(G) \;=\; \tau(G)

이며, 여기서 $\nu$ 는 서로 끝점을 공유하지 않는 간선의 최대 개수(매칭 수), $\tau$ 는 모든 간선이 적어도 하나는 닿도록 고른 정점 집합의 최소 크기(정점 덮개 수)다. 1931년 데네시 쾨니그가 발표했고, 같은 해 예뇌 에게르바리가 가중 버전으로 확장해 쾨니그-에게르바리 정리로도 불린다.¹

매칭과 덮개는 방향이 정반대인 문제다. 매칭은 최대화, 덮개는 최소화이고, 임의의 그래프에서 $\nu \le \tau$ 는 자명하다 — 매칭 간선 하나마다 서로 다른 정점을 최소 하나씩 덮개에 넣어야 하니까. 이 부등식이 이분 구조에서만 등식으로 붙는다는 것이 정리의 내용이고, 그 결과 “최댓값을 찾았다”는 사실을 증명하는 증명서(certificate)를 매번 손에 쥘 수 있게 된다. 매칭 자체의 알고리즘과 응용은 이분 매칭에 있으므로, 이 문서는 정리·증명·쌍대성에 집중한다.

2. 왜 최소-최대 정리가 중요한가[편집]

$\nu \le \tau$ 만 있으면 매칭 $M$ 과 덮개 $C$ 를 각각 아무렇게나 찾아 놓고 $|M| \le \nu \le \tau \le |C|$ 라고밖에 못 한다. 그런데 우연히 $|M| = |C|$ 인 쌍을 손에 넣으면 이 사슬이 통째로 붕괴하면서 양쪽 모두 최적임이 즉시 증명된다. 쾨니그 정리는 이런 쌍이 이분 그래프에서 항상 존재한다고 보장하고, 게다가 아래 증명은 그 쌍을 만드는 방법까지 준다.

이게 실무에서 갖는 의미는 크다. 반복 최적화에서 “더 못 줄이겠는데요”는 근거가 없지만, “여기 $26$ 개짜리 매칭과 $26$ 개짜리 덮개가 있습니다”는 반박 불가능한 근거다. 분지한정법이나 정수계획법 솔버가 하는 일도 결국 이 쌍을 좁히는 것이고, 이분 매칭은 그 간극이 처음부터 0인 몇 안 되는 문제다.

한편 여집합을 취하면 독립집합이 나온다. 임의의 그래프에서 정점 집합 $C$ 가 덮개인 것과 $V \setminus C$ 가 독립집합인 것은 동치이므로

\alpha(G) + \tau(G) = n

가 항상 성립한다(갈라이 항등식). 여기에 쾨니그를 얹으면 이분 그래프에서

\alpha(G) = n - \nu(G)

즉 일반 그래프에서 NP-난해인 최대 독립집합 문제가 이분 그래프에서는 매칭 한 번으로 끝난다. 같은 논리로 최소 정점 덮개도 다항시간이 된다. 이분성이라는 조건 하나가 복잡도 계급을 통째로 갈아 치우는 것.

3. 증명 — 덮개를 직접 만든다[편집]

존재성만 말하는 증명도 있지만, 쓸모 있는 것은 구성적 증명이다. $G=(X \cup Y, E)$ 에서 최대 매칭 $M$ 을 하나 구했다고 하자. 절차는 세 줄이다.

$U$ := $X$ 안의 미포화(unmatched) 정점 전체.
$Z$ := $U$ 에서 출발하는 교대 경로(미매칭 간선 → 매칭 간선 → …)로 도달 가능한 정점 전체.
$C := (X \setminus Z) \;\cup\; (Y \cap Z)$ .

이 $C$ 가 크기 $|M|$ 인 정점 덮개다. 확인해야 할 것은 두 가지.

$C$ 가 덮개다. 간선 $xy$ ( $x \in X$ , $y \in Y$ )가 덮이지 않는다면 $x \in Z$ 이면서 $y \notin Z$ 여야 한다. 그런데 $x \in Z$ 이면 $x$ 까지 교대 경로가 있고, 그 경로가 $x$ 에 매칭 간선으로 들어왔거나( $x$ 가 포화) $x \in U$ 거나 둘 중 하나다. 어느 쪽이든 $x$ 에서 미매칭 간선으로 한 걸음 더 나갈 수 있으므로, $xy$ 가 미매칭이면 $y \in Z$ 가 되어 모순이다. $xy$ 가 매칭 간선이라면 $x$ 는 $y$ 를 통해서만 포화될 수 있는데, 그러면 $x$ 로 들어온 매칭 간선이 곧 $xy$ 라 역시 $y \in Z$ 다. 모순.

$|C| = |M|$ 이다. $C$ 의 각 정점은 매칭 간선으로 포화되어 있고( $X \setminus Z$ 의 정점이 미포화면 $U$ 에 들어가 $Z$ 에 속했을 것이고, $Y \cap Z$ 의 정점이 미포화면 그 교대 경로가 곧 증대 경로라 $M$ 의 최대성에 어긋난다), 서로 다른 두 정점이 같은 매칭 간선을 쓰는 일도 없다 — 그러려면 매칭 간선 $xy$ 의 양 끝이 $x \in X\setminus Z$ , $y \in Y \cap Z$ 여야 하는데, $y \in Z$ 인 포화 정점에서는 매칭 간선을 타고 $x$ 로 갈 수 있으므로 $x \in Z$ 가 되어 모순이다. 따라서 $|C| \le |M|$ , 반대 방향은 자명하므로 등호.

핵심은 미포화 정점에서 증대 경로가 없다는 사실(베르주 정리)이 그대로 덮개의 존재로 번역된다는 점이다. 그래서 이 구성은 이분 매칭 알고리즘의 공짜 후처리다. 홉크로프트-카프가 $O(E\sqrt{V})$ 로 끝나고 나면, 마지막 실패한 BFS가 남긴 도달 집합이 이미 $Z$ 이므로 덮개를 뽑는 데 추가로 $O(E)$ 탐색 한 번이면 된다. 최소 덮개와 최대 독립집합을 요구하는 실무 코드는 예외 없이 이 경로를 탄다.

4. LP 쌍대성과 전체 단모듈성[편집]

같은 정리를 선형계획으로 읽으면 왜 하필 이분 그래프인지가 선명해진다. 간선 $e$ 마다 변수 $x_e$ , 정점 $v$ 마다 변수 $y_v$ 를 두고 접속행렬 $A$ 를 쓰면

\nu^*(G) = \max\{\mathbf{1}^{\mathsf T} x : Ax \le \mathbf{1},\ x \ge 0\}, \qquad \tau^*(G) = \min\{\mathbf{1}^{\mathsf T} y : A^{\mathsf T} y \ge \mathbf{1},\ y \ge 0\}

이 서로 쌍대 관계이므로 강쌍대성에 의해 $\nu^* = \tau^*$ 는 모든 그래프에서 성립한다. 문제는 정수해와의 간극이고, 언제나

\nu(G) \;\le\; \nu^*(G) = \tau^*(G) \;\le\; \tau(G)

가 성립한다. 이분 그래프에서는 접속행렬이 전체 단모듈이라 두 LP의 꼭짓점이 전부 정수점이 되고, 따라서 위 사슬 전체가 붕괴해 $\nu = \tau$ 가 나온다. 쾨니그 정리 = 접속행렬의 전체 단모듈성 + LP 강쌍대성인 셈이다.

이것이 정수성이 어디서 오는지도 알려준다. 접속행렬이 TU일 필요충분조건은 그래프에 홀수 사이클이 없는 것, 즉 이분성이다. 이분성이 깨지는 순간 완화해가 반정수(half-integral)로 튀는데, 삼각형 $K_3$ 에서 모든 $x_e = \tfrac12$ 를 두면 $\nu^* = \tfrac32$ 이고 모든 $y_v = \tfrac12$ 면 $\tau^* = \tfrac32$ 인 반면 $\nu = 1$ , $\tau = 2$ 다. 정확히 홀수 사이클 하나가 양쪽으로 $\tfrac12$ 씩 간극을 벌린다.

일반 그래프에서 이 간극을 메우려면 다면체에 홀수 집합 제약 $x(E[U]) \le (|U|-1)/2$ 를 추가해야 하고, 그게 에드먼즈의 매칭 다면체 정리이자 블로섬 알고리즘이 홀수 사이클을 수축해 가며 하는 일이다. 반면 정점 덮개 쪽은 회복되지 않는다 — 최소 정점 덮개는 일반 그래프에서 NP-난해이고, 최선의 근사비가 $2$ 언저리에 머물러 있다. 쾨니그 정리는 매칭이 쉬워지는 정리가 아니라 덮개가 쉬워지는 정리다.

$\nu = \tau$ 가 성립하는 그래프를 쾨니그-에게르바리 그래프라 부르는데, 이분 그래프가 그 부분집합이며 비이분 예도 존재한다. 이 성질 자체는 다항시간에 판정 가능하다는 것이 알려져 있다.²

5. 최소-최대 정리 가족[편집]

쾨니그 정리는 혼자 서 있지 않다. 조합 최적화의 고전 정리 몇 개는 사실상 서로 몇 줄 안에 유도되는 한 덩어리다.

최대유량-최소절단. 이분 그래프를 소스·싱크로 감싼 단위 용량 네트워크에서 유한 절단이 곧 정점 덮개이므로, 쾨니그는 네트워크 흐름 정리의 특수 사례다. 가장 짧은 증명 경로이기도 하다.
홀의 결혼정리. $X$ -포화 매칭의 존재 조건 $|N(S)| \ge |S|$ 는 쾨니그에서 두 줄로 나온다. $\tau < |X|$ 이면 덮개에서 빠진 $X$ 정점들이 홀 조건 위반 집합이 되기 때문. 역방향 유도도 가능해 두 정리는 동치다.
멩거 정리. 두 정점을 잇는 서로소 경로의 최대 개수 = 분리 집합의 최소 크기. 이분 그래프에 적용하면 그대로 쾨니그가 된다.
딜워스 정리. 유한 부분순서집합에서 최대 반사슬의 크기 = 사슬 덮개의 최소 개수. 원소 $v$ 를 $v_{\text{out}} \in X$ 와 $v_{\text{in}} \in Y$ 로 쪼개 비교 가능 쌍을 간선으로 놓은 이분 그래프에서, 사슬 덮개의 최소 개수 = $n$ − 최대 매칭이 되어 딜워스가 쾨니그의 따름정리로 나온다(펄커슨의 증명). 반대 방향 유도도 알려져 있다.

이 정리들이 전부 “어떤 최대화 문제의 답 = 어떤 최소화 문제의 답”이라는 같은 형태를 갖는다는 관찰이, 이후 전체 단모듈성·완전 그래프·다면체 조합론이라는 통합 이론으로 이어졌다. 조합 최적화 교과서가 이 정리들을 한 장에 몰아넣는 이유다.

6. 수치해석에서의 접점[편집]

정리 하나가 왜 수치 소프트웨어에 박혀 있는지는 희소행렬의 구조 해석을 보면 안다. 희소행렬 $A$ 의 행을 $X$ , 열을 $Y$ 로 두고 $a_{ij} \ne 0$ 인 자리를 간선으로 하는 이분 그래프를 만들면, 최대 매칭의 크기가 곧 구조적 계수(structural rank)다. 실제 계수의 상한이며, 수치값과 무관하게 희소 패턴만으로 계산된다.

여기서 쾨니그의 구성이 그대로 쓰인다. 미포화 정점에서의 교대 도달 집합 $Z$ 로 행과 열을 각각 세 덩어리로 가르면 덜마주-멘델존 분해(Dulmage–Mendelsohn decomposition)가 나오고, 이것이 행렬을 과소결정·정사각·과다결정 블록으로 쪼갠 뒤 블록 삼각 형태로 재배열해 준다. MATLAB의 dmperm, SuiteSparse의 관련 루틴이 하는 일이 정확히 이것이며, 실용적 결과는 다음과 같다.

구조적 특이성 조기 발견. 구조적 계수가 $n$ 보다 작으면 어떤 수치값을 넣어도 특이행렬이다. LU 분해를 돌리기 전에 알 수 있고, 부족분을 만드는 행·열 집합까지 바로 나온다.
블록 삼각화로 연산량 절감. 분해가 비자명하면 전체를 한 덩어리로 푸는 대신 대각 블록만 차례로 풀면 되므로, 큰 비대칭 문제에서 채움(fill-in)이 크게 줄어든다.
정적 피벗팅 전처리. 대각에 0이 아닌 원소를 앉히는 최대 대각 전치는 완전 매칭 찾기고, 여기에 가중을 얹으면 배정 문제(헝가리안 알고리즘)가 된다. MC64류 전처리의 뿌리.
미분대수방정식 구조 해석. 방정식과 미지수를 짝짓는 매칭이 실패하면 모델이 구조적으로 특이하다는 뜻이고, 컴파일러는 실패한 도달 집합을 그대로 사용자에게 던진다. 그 집합이 바로 홀의 결혼정리가 말하는 병목이다.

정리 하나가 “왜 이 모델은 안 풀리는가”에 대한 사람이 읽을 수 있는 답을 만들어 준다는 점에서, 쾨니그 정리는 순수 조합론 치고는 대단히 실무적인 물건이다.³

7. 관련 문서[편집]

쾨니그는 1916년에 이미 정규 이분 그래프의 1-인자분해와 “이분 그래프의 변 채색수는 최대 차수와 같다”는 정리를 냈고, 1931년 논문이 지금 말하는 최소-최대 정리다. 같은 해 에게르바리가 가중 일반화를 발표했고, 그 결과를 24년 뒤 쿤이 재발견해 알고리즘으로 만든 것이 헝가리안 알고리즘이다. 이름이 “헝가리안”인 이유가 이 두 헝가리 사람이다. ↩
쾨니그-에게르바리 그래프의 구조적 특징은 1979년경 데밍과 스테르불이 각각 정리했다. 이분성이 충분조건이지 필요조건은 아니라는 점만 기억하면 실무에서 헷갈릴 일은 없다. 어차피 대부분의 응용은 원래부터 이분이다. ↩
희소 솔버가 “structurally singular”라고 뱉으면 대개 모델링 실수다. 미지수 하나를 두 번 정의했거나, 방정식 하나를 빠뜨렸거나. 이때 솔버가 같이 뱉는 행·열 목록을 무시하고 격자부터 다시 짜는 사람이 의외로 많은데, 그 목록이 이미 범인을 지목하고 있다. ↩