홀의 결혼정리

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

1. 개요[편집]

홀의 결혼정리 Hall's Marriage Theorem
발표	Philip Hall (1935), "On Representatives of Subsets"
조건	$\|N(S)\| \ge \|S\|$ for all $S \subseteq X$ (홀 조건)
결론	$X$-포화 매칭이 존재
결함형	$\nu = \|X\| - \max_S (\|S\| - \|N(S)\|)$ (Ore, 1955)
동치 정리	쾨니그 정리 · 멩거 정리 · 최대유량-최소절단
검사 비용	부분집합은 $2^{\|X\|}$개지만 판정은 매칭 한 번

홀의 결혼정리(Hall’s marriage theorem)는 이분 그래프 $G = (X \cup Y, E)$ 에서 $X$ 의 모든 정점을 짝지어 주는 매칭이 존재할 필요충분조건이 “ $X$ 의 어떤 부분집합 $S$ 를 잡아도 그 이웃 집합이 $S$ 보다 작지 않은 것”이라는 정리다.

X\text{-포화 매칭이 존재} \iff |N(S)| \ge |S| \quad \forall\, S \subseteq X

여기서 $N(S) = \{\,y \in Y : \exists\, x \in S,\ xy \in E\,\}$ 다. 필립 홀이 1935년 논문에서 “집합족의 서로 다른 대표원”을 다루며 증명했고, 필요조건 쪽은 세 줄이면 끝난다 — $S$ 의 정점들은 서로 다른 짝을 $N(S)$ 안에서 골라야 하므로 $|N(S)| < |S|$ 면 비둘기집 원리로 끝. 정리의 내용은 이 뻔한 필요조건이 충분조건이기도 하다는 것이다.

이름이 “결혼정리”인 것은 원래 서술이 “각 남성이 아는 여성들의 명단이 주어졌을 때 모두를 서로 아는 사람끼리 결혼시킬 수 있는가”였기 때문이다. 부제까지 붙여 홀의 정리를 소개하는 교과서가 많지만, 뒤에서 볼 안정 결혼 문제와는 완전히 다른 문제라는 점을 먼저 못 박아 둔다. 매칭 알고리즘 일반은 이분 매칭, 쌍대 정리는 쾨니그 정리 참고.

2. 두 개의 증명[편집]

귀납법. $|X|$ 에 대한 귀납이다. 부분집합의 여유를 $|N(S)| - |S|$ 라 부르고 두 경우로 나눈다.

여유가 넉넉한 경우: 공집합도 $X$ 전체도 아닌 모든 $S$ 가 $|N(S)| \ge |S| + 1$ 을 만족하면, $X$ 에서 아무 정점 $x$ 와 그 이웃 $y$ 를 골라 짝지어 버린다. $x, y$ 를 지운 그래프에서 임의의 $S$ 는 이웃을 최대 하나( $y$ ) 잃으므로 홀 조건이 살아남고, 귀납 가설이 나머지를 처리한다.
꽉 끼는 집합이 있는 경우: 어떤 진부분집합 $S \ne \emptyset$ 이 $|N(S)| = |S|$ 를 만족하면, $S$ 와 $N(S)$ 만 떼어 귀납 가설로 완전히 짝지운다. 남은 쪽 $X \setminus S$ 와 $Y \setminus N(S)$ 에서도 홀 조건이 성립하는데, 임의의 $T \subseteq X\setminus S$ 에 대해 $|N(S \cup T)| \ge |S| + |T|$ 이고 $N(S)$ 가 이미 $|S|$ 개를 차지하므로 $T$ 가 새로 쓸 수 있는 이웃이 $|T|$ 개 이상 남기 때문이다.

교대 경로. 이쪽이 알고리즘과 직결된다. 최대 매칭 $M$ 이 $X$ 를 포화시키지 못한다고 하자. 미포화 정점 $x_0 \in X$ 에서 출발하는 교대 경로(미매칭 → 매칭 → …)로 도달 가능한 정점 집합을 $Z$ 라 두고 $S := Z \cap X$ 로 잡는다. 그러면

