이분 매칭은 정점을 두 partition으로 나누고, 서로 다른 양쪽 정점을 잇는 간선 중에서 끝점이 겹치지 않게 고르는 문제입니다. 핵심은 “지금 고른 간선을 유지하면서 더 좋은 선택을 찾는다”가 아니라, 현재 매칭을 기준으로 증가 경로(augmenting path)를 찾아 매칭과 비매칭 간선의 소속을 뒤집는 것입니다. 양 끝이 아직 매칭되지 않은 경로라면 매칭 간선 수가 정확히 하나 늘고, 그런 경로가 더 이상 없을 때 현재 매칭은 최대 카디널리티입니다.
모델과 매칭 불변식
왼쪽 정점 집합을 L, 오른쪽을 R이라 하고 간선은 L→R로 저장하겠습니다. 매칭 M은 같은 정점을 두 번 포함하지 않는 간선 부분집합입니다. 따라서 matchR[r]에는 r과 연결된 왼쪽 정점 하나 또는 NONE만 들어가고, 왼쪽에서 시작하는 DFS는 “이 오른쪽 정점을 이미 다른 왼쪽이 사용하고 있는가?”를 검사합니다. 일반 그래프의 임의 경로를 찾는 것과 달리, 탐색 중에 간선의 방향이 현재 매칭 소속에 따라 번갈아 바뀝니다.
초기 매칭은 공집합으로 둡니다. 한 번의 성공적인 시도 뒤에도 다음 조건을 지켜야 합니다.
- 모든
matchR[r]는 최대 한 왼쪽 정점만 가리킨다. matchR[r]=l이면 간선(l,r)가 실제 그래프에 존재하고 매칭에 들어 있다.- 성공할 때마다
|M|은 1만 증가한다. - 실패한 시도는 현재 매칭을 바꾸지 않는다.
이 불변식은 매칭 배열 하나만 갱신하는 Kuhn 방식에서 특히 중요합니다. 왼쪽에 대한 역배열도 저장한다면 두 배열을 같은 순간에 갱신하거나, 한쪽만으로 의미를 정의해야 합니다.
증가 경로의 교대 구조
증가 경로는 매칭에 속하지 않는 간선으로 시작하고, 매칭에 속하는 간선과 비매칭 간선을 번갈아 지나며, 마지막도 비매칭 간선으로 끝납니다. 출발 왼쪽 정점과 도착 오른쪽 정점이 모두 현재 매칭에 속하지 않아야 합니다. 이 조건에서 경로의 간선 수는 홀수이고, 비매칭 간선이 매칭 간선보다 하나 많습니다.
예를 들어 다음 상태를 보겠습니다.
L1-R1은 현재 매칭이다.L1-R2,L2-R1은 그래프 간선이지만 현재 매칭은 아니다.L2와R2는 아직 매칭되지 않았다.
L2-R1-L1-R2는 비매칭, 매칭, 비매칭의 순서입니다. 이 경로에서 세 간선의 소속을 뒤집으면 L1-R1을 제거하고 L2-R1과 L1-R2를 추가합니다. 위 경로에서 중간 매칭 간선은 L1-R1 하나이므로 최종 매칭은 L2-R1, L1-R2 두 개입니다. 기존 한 개가 두 개가 되어 크기가 1 증가합니다.
그림을 글로 읽기
- 현재 M: L1-R1 한 개 · L2·R2는 자유
- L2-R1-L1-R2: 비매칭-매칭-비매칭 · 양 끝이 자유
- 새 M: L2-R1와 L1-R2 · 두 개로 증가
- 현재 M → L2-R1-L1-R2: 교대 경로 선택
- L2-R1-L1-R2 → 새 M: 모든 소속 뒤집기
경로의 내부 정점은 한 번은 들어오고 한 번은 나가므로 끝점 중복이 새로 생기지 않습니다. 내부에서 원래 매칭이었던 간선은 제거되고, 원래 비매칭이었던 간선은 추가됩니다. 따라서 |P\M| = |P∩M|+1이고, 추가 간선 수에서 제거 간선 수를 뺀 값이 1입니다. |M Δ P|는 바뀐 간선의 총 개수일 뿐 이 차이와 같은 값은 아닙니다. 이것이 “잠시 기존 매칭을 취소하는데도” 카디널리티가 증가하는 이유입니다. 양 끝이 모두 이미 매칭된 alternating cycle을 뒤집으면 간선 수가 그대로라서 증가 경로가 아닙니다.
Kuhn DFS의 상태 전개
왼쪽 정점 l에서 시작하는 전형적인 DFS는 r의 현재 상대가 없으면 즉시 r을 l에 배정하고, 상대가 old=matchR[r]라면 old가 다른 오른쪽 정점을 찾을 수 있는지 재귀적으로 시도합니다.
try_augment(l, token):
for r in adjacency[l]:
if seen[r] == token:
continue
seen[r] = token
old = matchR[r]
if old == NONE or try_augment(old, token):
matchR[r] = l
return true
return false
L1이 R1을 보았는데 R1은 이미 L0와 매칭되어 있다고 하겠습니다. try_augment(L0)가 성공해 L0를 R2로 옮기면 호출이 돌아온 뒤 matchR[R1]=L1로 덮어쓸 수 있습니다. 호출 스택의 복귀 순서가 곧 “이전 상대를 재배치한 뒤 현재 정점을 연결한다”는 교대 경로의 뒤집기입니다. 별도의 경로 목록을 만들지 않아도 매칭 배열 덮어쓰기가 같은 효과를 냅니다.
실패가 발생했다고 해서 탐색 중 일부 배정을 되돌릴 필요는 없습니다. 위 의사코드는 재귀가 성공했을 때에만 상위 프레임의 matchR[r]를 바꾸므로, 실패한 가지는 배열에 흔적을 남기지 않습니다. 구현이 먼저 배열을 쓰고 나중에 실패하는 구조라면 복구 로그가 필요하고, 보통은 성공 조건 안에서만 쓰는 편이 안전합니다.
방문 token과 탐색 세대
한 augmentation DFS 안에서는 같은 오른쪽 정점을 여러 번 따라가면 순환과 중복 작업이 발생합니다. 그러나 모든 시작 왼쪽 정점 사이에서 seen을 영구 유지하면 안 됩니다. 매칭이 하나 추가될 때마다 어느 왼쪽 정점이 어느 오른쪽 정점을 점유하는지 달라져서, 과거에 막혔던 가지가 새 경로로 성공할 수 있기 때문입니다.
그래서 attempt를 세대로 쓰고 seen[r] == attempt인 경우에만 이번 DFS에서 재방문을 막습니다. L0 시도에서 R2를 보았더라도 다음 L1 시도에서는 token을 증가시켜 R2를 새 구조에서 다시 검사합니다. 배열 전체를 매번 false로 채우는 비용을 피하는 구현 기법이지만, 의미는 “이번 탐색에서 방문”과 “과거 어느 탐색에서 방문”을 구분하는 것입니다.
토큰이 정수 범위를 넘을 수 있는 장수 프로세스에서는 세대 래핑을 처리해야 합니다. 작은 범위의 token을 무심코 재사용하면 오래된 값이 현재 세대와 같아져 정점을 잘못 건너뛸 수 있습니다. 현실적인 구현에서는 충분히 큰 정수형을 쓰거나, 포화 시 배열을 0으로 초기화하는 정책을 둡니다.
분할 방향과 복잡도
Kuhn 방식의 표준적인 상한은 시작 쪽 정점 수를 n1, 간선 수를 m이라 할 때 O(n1·m)으로 설명합니다. 각 시작 정점에서 DFS가 간선을 훑을 수 있고, 이를 n1번 시도하기 때문입니다. 실제 상수와 입력 구조에 따라 다르지만, 한쪽 partition이 100개이고 다른 쪽이 10,000개라면 10,000개 쪽을 시작점으로 고정할 이유가 없습니다. 그래프의 양쪽 이름을 바꾸고 match의 인덱스 의미도 함께 바꿔 작은 쪽에서 시도하는 것이 유리합니다.
이 변환은 정답의 크기를 바꾸지 않습니다. 같은 매칭 간선을 반대 방향으로 표현할 뿐이고, Berge의 증명 조건인 “증가 경로가 있으면 크기를 하나 늘릴 수 있다”도 그대로입니다. 다만 adj[l]가 어느 partition의 배열인지, matchR[r]가 어느 쪽 인덱스를 저장하는지, 출력할 때 원래 정점 ID로 되돌리는지를 한 계약으로 묶어야 합니다. partition만 교체하고 배열의 상대 인덱스를 그대로 읽으면 전혀 다른 정점을 해제하는 버그가 생깁니다.
그래프가 크고 반복 DFS가 병목이면 Hopcroft–Karp를 검토합니다. 이 알고리즘은 BFS로 증가 경로의 층을 구성하고 DFS로 같은 최단 층에 속하는 경로들을 묶어 찾습니다. 여기서 바뀌는 것은 탐색 전략과 시간 상한이지 문제의 결과 계약이 아닙니다. 가중치가 있는 매칭, 일반 그래프 매칭, 모든 가능한 매칭 열거 문제를 자동으로 해결하는 것은 아닙니다. 필요한 것이 최대 카디널리티인지, 최대 가중치인지부터 다시 확인해야 합니다.
최대성 증명과 실패 경계
현재 매칭에 증가 경로가 하나라도 있으면 위 뒤집기로 매칭 크기를 키울 수 있습니다. 반대로 증가 경로가 없다면 현재 매칭은 최대입니다. 이 양방향 조건이 흔히 Berge 정리라고 불리는 최대 매칭의 판정 기준입니다. 따라서 “DFS가 이번 시작점에서 실패했다”는 것은 전역 최대라는 뜻이 아니며, 모든 적절한 시작 정점을 더 이상 성공시키지 못하는 상태까지 가야 합니다.
검증용 작은 입력에서는 다음 trace를 기록하면 좋습니다. 각 DFS의 token, 방문한 오른쪽 집합, 재귀 호출이 본 old, 성공 복귀 시 갱신된 matchR, 매칭 크기를 한 행에 씁니다. L2가 R1을 통해 L1을 밀어내고 R2를 얻는 경우 최종 크기가 1 증가해야 합니다. 반대로 양 끝이 매칭된 교대 cycle만 뒤집은 경우 크기가 그대로여야 하며, 이것을 성공으로 세면 알고리즘의 종료 조건이 흔들립니다.
참고 자료와 검증 범위
- Kuhn's Algorithm for Maximum Bipartite Matching — cp-algorithms, 2026-09-18 갱신본을 2026-09-19 본문으로 확인했습니다. 증가 경로의 증가 효과, 경로 부재와 최대성,
O(nm)설명의 근거로 사용했습니다. - BFS의 층별 탐색과 최단 거리 — 저장소 노트, BFS 방문 시점과 큐 불변식의 인접 개념으로 대조했습니다. 매칭 최적성의 근거를 BFS 최단성으로 바꾸어 말하지 않았습니다.
- 설명용 숫자 trace와 의사코드는 이 문서에서 직접 구성했습니다. 저장소의 테스트나 구현을 실행한 결과라고 주장하지 않습니다.
- Hopcroft–Karp의 층 탐색은 전환 경계를 설명하기 위한 개념 수준으로 적었으며, 이 장에서 해당 구현을 실행하거나 성능을 측정하지 않았습니다.