매칭과 홀의 정리

개요 — 동기·문제의식

매칭(matching) 은 서로 끝점을 공유하지 않는 간선들의 집합이다. 한 사람이 두 일자리에 동시에 배정될 수 없고, 한 일자리에 두 사람이 동시에 배정될 수 없다는 식의 충돌 제약을 그래프 언어로 적으면 매칭 문제가 된다.

가장 기본적이고 강력한 결과는 Hall 결혼정리다. 이분그래프의 한쪽 part $A$ 를 모두 매칭할 수 있는 필요충분조건은, $A$ 의 임의의 부분집합 $S$ 가 적어도 $|S|$ 개의 이웃을 가져야 한다는 것이다. 이 조건은 너무 당연해 보이지만, 놀랍게도 충분하기까지 하다.¹

매칭 이론은 connectivity and menger의 분리자-경로 이중성과 닮아 있다. 실제로 Diestel은 König 정리와 Menger 정리를 같은 종류의 packing-covering 정리로 배치한다.²

직관

이분그래프 $G$ 의 두 part를 사람 $A$ 와 일자리 $B$ 라고 하자. 간선 $ab$ 는 사람 $a$ 가 일자리 $b$ 를 맡을 수 있다는 뜻이다. $A$ 를 모두 배정하려면 어떤 사람 무리 $S\subseteq A$ 도 자기들이 갈 수 있는 일자리 집합 $N(S)$ 보다 더 클 수 없다.

Hall 조건은 병목을 찾는 조건이다. 배정이 안 된다면 실패한 이유는 "전체적으로 뭔가 복잡해서"가 아니라, 이미 어떤 부분집합 $S$ 가 자기 이웃보다 많기 때문이다. 즉 매칭 문제의 모든 장애물은 국소적인 부족 집합으로 잡힌다.

증명의 핵심 직관은 augmenting path다. 현재 매칭이 완전하지 않을 때, unmatched 정점에서 시작해 매칭 밖 간선과 매칭 간선을 번갈아 따라가다가 반대쪽 unmatched 정점에 도달하면, 간선 선택을 뒤집어 매칭 크기를 1 늘릴 수 있다.

정의

매칭: 서로 인접하지 않은 간선들의 집합 $M\subseteq E(G)$.

포화(saturated, matched): 정점 $v$ 가 $M$ 의 어떤 간선에 incident하면 $v$ 는 $M$ 에 의해 포화되었다고 한다.

$A$ 의 매칭: 이분그래프 $G=(A\cup B,E)$ 에서 $A$ 의 모든 정점을 포화하는 매칭.

완전매칭 / 1-factor: 모든 정점을 포화하는 매칭. 일반 그래프에서는 1-factor라고도 한다.

주의: maximum은 전역 최적이고, maximal은 더 이상 locally 확장할 수 없다는 뜻이다. 둘은 다르다.

주요 정리

정리 1 (augmenting path 판정). 매칭 $M$ 이 maximum이 아니면 $M$ 에 대한 augmenting path가 존재한다. 반대로 augmenting path가 있으면 $M$ 은 maximum이 아니다.³

정리 2 (Hall 결혼정리). 이분그래프 $G=(A\cup B,E)$ 가 $A$ 를 포화하는 매칭을 가질 필요충분조건은 모든 $S\subseteq A$ 에 대해 $$|N(S)|\ge |S|$$ 가 성립하는 것이다.

충분성을 보이자. Hall 조건을 만족하지만 $A$ 를 포화하지 못하는 최대 매칭 $M$ 을 잡고, $A$ 의 unmatched 정점 $a_0$ 에서 시작하는 alternating path로 도달 가능한 정점들의 집합을 $Z$ 라 하자. $S=Z\cap A$, $T=Z\cap B$ 로 둔다. 최대성 때문에 $T$ 안의 모든 정점은 matched되어야 한다. 그렇지 않으면 $a_0$ 에서 그 정점까지 augmenting path가 생긴다.

또한 $S\setminus\{a_0\}$ 의 각 정점은 $T$ 의 어떤 정점과 매칭되어 있고, $T$ 의 각 정점의 매칭 partner도 $S\setminus\{a_0\}$ 에 있다. 따라서 $|T|=|S|-1$ 이다. 한편 $S$ 의 어떤 이웃 $b$ 가 $T$ 밖에 있다면, $S$ 로 가는 alternating path 뒤에 간선 $ab$ 를 붙여 $b$ 에 도달할 수 있으므로 모순이다. 따라서 $N(S)=T$ 이고 $|N(S)|=|S|-1<|S|$, Hall 조건에 모순. ∎

정리 3 (König 정리, 이분그래프). 이분그래프에서 maximum matching의 크기는 minimum vertex cover의 크기와 같다.²

정리 4 (Tutte 1-factor 정리, 안내). 일반 그래프 $G$ 가 완전매칭을 가질 필요충분조건은 모든 $S\subseteq V(G)$ 에 대해 $$q(G-S)\le |S|$$ 가 성립하는 것이다. 여기서 $q(G-S)$ 는 $G-S$ 의 홀수 크기 연결성분 수다.⁴

의미. 이분그래프에서는 Hall 조건이 모든 장애물을 설명하지만, 일반 그래프에서는 홀수 성분이 새 장애물이 된다. 홀수 성분 하나는 내부만으로 완전매칭을 이룰 수 없으므로, 바깥 $S$ 로 나가는 매칭 간선이 적어도 하나 필요하다.