$N(S) = Z \cap Y$ 다. $S$ 에서 나가는 미매칭 간선은 전부 $Z$ 안으로 들어가니까.
$Z \cap Y$ 의 정점은 전부 포화되어 있다. 미포화 정점이 하나라도 있으면 그 교대 경로가 곧 증대 경로이고, 이분 매칭의 베르주 정리에 의해 $M$ 이 최대가 아니게 된다.
$Z \cap Y$ 의 매칭 짝은 전부 $S$ 안에 있고, $S$ 에서 그렇게 짝지어지지 않은 정점은 $x_0$ 하나뿐이다.

따라서 $|N(S)| = |S| - 1$ . 즉 매칭이 실패하면 홀 조건을 위반하는 집합이 자동으로 손에 들어온다. 대우를 취하면 정리 그대로다. 이 증명이 귀납 증명보다 값진 이유는 결론이 “존재한다”가 아니라 **“여기 있다”**이기 때문이다.

3. 결함형 — 얼마나 부족한가[편집]

위 논증을 미포화 정점 하나가 아니라 전부에 대해 돌리면 정량적 버전이 나온다. 결함(deficiency)을 $\mathrm{def}(S) = |S| - |N(S)|$ 로 정의할 때

\nu(G) \;=\; |X| \;-\; \max_{S \subseteq X} \bigl(|S| - |N(S)|\bigr)

이며, 우변의 최댓값은 $S = \emptyset$ 덕에 항상 0 이상이다. 오레(Ore, 1955)의 결함형 홀 정리다. 홀 정리는 최댓값이 0인 특수 사례일 뿐이다.

이 식이 말하는 바는 강하다. 매칭을 방해하는 원인은 언제나 “후보가 모자라는 집합” 하나로 요약된다. 배정이 $k$ 개 모자란다면 정확히 $k$ 만큼 결함이 있는 부분집합이 존재하고, 그것 말고 다른 종류의 병목은 없다. 그리고 그 $S$ 는 최대 매칭 이후 미포화 $X$ -정점 전체에서 교대 도달 집합을 한 번 계산하면 그대로 나온다.

여기서 계산 복잡도의 반전이 재미있다. 홀 조건은 부분집합 $2^{|X|}$ 개를 전부 확인해야 하는 것처럼 생겼지만, 실제로는 최대 매칭 한 번( $O(E\sqrt V)$ )으로 판정이 끝나고 위반 집합까지 나온다. 조건이 지수개인데 판정이 다항시간인 것은 선형계획법에서 분리 문제가 다항시간이면 최적화도 다항시간이라는 원리의 조합론적 원형이라 볼 수 있다.

4. 홀 위반자를 뱉는 소프트웨어[편집]

이 “위반 증명서”가 실무에서 갖는 값어치가 정리의 진짜 배당금이다. 배정이 불가능하다는 통보는 아무 정보가 없지만, $|S| = 7$ 인데 $|N(S)| = 5$ 라는 구체적 집합은 곧바로 조치로 이어진다.

미분대수방정식·모델링 언어. 방정식을 $X$ , 미지수를 $Y$ 로 두고 “이 방정식에 이 미지수가 등장한다”를 간선으로 하면, 모델이 잘 세워졌다는 것은 완전 매칭의 존재와 같다. Modelica 계열 컴파일러가 판텔리데스 알고리즘으로 지표 축소를 할 때 정확히 이 매칭을 돌리고, 실패하면 구조적으로 특이한 방정식 집합을 사용자에게 던진다. 그 집합이 홀 위반자다. “미지수를 하나 빠뜨렸거나 같은 관계를 두 번 썼다”는 진단이 여기서 나온다.
희소행렬의 구조적 계수. 0이 아닌 자리만 보고 만든 이분 그래프의 최대 매칭이 구조적 계수이고, 결함형 홀 정리가 곧 “어떤 행 집합이 열을 충분히 못 건드리는가”를 준다. 덜마주-멘델존 분해가 이 정보를 블록 삼각 형태로 정리한다(쾨니그 정리 참고).
자원 배정·시간표. 강의를 강의실에 배정하지 못했다면 결함 집합이 “이 세 과목이 요구하는 조건을 만족하는 강의실이 두 개뿐”이라고 알려 준다. 요구 조건을 완화하거나 자원을 늘리거나, 손댈 지점이 특정된다.

정리 하나가 오류 메시지의 품질을 결정한다는 것이 흔한 일은 아니다.¹

5. 정규 이분 그래프와 라틴 방진[편집]

