bipartite matching, 이분 매칭, 최대 매칭, maximum matching, Hopcroft-Karp, augmenting path
정의
이분 매칭 (Bipartite Matching) 은 이분 그래프 G = (L ∪ R, E) 에서 간선 부분집합 M ⊆ E 을 선택하되, M 의 어떤 두 간선도 정점을 공유하지 않는 (disjoint endpoints) 최대 크기 M.
수학적: M 이 매칭 ↔ 모든 v ∈ V 에 대해 M 의 간선이 v 를 많아야 한 번 포함.
최대 매칭 (maximum matching): 가능한 M 중 |M| 이 최대.
알고리즘:
DFS augmenting path (기본): O(VE).
Hopcroft-Karp: O(E√V), 레벨 그래프 + multi-path BFS.
최대 유량: 이분 매칭 = max-flow (L→R 용량 1). Dinic O(V^2 E) 또는 Push-Relabel O(V^3).
문제 상황과 동기
PS 전형: 직원-작업, 학생-프로젝트, 축사-소 배정.
naive: 모든 간선 부분집합 (2^E) 순회 → 불가능.
greedy: 임의 순서로 간선 추가 → 최대 보장 없음.
augmenting path (Ford-Fulkerson 아이디어): 매칭을 키울 수 있는 경로를 DFS 로 찾기. O(VE).
Hopcroft-Karp: BFS 로 여러 경로 한꺼번에 증강. O(E√V).
핵심 통찰: 증가 경로 (augmenting path) 존재 ↔ 매칭이 최대가 아님. Berge’s lemma.
실무: 추천 시스템, 작업 스케줄링, 네트워크 최적화.
시각화
핵심 아이디어
augmenting path
경로 P: 시작/끝 모두 미매칭 정점 (unmatched), 간선이 매칭/비매칭 교대.
P 를 발견하면 매칭 간선 반전 (M ← M △ P) → |M| 증가 1.
Berge’s lemma: augmenting path 없으면 M 이 최대 매칭.
DFS augmenting path (기본)
L 의 미매칭 정점에서 DFS:
비매칭 간선 (u, v) 로 R 진입.
v 가 미매칭이면 성공 (경로 완성).
v 가 이미 매칭되어 있으면 (v, w) 로 L 로 돌아가 재귀.
최악 O(VE): V 번의 DFS, 각 O(E).
Hopcroft-Karp (O(E√V))
BFS 레벨 그래프 구축: 미매칭 L 에서 시작, 매칭/비매칭 교대로 레벨.
DFS 로 여러 augmenting path 동시 증강.
레벨 그래프 갱신 반복.
√V phase 내에 완료 (증명: 각 phase 마다 최단 augmenting path 길이 증가).
König 정리
이분 그래프에서:
|최대 매칭| = |최소 정점 덮개|.
정점 덮개 (vertex cover): 모든 간선이 적어도 한 끝점을 포함하는 정점 집합.
응용: 간선 선택 문제 = 정점 선택 문제 dual.
증명: 최대 매칭 M 에서 M-alternating path 로 덮개 구성.
Hall’s marriage theorem
L 의 모든 부분집합 S 에 대해 |N(S)| ≥ |S| (N(S) = S 의 이웃 집합 in R) ↔ L 의 완전 매칭 존재.
알고리즘
DFS augmenting path (기본)
bipartite_matching_dfs(G): match_L[] = -1, match_R[] = -1 for u in L: if match_L[u] < 0: visited[] = false dfs_augment(u) return count(match_L >= 0)dfs_augment(u): for v in adj[u]: if visited[v]: continue visited[v] = true if match_R[v] < 0 or dfs_augment(match_R[v]): match_L[u] = v match_R[v] = u return true return false
Hopcroft-Karp (O(E√V))
hopcroft_karp(G): match_L[] = -1, match_R[] = -1 while bfs_level() < ∞: for u in L: if match_L[u] < 0: dfs_augment_hk(u) return count(match_L >= 0)bfs_level(): queue = all unmatched u in L level[u] = 0 for u in queue min_level = ∞ while queue not empty: u = queue.pop() for v in adj[u]: if match_R[v] < 0: min_level = min(min_level, level[u] + 1) elif level[match_R[v]] < 0: level[match_R[v]] = level[u] + 2 queue.push(match_R[v]) return min_leveldfs_augment_hk(u): for v in adj[u]: if match_R[v] < 0: match_L[u] = v match_R[v] = u return true elif level[match_R[v]] == level[u] + 2 and dfs_augment_hk(match_R[v]): match_L[u] = v match_R[v] = u return true level[u] = -1 # 이번 phase 실패 return false
구현
// 이분 매칭 DFS augmenting path O(VE)#include <bits/stdc++.h>using namespace std;int n, m, e;vector<int> adj[1005]; // L[0..n-1] → Rint match_L[1005], match_R[1005];bool visited[1005];bool dfs_augment(int u) { for (int v : adj[u]) { if (visited[v]) continue; visited[v] = true; if (match_R[v] < 0 || dfs_augment(match_R[v])) { match_L[u] = v; match_R[v] = u; return true; } } return false;}int main() { cin >> n >> m >> e; // L 크기 n, R 크기 m, 간선 e fill(match_L, match_L + n, -1); fill(match_R, match_R + m, -1); for (int i = 0; i < e; i++) { int u, v; cin >> u >> v; u--; v--; // 0-indexed adj[u].push_back(v); } int cnt = 0; for (int u = 0; u < n; u++) { if (match_L[u] < 0) { fill(visited, visited + m, false); if (dfs_augment(u)) cnt++; } } cout << "최대 매칭: " << cnt << "\n"; for (int u = 0; u < n; u++) { if (match_L[u] >= 0) { cout << u + 1 << " - " << match_L[u] + 1 << "\n"; } }}
# 이분 매칭 DFS augmenting path O(VE)import syssys.setrecursionlimit(200005)input = sys.stdin.readlinen, m, e = map(int, input().split()) # L 크기 n, R 크기 m, 간선 eadj = [[] for _ in range(n)]match_L = [-1] * nmatch_R = [-1] * mfor _ in range(e): u, v = map(int, input().split()) u -= 1; v -= 1 # 0-indexed adj[u].append(v)def dfs_augment(u, visited): for v in adj[u]: if visited[v]: continue visited[v] = True if match_R[v] < 0 or dfs_augment(match_R[v], visited): match_L[u] = v match_R[v] = u return True return Falsecnt = 0for u in range(n): if match_L[u] < 0: visited = [False] * m if dfs_augment(u, visited): cnt += 1print(f"최대 매칭: {cnt}")for u in range(n): if match_L[u] >= 0: print(f"{u+1} - {match_L[u]+1}")
// 이분 매칭 DFS augmenting path O(VE)import java.util.*;import java.io.*;public class Main { static int n, m, e; static List<Integer>[] adj; static int[] matchL, matchR; static boolean[] visited; static boolean dfsAugment(int u) { for (int v : adj[u]) { if (visited[v]) continue; visited[v] = true; if (matchR[v] < 0 || dfsAugment(matchR[v])) { matchL[u] = v; matchR[v] = u; return true; } } return false; } @SuppressWarnings("unchecked") public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); e = Integer.parseInt(st.nextToken()); adj = new ArrayList[n]; matchL = new int[n]; matchR = new int[m]; Arrays.fill(matchL, -1); Arrays.fill(matchR, -1); for (int i = 0; i < n; i++) adj[i] = new ArrayList<>(); for (int i = 0; i < e; i++) { st = new StringTokenizer(br.readLine()); int u = Integer.parseInt(st.nextToken()) - 1; int v = Integer.parseInt(st.nextToken()) - 1; adj[u].add(v); } int cnt = 0; for (int u = 0; u < n; u++) { if (matchL[u] < 0) { visited = new boolean[m]; if (dfsAugment(u)) cnt++; } } System.out.println("최대 매칭: " + cnt); for (int u = 0; u < n; u++) { if (matchL[u] >= 0) { System.out.println((u+1) + " - " + (matchL[u]+1)); } } }}
stdin
3 3 51 11 22 22 33 1
결과
최대 매칭: 31 - 22 - 33 - 1
복잡도
항목
값
DFS augmenting path
O(VE) 시간, O(V+E) 공간
Hopcroft-Karp
O(E√V) 시간, O(V+E) 공간
최대 유량 (Dinic)
O(V^2 E) 시간 (이분 그래프에서 O(E√V))
전처리
없음 (그래프 입력만)
König 정리와 최소 정점 덮개
이분 그래프에서:
최대 매칭 M: 간선 부분집합, disjoint endpoints.
최소 정점 덮개 C: 모든 간선이 C 의 정점 하나 이상 포함.
König 정리: |M| = |C|.
구성: 최대 매칭 M 에서 시작, M-alternating path 로 도달 가능한 정점 집합 Z 구하기.
💬 댓글