이분 매칭

최적설계 수치해석 마지막 수정: 2026-08-13 04:24:07

1. 개요[편집]

이분 매칭 Bipartite Matching
입력	이분 그래프 $G=(L\cup R, E)$
핵심 원리	증대 경로 · 베르주 정리(1957)
대표 알고리즘	홉크로프트-카프 $O(E\sqrt{V})$ (1973)
쌍대 정리	쾨니그 정리 · 홀의 결혼정리
가중 버전	배정 문제 · 헝가리안 알고리즘 $O(n^3)$
정수성 근거	접속행렬의 전체 단모듈성

이분 매칭(bipartite matching)은 정점 집합이 $L$ 과 $R$ 두 독립집합으로 갈리고 모든 간선이 $L$ 과 $R$ 을 잇는 이분 그래프에서, 끝점을 공유하지 않는 간선들의 집합(매칭) 중 크기가 최대인 것을 찾는 문제다. 일꾼과 작업, 학생과 기숙사, 검출된 물체와 추적 중인 궤적처럼 “왼쪽 하나에 오른쪽 하나씩, 겹치지 않게” 짝지어야 하는 상황이라면 전부 이 문제다.

매칭 $M \subseteq E$ 에 대해 $M$ 의 간선 끝점이 되는 정점을 포화(saturated)됐다고 하고, 모든 정점이 포화되면 완전 매칭(perfect matching), $L$ 의 모든 정점이 포화되면 $L$ -포화 매칭이라 부른다. 조합 최적화에서 이 문제가 갖는 위상은 특별하다 — NP-난해해 보이는 이산 문제인데 실제로는 다항시간에 정확히 풀리고, 게다가 그 이유를 최소절단·선형계획 쌍대성·정수성이라는 세 가지 언어로 각각 설명할 수 있다. 조합 최적화 교과서가 이 문제를 초반에 배치하는 데는 이유가 있다.¹

2. 증대 경로와 베르주 정리[편집]

이 분야의 모든 알고리즘은 하나의 개념 위에 서 있다. 매칭 $M$ 이 주어졌을 때, $M$ 에 속한 간선과 속하지 않은 간선이 번갈아 나타나는 경로를 교대 경로(alternating path)라 하고, 그중 양 끝점이 모두 미포화 정점인 것을 증대 경로(augmenting path)라 한다.

증대 경로 $P$ 를 찾으면 매칭을 키울 수 있다. $P$ 위에서 $M$ 에 속한 간선과 속하지 않은 간선의 역할을 통째로 뒤집으면, 즉 대칭차 $M \triangle E(P)$ 를 취하면 — $P$ 는 미매칭 간선으로 시작해 미매칭 간선으로 끝나므로 미매칭 간선이 매칭 간선보다 정확히 하나 많고, 결과는 여전히 매칭이면서 크기가 1 늘어난다. 여기서 베르주 정리(Berge, 1957)가 나온다.

매칭 $M$ 이 최대 $\iff$ $M$ 에 대한 증대 경로가 존재하지 않는다.

증명의 핵심은 대칭차의 구조다. 최대 매칭 $M^*$ 와 임의의 매칭 $M$ 에 대해 $M \triangle M^*$ 의 각 정점은 양쪽에서 최대 1개씩의 간선만 갖게 되므로, 이 부분그래프의 연결성분은 경로 아니면 짝수 길이 사이클뿐이다. 사이클과 짝수 길이 경로는 양쪽 간선 수가 같으므로 $|M^*| > |M|$ 이면 $M^*$ 간선이 하나 더 많은 홀수 길이 경로가 반드시 존재하고, 그게 바로 $M$ 에 대한 증대 경로다.

왼쪽 U와 오른쪽 V 사이에서 증대경로를 하나 찾을 때마다 매칭이 정확히 1 늘어난다. 같은 그래프(n=28, 평균차수 3, 간선 74)를 쿤(자유 정점마다 DFS)과 홉크로프트-카프(층별 BFS로 정점서로소 최단 증대경로를 한꺼번에)로 풀어 누적 간선검사를 계단그래프에 겹치면 쿤 572회·DFS 28번, HK 373회·phase 3번(최단 경로 길이 1→5→13)이 나온다. 끝나면 교대 도달집합으로 최소 정점덮개를 구성해 쾨니그 정리 |M| = |C| = 26 을 확인한다.