홀 조건이 공짜로 성립하는 대표적 구조가 정규 그래프다. $k$ -정규 이분 그래프( $k \ge 1$ , 모든 정점의 차수가 $k$ )에서 $S \subseteq X$ 를 잡으면 $S$ 에서 나가는 간선이 정확히 $k|S|$ 개이고 이들은 전부 $N(S)$ 에 꽂히는데, $N(S)$ 가 받을 수 있는 간선은 $k|N(S)|$ 개다. 따라서 $k|S| \le k|N(S)|$ , 즉 $|S| \le |N(S)|$ . 모든 정규 이분 그래프는 완전 매칭을 갖는다.

여기에 귀납을 얹으면 더 강한 결과가 나온다. 완전 매칭 하나를 떼어 내면 $(k-1)$ -정규 이분 그래프가 남으므로, $k$ -정규 이분 그래프의 간선 집합은 $k$ 개의 완전 매칭으로 분해된다(1-인자분해). 이것이 이분 그래프의 변 채색수가 최대 차수와 같다는 쾨니그의 1916년 정리이고, 실무적으로는 “리그 경기 일정을 라운드로 쪼개기”, “스위치 포트 스케줄링을 시분할 슬롯으로 쪼개기”가 전부 이 분해다.

라틴 방진 완성도 같은 논증의 응용이다. $n$ 개의 기호로 채운 $k \times n$ 라틴 직사각형( $k < n$ , 각 행과 각 열에 기호 중복 없음)이 주어졌을 때, 열을 $X$ ·기호를 $Y$ 로 두고 “이 열에 이 기호가 아직 안 쓰였다”를 간선으로 하면 각 열은 $n-k$ 개의 기호를 남기고 각 기호는 $n-k$ 개의 열에서 빠져 있으므로 $(n-k)$ -정규 이분 그래프가 된다. 완전 매칭이 다음 한 행이 되고, 이를 반복하면

임의의 $k \times n$ 라틴 직사각형은 $n \times n$ 라틴 방진으로 확장된다.

가 나온다. 부분적으로 채워진 배열을 이어 붙일 수 있느냐는 문제가 매칭 하나로 결정된다는 점에서, 실험계획법에서 라틴 방진 배치를 쓸 때의 존재성 근거가 여기 있다.

6. 시스템 대표원과 행렬 형태[편집]

홀의 원 논문 서술은 그래프가 아니라 집합족이었다. 유한 집합족 $A_1, \dots, A_m$ 에 대해 서로 다른 원소 $a_1 \in A_1, \dots, a_m \in A_m$ 을 고를 수 있는가 — 이런 $\{a_i\}$ 를 서로 다른 대표원의 계(system of distinct representatives, SDR)라 한다. 집합을 $X$ , 원소를 $Y$ 로 두면 이분 그래프 문제와 정확히 같고, 조건은

\Bigl|\bigcup_{i \in I} A_i\Bigr| \ge |I| \qquad \forall\, I \subseteq \{1,\dots,m\}

이다. 위원회마다 대표를 뽑되 겹치지 않게, 부서마다 담당자를 배정하되 한 사람이 두 자리를 못 맡게 — SDR이 나오는 자리는 이 모양이다.

행렬 언어로 옮기면 프로베니우스-쾨니그 정리가 된다. $n \times n$ 0-1 행렬에서 서로 다른 행·열을 하나씩 골라 전부 1인 자리를 찾는 것이 완전 매칭인데, 그런 선택이 불가능할 필요충분조건은 행렬 안에 $s + t = n + 1$ 을 만족하는 $s \times t$ 크기의 완전 영 부분행렬이 존재하는 것이다. 홀 조건의 대우를 행렬로 쓴 것에 지나지 않지만, 순열식(permanent)이 0인지 판정하는 조건으로 자주 인용된다.

파생 결과 하나만 더. 이중확률행렬은 항상 지지집합에서 홀 조건을 만족하고, 따라서 완전 매칭 = 순열행렬을 하나 뽑아낼 수 있다. 이를 반복하면 버코프-폰 노이만 정리(이중확률행렬 = 순열행렬들의 볼록결합)가 나온다. 헝가리안 알고리즘과 배정 문제의 정수성이 서 있는 기반이 이것이다.

7. 무한 그래프에서 깨지는 지점[편집]

