홀의 결혼 정리 (Hall's Marriage Theorem)

정의

홀의 결혼 정리 (Hall’s Marriage Theorem) 는 이분 그래프 G = (L, R, E) 에서 완전 매칭 (perfect matching) 이 존재할 필요충분조건 을 제시하는 정리.

정리: G 에서 L 의 모든 정점을 커버하는 매칭이 존재한다.

<=> 모든 부분집합 S subset of L 에 대해 |N(S)| >= |S| (N(S) = S 의 이웃 집합 in R).

즉, L 의 어떤 부분집합을 봐도 그 집합의 이웃이 원래 집합보다 작지 않아야 완전 매칭이 존재.

Philip Hall (1935) 증명. 조합론의 기본 정리 중 하나.

문제 상황과 동기

n 명의 남성과 n 명의 여성이 있음. 각 남성은 특정 여성과만 결혼 의사가 있음. 모든 남성이 결혼할 수 있는가?

• naive: 모든 매칭을 시도 (n! 가지).
• Hall 조건: 모든 남성 부분집합에 대해, 그 집합이 선호하는 여성의 수가 집합의 크기 이상이면 항상 가능.

핵심 통찰: 완전 매칭의 존재성은 “어느 한쪽이 부족하지 않은가” 로 결정된다. 즉, bottleneck 은 이웃의 크기.

PS 응용: 매칭 존재성 판정, SDR (system of distinct representatives) 문제, 조합적 설계 검증, Dilworth 정리 연결.

시각화

핵심 아이디어

필요성 (=>)

완전 매칭 M 이 존재하면, S 의 각 원소는 M 을 통해 서로 다른 R 의 원소와 연결됨. 따라서 |N(S)| >= |S|. 당연.

충분성 (≤)

귀납법 또는 augmenting path 로 증명:

• |L| = 1: trivial.
• |L| > 1: 두 case 로 나눔.
  • Case 1: 모든 진부분집합 S (S != empty, S != L) 에 대해 |N(S)| > |S|. 아무 간선 (u,v) 매칭, 남은 그래프에서 Hall 조건 유지 -> 귀납.
  • Case 2: |N(S)| = |S| 인 진부분집합 S 존재. S 와 N(S) 사이 완전 매칭 (귀납), 나머지 L-S 에서도 Hall 조건 성립 -> 결합.

Hall violator

Hall 조건을 깨는 집합 S (|N(S)| < |S|) 를 Hall violator 라고 함. 존재하면 완전 매칭 불가능. min-cut 과 연결되어 있음.

König 정리와의 관계

König: |최대 매칭| = |최소 정점 덮개|. Hall 조건은 이분 그래프에서 |최대 매칭| = |L| 인 조건.

Dilworth 정리

부분 순서 집합에서 chain 분할과 antichain 크기의 관계. Hall 의 일반화.

알고리즘

check_perfect_matching(G):
    max_matching = dfs_augment_all(G)   // O(VE)
    if max_matching == |L|: return YES
    return find_hall_violator(G)

find_hall_violator(G):
    // orient: unmatched L->R, matched R->L
    // BFS from unmatched L vertices
    // Z = reachable vertices
    // S = L ∩ Z  (Hall violator, |N(S)| < |S|)
    build_directed_alternating_graph(G)
    Z = bfs(all_unmatched_L)
    S = Z ∩ L
    return S

구현

// Hall's theorem: perfect matching check + violator find
#include <bits/stdc++.h>
using namespace std;
​
int n, m, e;               // |L| = n, |R| = m
vector<int> adj[1005];
int matchL[1005], matchR[1005];
bool visited[1005];
​
bool dfs(int u) {
  for (int v : adj[u]) {
      if (visited[v]) continue;
      visited[v] = true;
      if (matchR[v] < 0 || dfs(matchR[v])) {
          matchL[u] = v;
          matchR[v] = u;
          return true;
      }
  }
  return false;
}
​
int max_matching() {
  fill(matchL, matchL + n, -1);
  fill(matchR, matchR + m, -1);
  int cnt = 0;
  for (int u = 0; u < n; u++) {
      fill(visited, visited + m, false);
      if (dfs(u)) cnt++;
  }
  return cnt;
}
​
vector<int> find_violator() {
  // build directed graph for alternating BFS
  vector<vector<int>> g(n + m);
  for (int u = 0; u < n; u++) {
      for (int v : adj[u]) {
          if (matchL[u] == v) g[n + v].push_back(u);     // matched: R -> L
          else g[u].push_back(n + v);                     // unmatched: L -> R
      }
  }
  // BFS from unmatched L
  vector<bool> vis(n + m, false);
  queue<int> q;
  for (int u = 0; u < n; u++) {
      if (matchL[u] < 0) { q.push(u); vis[u] = true; }
  }
  while (!q.empty()) {
      int cur = q.front(); q.pop();
      for (int nxt : g[cur]) {
          if (!vis[nxt]) { vis[nxt] = true; q.push(nxt); }
      }
  }
  // Hall violator S = reachable L in alternating graph
  vector<int> S;
  for (int u = 0; u < n; u++)
      if (vis[u]) S.push_back(u);
  return S;
}
​
int main() {
  cin >> n >> m >> e;
  for (int i = 0; i < e; i++) {
      int u, v; cin >> u >> v; u--; v--;
      adj[u].push_back(v);
  }
  int cnt = max_matching();
  if (cnt == n) { cout << "YES\n"; return 0; }
  auto S = find_violator();
  set<int> nhd;
  for (int u : S)
      for (int v : adj[u])
          nhd.insert(v);
  cout << "NO\nHall violator: [";
  for (int i = 0; i < (int)S.size(); i++) {
      if (i) cout << ", ";
      cout << S[i] + 1;
  }
  cout << "]\n|N(S)| = " << nhd.size() << " < |S| = " << S.size() << "\n";
}

# Hall's theorem: perfect matching check + violator find
import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
​
n, m, e = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(e):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  adj[u].append(v)
​
matchL = [-1] * n
matchR = [-1] * m
​
def dfs(u, visited):
  for v in adj[u]:
      if visited[v]: continue
      visited[v] = True
      if matchR[v] < 0 or dfs(matchR[v], visited):
          matchL[u] = v
          matchR[v] = u
          return True
  return False
​
cnt = 0
for u in range(n):
  visited = [False] * m
  if dfs(u, visited): cnt += 1
​
if cnt == n:
  print("YES")
else:
  # build alternating graph for Hall violator
  g = [[] for _ in range(n + m)]
  for u in range(n):
      for v in adj[u]:
          if matchL[u] == v:
              g[n + v].append(u)   # matched: R -> L
          else:
              g[u].append(n + v)   # unmatched: L -> R
  # BFS from unmatched L
  q = deque()
  vis = [False] * (n + m)
  for u in range(n):
      if matchL[u] < 0:
          q.append(u); vis[u] = True
  while q:
      cur = q.popleft()
      for nxt in g[cur]:
          if not vis[nxt]:
              vis[nxt] = True; q.append(nxt)
  S = [u for u in range(n) if vis[u]]
  nhd = set()
  for u in S:
      nhd.update(adj[u])
  print(f"NO\nHall violator: {[u+1 for u in S]}")
  print(f"|N(S)| = {len(nhd)} < |S| = {len(S)}")

3 3 5
1 1
1 2
2 2
2 3
3 1

YES

3 3 4
1 1
1 2
2 1
2 2

NO
Hall violator: [3]
|N(S)| = 0 < |S| = 1

복잡도

Hall 조건의 응용

1. SDR (System of Distinct Representatives)

집합족 {A_1, …, A_n} 에서 각 집합에서 서로 다른 대표 원소를 고를 수 있음 <=> 모든 J subset of [n] 에 대해 |union_{i in J} A_i| >= |J|.

2. Latin rectangle 확장

r x n Latin rectangle 을 n x n Latin square 로 항상 확장 가능 (Hall 조건).

3. Dilworth 정리

finite poset 에서 최소 chain 분할 크기 = 최대 antichain 크기. Hall 정리로 증명 가능.

4. 정규 이분 그래프

k-regular bipartite graph 는 항상 완전 매칭을 가짐 (Hall 조건 자동 성립).

함정

1. Hall 조건은 “완전 매칭” 만 판정

Hall 조건은 L 의 완전 매칭 (즉 |L| 만큼의 매칭) 만 판정. R 쪽까지 모두 커버하는 perfect matching 의 존재성은 |L| = |R| 일 때만 Hall 조건으로 판정 가능.

2. Hall violator 찾기는 최대 매칭 이후

Hall violator 를 직접 찾으려면 최대 매칭을 먼저 구해야 함. 단순히 “조건을 깨는 부분집합” 은 matching 없이 직접 찾기 어려움.

3. |N(S)| >= |S| 확인의 비효율성

모든 부분집합 S subset of L (2^|L| 개) 를 검사하는 것은 불가능. 대신 최대 매칭으로 판정.

BOJ 연습 문제

참고

• 이분 그래프
• 이분 매칭 (augmenting path, Konig)
• 최대 유량 (matching to flow)