베르주 정리는 이분 그래프뿐 아니라 일반 그래프에서도 성립한다. 다만 찾는 난이도가 다르다. 이분 그래프에서는 미포화 정점에서 DFS/BFS를 한 번 돌리면 증대 경로가 있으면 반드시 걸리는데, 일반 그래프에서는 홀수 사이클(blossom)에 갇혀 탐색이 실패한다. 이 장애물을 수축(contraction)으로 걷어낸 것이 에드먼즈의 블로섬 알고리즘(1965)이고, 그 논문이 “다항시간 = 효율적”이라는 지금의 상식을 만든 문헌이기도 하다.

가장 단순한 구현(흔히 쿤의 알고리즘이라 불리는 것)은 $L$ 의 정점을 하나씩 훑으며 DFS로 증대 경로를 찾는다. 증대는 최대 $|L|$ 번, 매번 $O(E)$ 이므로 $O(VE)$ . 코드가 20줄이라 대회·실무 스크립트에서는 이걸 그냥 쓴다.

3. 홉크로프트-카프 알고리즘[편집]

$O(VE)$ 보다 나아지려면 증대 경로를 한 번에 여러 개 처리해야 한다. 1973년 홉크로프트와 카프가 낸 답은 이렇다.

각 페이즈에서,

미포화 정점들에서 BFS로 계층 그래프를 만들어 최단 증대 경로의 길이 $\ell$ 을 찾는다.
길이가 정확히 $\ell$ 인 증대 경로들 중 서로 정점을 공유하지 않는 극대 집합을 DFS로 한꺼번에 찾아 모두 증대한다.

페이즈 하나가 $O(E)$ 다. 그리고 페이즈가 끝날 때마다 최단 증대 경로의 길이가 반드시 늘어난다는 것이 핵심 보조정리다. 여기서 페이즈 수 상한이 나온다. 최단 증대 경로의 길이가 $\ell$ 을 넘으면 현재 매칭과 최대 매칭의 대칭차에 들어 있는 정점-서로소 증대 경로가 각각 길이 $\ell$ 이상이므로 그 개수가 $O(V/\ell)$ 개뿐이고, 따라서 남은 증대 횟수도 그만큼이다. $\ell = \sqrt{V}$ 에서 끊으면 앞뒤 모두 $O(\sqrt V)$ 페이즈, 총

O\!\left(E\sqrt{V}\right)

가 된다. 정점 서로소 최단 경로를 한 페이즈에 몰아 처리한다는 이 발상은 네트워크 흐름의 디닉 알고리즘에서 차단 흐름을 찾는 것과 정확히 같은 아이디어이며, 실제로 단위 용량 네트워크에 디닉을 돌리면 같은 $O(E\sqrt V)$ 가 나온다. 일반 그래프에서 같은 경계를 달성하는 것은 미칼리-바지라니 알고리즘(1980)인데, 블로섬을 계층 구조 안에서 다루느라 구현 난이도가 악명 높다.²

4. 최대유량으로의 환원[편집]

이분 매칭은 흐름 문제로 그대로 번역된다. 소스 $s$ 를 $L$ 의 모든 정점에 용량 1로, $R$ 의 모든 정점을 싱크 $t$ 에 용량 1로 잇고, 원래 간선은 $L \to R$ 방향으로 용량 1(또는 $\infty$ )을 준다. 그러면

\text{최대 매칭 크기} = \text{최대유량}

이 된다. 정점 용량이 1이라는 제약이 “한 정점은 한 간선에만 쓰인다”를 그대로 표현하고, 정수성 정리가 최적 흐름을 0/1로 잡을 수 있음을 보장해 흐름이 곧 매칭이 된다. 유량 알고리즘 자체는 네트워크 흐름 문서로 넘긴다.

이 환원의 진짜 배당금은 알고리즘이 아니라 최소절단 쪽을 읽었을 때 나온다. 위 네트워크의 유한 용량 절단은 $s$ -쪽에 남길 $L$ 정점과 $t$ -쪽으로 보낼 $R$ 정점을 고르는 것이고, 원래 간선을 무한 용량으로 두면 절단이 유한하려면 모든 간선이 선택된 정점 중 하나에 닿아야 한다. 즉 유한 절단 = 정점 덮개(vertex cover)이고, 최대유량-최소절단 정리가 다음을 준다.