예제

예제 1 ($K_{3,3}$). 왼쪽 part $A$ 의 임의의 $s$개 정점은 오른쪽 전체 3개를 이웃으로 갖는다. $s\le3$ 이므로 Hall 조건이 성립하고, $A$ 를 포화하는 매칭이 존재한다. 실제로 세 개의 서로 다른 perfect matching이 많다.

예제 2 (별 $K_{1,3}$). 중심을 $B$ 쪽, leaf 셋을 $A$ 쪽으로 두면 $S=A$ 에 대해 $|N(S)|=1<3$ 이다. leaf 셋을 모두 매칭할 수 없다.

예제 3 ($P_4$). 경로 $a_1-b_1-a_2-b_2$ 를 이분그래프로 보면 $\{a_1b_1,a_2b_2\}$ 는 완전매칭이다. 다른 매칭 $\{b_1a_2\}$ 는 maximal일 수 있지만 maximum은 아니다.

예제 4 ($C_5$). 홀수 순환은 완전매칭이 없다. $S=\varnothing$ 에서 $q(C_5)=1>|S|=0$ 이므로 Tutte 조건이 실패한다.

예제 5 ($C_6$). 짝수 순환은 번갈아 간선을 고르면 완전매칭이 있다. 두 가지 완전매칭이 순환을 따라 교대로 나타난다.

예제 6 (Petersen 그래프). Petersen 그래프는 3-정규이고 bridgeless cubic 그래프이므로 완전매칭을 가진다(Petersen 정리). 하지만 Hamilton 순환은 없으므로, 완전매칭의 존재가 Hamiltonicity를 의미하지 않는다.

예제 7 (수강 배정). 학생 $A$ 와 세미나 $B$ 를 두고 가능한 수강을 간선으로 둔다. 어떤 학생 집합 $S$ 가 지원 가능한 세미나를 $|S|-1$개 이하만 가진다면, 그 집합 내부에서 이미 배정 실패가 강제된다.

예제 8 (체스판 도미노). 흰 칸과 검은 칸을 part로 두고 인접한 칸을 간선으로 두면, 도미노 타일링은 완전매칭이다. 모서리 두 칸을 같은 색으로 제거한 체스판은 양쪽 part 크기가 달라져 완전매칭이 불가능하다.

흔한 오해와 함정

• maximal과 maximum 혼동 — 더 이상 추가할 수 없는 매칭이 최대 크기일 필요는 없다.
• Hall 조건을 $S=A$ 에 대해서만 확인하기 — 모든 부분집합 $S\subseteq A$ 를 확인해야 한다. 병목은 작은 부분집합에서 생길 수 있다.
• 이분그래프 정리를 일반 그래프에 그대로 적용하기 — Hall과 König의 깔끔한 형태는 이분그래프 구조에 의존한다.
• 완전매칭과 완전그래프 혼동 — 완전매칭은 간선 선택이고, 완전그래프는 모든 간선을 가진 그래프다.
• augmenting path가 아무 alternating path나 된다고 생각하기 — 양 끝이 unmatched여야 뒤집었을 때 매칭 크기가 증가한다.
• Tutte 조건의 홀수 성분을 무시하기 — 일반 그래프에서는 홀수 성분이 정확한 장애물이다.

큰 그림 / 연결

매칭은 packing 문제다. 서로 충돌하지 않는 간선을 최대한 많이 고르는 것이다. König 정리는 이 packing의 최댓값이 모든 간선을 덮는 최소 vertex cover와 같다는 covering 정리다.

connectivity and menger의 Menger 정리도 같은 형태다: 서로소 path를 최대한 많이 packing하는 수가, 두 집합을 분리하는 최소 separator 크기와 같다. 이 관점은 network flows에서 max-flow min-cut 정리로 더 넓어진다.

일반 그래프 매칭은 Tutte 정리와 Gallai-Edmonds 구조정리로 이어진다. Diestel의 무한 그래프 장에서는 König, Hall, Tutte 정리가 무한 그래프에서 어떤 방식으로 바뀌는지도 다룬다. 그 지점은 settheory 위키 axiom-of-choice, compactness와 연결된다.

연습문제

1. $K_{m,n}$ 에서 maximum matching의 크기를 구하라.
2. $K_{1,4}$ 에서 leaf 쪽 part를 모두 매칭할 수 없는 이유를 Hall 조건으로 설명하라.
3. $P_5$ 의 maximum matching 크기를 구하라.
4. $C_{2k}$ 와 $C_{2k+1}$ 의 maximum matching 크기를 각각 구하라.
5. Hall 정리의 필요성을 한 문장으로 증명하라.
6. 위 증명의 alternating reachability 집합 $Z$ 에서 왜 $N(S)=T$ 인지 자세히 설명하라.
7. 이분그래프에서 maximum matching 크기보다 작은 vertex cover가 존재할 수 없음을 보여라.
8. $C_5$ 가 Tutte 조건을 위반함을 $S=\varnothing$ 으로 확인하라.
9. 8x8 체스판에서 서로 다른 색 칸 하나씩을 제거하면 Hall 조건이 항상 충분한지 생각해 보라.

관련 개념

• graphs basics and trees — 이분그래프와 기본 경로 언어
• connectivity and menger — packing-covering 이중성
• network flows — max-flow min-cut과 매칭 알고리즘
• extremal and ramsey — matching number를 제약하는 extremal 문제
• reading path diestel — Diestel 2장 학습 순서

각주