정리가 유한성에 얼마나 기대고 있는지는 반례 하나로 드러난다. $X = \{x_0, x_1, x_2, \dots\}$ , $Y = \{y_1, y_2, \dots\}$ 를 두고 $x_0$ 는 모든 $y_i$ 와 인접, $x_i$ ( $i \ge 1$ )는 $y_i$ 하고만 인접시키자.

홀 조건은 성립한다 — $x_0$ 를 포함하는 집합의 이웃은 무한집합이고, $x_0$ 를 뺀 유한/무한 집합 $\{x_{i}\}_{i \in I}$ 의 이웃은 $\{y_i\}_{i \in I}$ 로 크기가 같다. 그런데 $X$ -포화 매칭은 없다. $i \ge 1$ 인 $x_i$ 는 $y_i$ 외에 선택지가 없으므로 $Y$ 가 전부 소진되고 $x_0$ 가 남는다.

수습 방법은 알려져 있다. 모든 정점의 차수가 유한하면(위 반례에서 $x_0$ 가 위반한 조건) 홀 조건은 무한 집합족에서도 충분조건이 된다. 마셜 홀 주니어(1948)가 “집합이 전부 유한하면 개수가 무한해도 SDR이 존재한다”로 정리했고, 증명은 유한 부분문제들의 해를 콤팩트성 논법으로 이어 붙이는 방식이다. 완전히 일반적인 무한 그래프에서는 정리를 어떻게 진술해야 하는가 자체가 어려운 문제였고, 이 계열의 확장은 20세기 후반 무한 조합론의 주요 주제였다.²

8. 안정 결혼과 헷갈리지 말 것[편집]

이름이 비슷해서 자주 뒤섞이지만 다른 문제다.

홀의 결혼정리는 존재성 문제다. 선호도가 없고 “가능/불가능”만 있으며, 답은 짝짓기가 가능한지 여부와 불가능하면 그 이유다.
안정 결혼 문제(게일-섀플리, 1962)는 안정성 문제다. 양쪽 모두 상대 전원에 대한 선호 순위를 갖고 있어 완전 매칭 자체는 언제나 존재하며, 질문은 “서로 현재 짝보다 상대를 선호하는 쌍(불안정 쌍)이 없는 매칭이 있는가”다. 답은 항상 예이고, 게일-섀플리 알고리즘이 $O(n^2)$ 에 구성한다.
헝가리안 알고리즘의 배정 문제는 최적화 문제다. 간선에 수치 비용이 있고 총합을 최소화한다. 선호를 기수적으로 다룬다는 점에서 안정 결혼과 갈린다.

셋 다 “짝짓기”라는 단어를 쓰지만 목적함수와 알고리즘이 전부 다르다. 요구사항이 “선호 순위”로 표현되는데 배정 문제로 모델링하거나, “가능한가”만 물으면 되는데 비용 행렬을 억지로 만드는 실수가 실무에서 종종 나온다. 짝을 셋 이상 묶거나 한쪽이 여럿을 받는 확장으로 가면 또 다른 이론(대학 입학 문제, $b$ -매칭)이 필요하고, 홀 조건도 그에 맞춰 일반화된 형태를 써야 한다.³

9. 관련 문서[편집]

반대로 홀 위반자를 안 뱉는 도구는 사람을 고문한다. “해가 없습니다”만 출력하는 배정 스크립트를 붙들고 조건을 하나씩 지워 보며 이진 탐색을 해 본 경험이 있다면, 결함 집합을 같이 출력하는 데 드는 비용이 탐색 한 번뿐이라는 사실이 꽤 억울하게 느껴질 것이다. ↩
위 반례에서 “무한 차수 정점 하나가 다 망친다”는 구조는 다른 무한 조합론 정리에서도 반복된다. 유한 조합론의 직관이 무한으로 넘어갈 때 가장 먼저 깨지는 것이 대개 “세면 된다”는 논법이고, 홀 정리의 필요조건 증명이 정확히 비둘기집 원리, 즉 세는 논법이었다는 점을 생각하면 자연스러운 결말이다. ↩
1935년 원논문의 예시가 “남자 집합의 어느 부분집합을 잡아도 그들이 아는 여자의 수가 그 이상이면”이었다는 점은 시대상으로 이해할 만하지만, 90년이 지난 지금도 교과서가 그 예시를 그대로 베끼고 있는 것은 다른 문제다. 요즘 강의노트는 대체로 “위원회와 대표”나 “작업과 기계”로 갈아탔다. ↩