쾨니그 정리(König, 1931): 이분 그래프에서 최대 매칭의 크기 = 최소 정점 덮개의 크기.

일반 그래프에서는 이게 성립하지 않는다(삼각형만 봐도 매칭 1, 덮개 2다). 그리고 여집합을 취하면 최대 독립집합 크기 $= n -$ 최소 정점 덮개 크기이므로, 일반 그래프에서 NP-난해인 최대 독립집합이 이분 그래프에서는 매칭 하나로 풀린다. 쾨니그 정리가 이분 구조의 위력을 상징하는 정리로 꼽히는 이유다.

5. 홀의 결혼정리[편집]

$L$ 의 모든 정점을 포화시키는 매칭이 언제 존재하는가에 대한 답이 홀의 결혼정리(Hall, 1935)다. $S \subseteq L$ 의 이웃 집합을 $N(S)$ 라 할 때,

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

필요조건이라는 건 자명하다( $S$ 의 짝은 전부 $N(S)$ 안에 있어야 하니까). 충분조건이 정리의 내용이고, 증명은 베르주 정리로 곧장 간다 — 최대 매칭이 $L$ 을 포화시키지 못하면 미포화 정점에서 시작하는 교대 경로로 도달 가능한 $L$ -정점 집합 $S$ 가 $|N(S)| = |S| - 1$ 을 만족하도록 잡히기 때문이다.

이 논증은 조건이 깨졌을 때 얼마나 깨졌는지도 알려준다(결함형 홀 정리, 오레).

\text{최대 매칭 크기} = |L| - \max_{S \subseteq L}\big(|S| - |N(S)|\big)

즉 매칭을 방해하는 것은 언제나 “짝 후보가 부족한 집합” 하나로 요약된다. 실무에서 배정이 실패했을 때 어느 부분집합이 병목인지를 이 식이 그대로 짚어 준다는 점이 유용하다. 스케줄이 안 짜인다고 화내기 전에 병목 집합을 뽑아 보면, 대개 자격 조건이 과하게 좁은 작업 몇 개가 범인이다.³

6. 가중 이분 매칭 — 배정 문제[편집]

간선에 비용 $c_{ij}$ 가 붙고 총비용이 최소인 완전 매칭을 찾으라는 문제가 배정 문제(assignment problem)다. 정식화는 다음과 같다.

\min \sum_{i,j} c_{ij} x_{ij} \quad\text{s.t.}\quad \sum_j x_{ij} = 1,\ \ \sum_i x_{ij} = 1,\ \ x_{ij} \ge 0

정수 제약을 아예 쓰지 않았는데도 최적해가 0/1로 나온다. 이분 그래프 접속행렬이 전체 단모듈 이기 때문이며, 기하적으로는 이 다면체(이중확률행렬들의 집합)의 꼭짓점이 정확히 순열행렬이라는 버코프-폰 노이만 정리로 읽힌다.

전용 알고리즘이 헝가리안 알고리즘(쿤, 1955; 문크레스, 1957)이다. 골격은 LP 쌍대와 정확히 대응한다. 쌍대변수 $u_i, v_j$ 를 유지하며

u_i + v_j \le c_{ij}, \qquad \text{등호가 성립하는 간선만 모은 그래프에서 완전 매칭을 찾는다}

를 반복한다. 이 “등식 부분그래프”에서 완전 매칭을 못 찾으면 홀 조건이 깨진 병목 집합이 드러나고, 그 정보로 쌍대변수를 최소량만큼 조정해 새 간선을 등식 부분그래프에 편입시킨다. 즉 비가중 매칭(원 문제)과 쌍대변수 갱신(쌍대 문제)을 번갈아 돌리는 원-쌍대 알고리즘이며, 상보 여유 조건이 만족되는 순간 최적성이 증명된다. 표준 구현이 $O(n^3)$ , 희소 그래프에서는 다익스트라 기반 연속 최단경로 방식이 더 낫다. 이름은 헝가리 수학자 쾨니그와 에게르바리의 결과에 빚졌다고 해서 쿤이 직접 붙였다.⁴

대안으로 베르트세카스의 경매(auction) 알고리즘 — 일꾼이 작업에 입찰하고 가격이 오르는 과정이 그대로 쌍대변수 상승이다 — 과, 최소비용 흐름 솔버를 그냥 부르는 방법이 있다. 문제 규모가 크면 후자가 무난하다.

7. 공학·수치해석에서의 접점[편집]

매칭은 알고리즘 교과서 안에만 사는 물건이 아니다. 수치해석 스택 곳곳에 박혀 있다.

희소 LU의 최대 대각 전치 — 희소행렬을 LU 분해하기 전에 행을 재배열해 대각에 0이 아닌 원소를 앉히는 작업은, 행을 $L$ ·열을 $R$ 로 두고 0 아닌 성분을 간선으로 하는 이분 그래프의 완전 매칭을 찾는 것이다. 여기에 “대각 원소 곱을 최대화”라는 가중을 얹으면 배정 문제가 되고, 이게 MC64류 정적 피벗팅 전처리다. 비대칭 희소 직접법 솔버가 조용히 돌리고 있는 계산.
다단계 그래프 분할의 코스닝 — METIS가 정점을 짝지어 초정점으로 합칠 때 쓰는 heavy edge matching이 바로 (극대) 매칭이다. 최대 매칭까지 갈 필요가 없어 그리디 극대 매칭으로 때우지만, 개념은 동일하다. 그래프 분할 참고.
대수적 다중격자의 응집 — 강한 결합끼리 짝짓는 pairwise aggregation도 매칭이다. 다중격자법의 조대 격자를 대수적으로 만드는 방법 중 하나.
다중 객체 추적 — 프레임마다 검출된 물체와 기존 궤적을 잇는 문제가 전형적인 배정 문제다. 비용은 예측 위치와의 거리나 외형 유사도이고, 실시간 추적기 상당수가 프레임당 헝가리안을 돌린다. 칼만 필터의 예측을 비용으로 쓰는 조합이 국룰.
자원 배정 일반 — 승무원·기계·GPU 스케줄링, 광고 노출 배분, 조합 최적화 모델의 부분구조. 매칭 부분이 TU라서 정수계획법 모델 안에 들어가도 완화가 잘 조여지는 편이다.

한계도 분명하다. 짝을 셋 이상 묶는 3차원 매칭은 NP-완전이고, 각 정점이 여러 개를 받을 수 있는 $b$ -매칭이나 선호 순위가 있는 안정 결혼 문제는 목적함수 자체가 달라 별도의 이론이 필요하다. “매칭은 다항시간”이라는 인상은 어디까지나 이분 + 1대1 + 선형 비용이라는 좁은 울타리 안에서만 참이다.

8. 관련 문서[편집]

반대로 말하면 “이분”이라는 조건이 빠지는 순간 세상이 험해진다. 최대 매칭은 일반 그래프에서도 다항시간이지만, 쾨니그 정리는 깨지고, 최대 독립집합은 NP-난해로 올라가며, 3차원으로 확장하면 완전히 손을 든다. 이분 그래프는 조합 최적화에서 몇 안 되는 안전지대다. ↩
미칼리-바지라니 알고리즘은 발표 후 정확성 증명이 완성되기까지 20년 넘게 걸렸다는 전설이 따라다닌다. 구현체를 인터넷에서 찾기 어려운 이유이기도 하고, 실무에서 일반 매칭이 필요하면 대개 $O(V^3)$ 짜리 블로섬을 그냥 쓴다. ↩
홀의 정리가 “결혼정리”라 불리는 것은 원래 서술이 “남자 집합의 어느 부분집합을 잡아도 그들이 아는 여자 수가 그 이상이면 모두 결혼시킬 수 있다”였기 때문이다. 1935년 논문의 서술이라는 점을 감안해도 예시 선정이 요즘 기준으로는 고풍스럽다. ↩
쿤 본인이 나중에 밝힌 바에 따르면, 야코비가 19세기에 사실상 같은 방법을 라틴어 유고로 남겼다는 사실이 뒤늦게 발견됐다. 이 분야에서 “누가 먼저 했나”를 따지기 시작하면 대개 200년 전 누군가가 이미 해 놨다는 결론에 도달한다. ↩