블로섬 알고리즘

최적설계 수치해석 마지막 수정: 2026-08-16 04:33:26

1. 개요[편집]

블로섬 알고리즘 Blossom Algorithm
발표	Jack Edmonds (1965), "Paths, Trees, and Flowers"
푸는 문제	일반 그래프의 최대 매칭 (이분 조건 없음)
핵심 장치	홀수 사이클(블로섬) 수축 · 증대 후 전개
복잡도	원논문 $O(V^4)$ → $O(V^3)$ (Gabow 1976) → $O(E\sqrt{V})$ (Micali–Vazirani 1980)
가중 버전	원-쌍대 + 홀수집합 쌍대변수 — Blossom V, LEMON
최소-최대 정리	튜테-베르지 공식
역사적 의의	"good algorithm = 다항시간"이라는 정의의 출발점

블로섬 알고리즘(blossom algorithm)은 이분성 가정 없이 임의의 무향 그래프에서 최대 매칭을 다항시간에 정확히 구하는 알고리즘이다. 1965년 잭 에드먼즈가 논문 Paths, Trees, and Flowers에서 제시했다. 증대 경로 탐색이 홀수 사이클에 걸려 실패하는 현상을 사이클 전체를 하나의 정점으로 수축해 우회하고, 증대가 끝난 뒤 다시 전개해 원래 그래프의 매칭으로 되돌린다. 수축되는 그 홀수 사이클을 꽃봉오리에 빗대어 블로섬(blossom)이라 부르고, 그것이 알고리즘의 이름이 되었다.

이 논문이 조합 최적화에서 갖는 위치는 알고리즘 하나 이상이다. 에드먼즈는 서론에서 “좋은 알고리즘”이란 무엇인지를 명시적으로 논하며 입력 크기의 다항식으로 유계인 연산량을 그 기준으로 제안했다. 코브햄이 비슷한 시기에 같은 주장을 했고, 오늘날 복잡도 계급 $\mathsf P$ 의 개념적 뿌리로 코브햄-에드먼즈 논제라 불린다. 즉 블로섬 알고리즘은 “다항시간이면 효율적”이라는 상식이 처음 문헌에 박히는 순간의 실증 사례였다.¹ 이분 매칭이 왜 그렇게 쉬운지, 그리고 그 쉬움이 어디서 끝나는지를 알려면 이쪽을 봐야 한다.

2. 이분 그래프의 방법이 깨지는 지점[편집]

매칭 알고리즘의 뼈대는 이분 매칭과 동일한 베르주 정리다 — 매칭 $M$ 이 최대인 것과 $M$ -증대 경로(양 끝이 미포화이고 매칭·비매칭 간선이 번갈아 나오는 경로)가 없는 것은 동치다. 이 정리 자체는 일반 그래프에서도 그대로 성립한다. 문제는 증대 경로를 찾는 일이다.

이분 그래프에서는 미포화 정점에서 교대 탐색을 하면 정점의 “짝수 거리/홀수 거리” 구분이 정확히 $X$ / $Y$ 쪽 구분과 맞아떨어져, 한 정점이 두 신분을 동시에 가질 일이 없다. 홀수 사이클이 존재하면 이 대응이 무너진다. 탐색 트리에서 뿌리로부터 짝수 길이 교대 경로로 닿는 정점을 바깥(outer), 홀수 길이로 닿는 정점을 안쪽(inner)이라 하면, 홀수 사이클 위의 정점은 도는 방향에 따라 바깥이 되기도 하고 안쪽이 되기도 한다.

여섯 개의 정점이면 사고를 재현할 수 있다. 정점 $r, p, a, b, c, d$ 에 간선 $rp,\ pa,\ ab,\ bc,\ ca,\ cd$ 를 두고 매칭을 $\{pa,\ bc\}$ 라 하자. 미포화 정점은 $r$ 과 $d$ 뿐이고, 증대 경로는 $r - p - a - b - c - d$ 로 멀쩡히 존재한다. 그런데 $r$ 에서 탐색을 시작해 $r \to p \to a$ 까지 온 뒤 삼각형 $abc$ 를 $c$ 쪽으로 먼저 돌면, $c$ 는 홀수 거리(안쪽)로, $b$ 는 짝수 거리(바깥)로 굳은 채 막다른 길에 닿는다. 정점마다 신분을 하나만 기록하는 구현은 되돌아와 $a \to b$ 를 시도할 때 “ $b$ 는 이미 봤다”며 건너뛰고 증대 경로가 없다고 보고한다. 정답 경로에서는 $b$ 가 안쪽, $c$ 가 바깥이어야 하니, 같은 정점이 방향에 따라 두 신분을 모두 가져야 한다는 것이 문제의 본질이다. 이것이 일반 그래프 매칭이 1965년까지 미해결로 남아 있던 이유다.

3. 블로섬 — 수축과 전개[편집]

에드먼즈의 정의부터 보자. 탐색 중 바깥 정점 두 개를 잇는 간선이 발견되면, 두 정점의 트리 경로를 합쳐 길이 $2k+1$ 의 홀수 사이클이 만들어진다. 이 사이클은 매칭 간선 $k$ 개를 포함하고 정확히 한 정점만 사이클 안에서 짝이 없는데, 이 정점을 사이클의 밑동(base)이라 한다. 이런 홀수 사이클이 블로섬이다.

블로섬의 결정적 성질은 밑동에서 사이클 위 어느 정점으로든 짝수 길이 교대 경로가 존재한다는 것이다. 시계 방향과 반시계 방향 중 한쪽은 반드시 짝수 길이이기 때문이다. 그래서 블로섬 안의 정점들은 바깥에서 볼 때 전부 동등하다 — 어느 것을 경유하든 짝수 걸음으로 오갈 수 있으므로 구별할 이유가 없다. 여기서 알고리즘이 나온다.

수축 보조정리. $B$ 가 $M$ 에 대한 블로섬일 때, $G$ 에 $M$ -증대 경로가 존재할 필요충분조건은 수축 그래프 $G/B$ 에 $M/B$ -증대 경로가 존재하는 것이다.

$\Rightarrow$ 방향은 원래 경로를 $B$ 를 지날 때 초정점 하나로 접으면 되고, $\Leftarrow$ 방향이 위 성질을 쓴다. $G/B$ 의 증대 경로가 초정점 $b$ 를 지난다면, $b$ 로 들어온 간선의 원래 끝점에서 밑동까지 사이클을 짝수 쪽으로 돌아 나가면 $G$ 의 교대 경로가 복원된다. 이 복원이 곧 전개(lift)다.

블로섬을 계속 수축하면 홀수 사이클이 사라진 그래프가 남고, 거기서 찾은 증대 경로를 역순으로 전개해 원래 그래프의 증대 경로를 얻는다. 전체 절차는 다음과 같다.

미포화 정점 하나를 뿌리로 교대 탐색을 시작한다(교대 포리스트를 키운다).
바깥 정점 두 개가 서로 다른 트리에 있고 간선으로 이어지면 → 증대 경로 발견. 증대하고 처음부터 다시.
바깥 정점 두 개가 같은 트리에 있고 간선으로 이어지면 → 블로섬 발견. 수축하고 탐색을 이어 간다.
더 확장할 수 없으면 그 뿌리에서는 증대 경로가 없다. 다음 미포화 정점으로 넘어간다.

수축된 상태에서 찾은 증대 경로를 전개해 실제 매칭에 반영하는 것이 마지막 단계다. 각 증대마다 매칭이 1 늘고 증대는 최대 $V/2$ 번이므로 종료는 보장된다.

에드먼즈 블로섬으로 일반 그래프의 최대 매칭을 푼다 — 짝수–짝수 간선을 만나면 그 홀수 사이클을 base 한 점으로 접고(보라색 무리), 증대경로를 찾은 뒤 접힌 안쪽까지 전개해 매칭을 뒤집는다. 기본 인스턴스는 정점 15·간선 21에서 축약 4회·증대 7회로 매칭 크기 7에 도달하며, 부분집합 완전열거로 구한 최대매칭 7과 일치한다. 같은 탐색에서 축약만 끄면 6에서 멈춘다.

한 가지 강조할 점. 수축은 탐색을 위한 임시 조작이지 그래프의 근사가 아니다. 전개 과정이 원래 그래프에서 유효한 교대 경로를 정확히 복원하므로 결과는 근사해가 아니라 최적해다. 구현에서 버그가 가장 많이 나오는 곳도 이 전개 부분이고, 중첩 블로섬(블로섬 안에 블로섬)을 만나면 자료구조가 급격히 지저분해진다.

4. 복잡도와 구현[편집]

에드먼즈의 원논문 분석은 $O(V^4)$ 수준이었다. 이후 정리된 결과는 다음과 같다.

알고리즘	복잡도	비고
에드먼즈 원논문 (1965)	$O(V^4)$	개념적 원형
가보우 (1976) 등 정리된 구현	$O(V^3)$	실무에서 흔히 쓰는 기준선
미칼리-바지라니 (1980)	$O(E\sqrt{V})$	이론상 최선급, 구현 난이도 악명

$O(E\sqrt V)$ 는 이분 그래프의 홉크로프트-카프와 같은 차수다. 즉 일반 그래프 매칭은 점근적으로 이분 매칭과 같은 값에 도달했다. 다만 미칼리-바지라니는 층별 탐색 안에서 블로섬을 다뤄야 해 정확성 증명과 구현 모두 훨씬 어렵고, 실무에서 일반 매칭이 필요하면 $O(V^3)$ 짜리 블로섬을 그냥 쓰는 것이 보통이다. 매칭 크기가 수천 정도면 그 차이는 체감되지 않는다.

라이브러리로는 C++의 LEMON(최대 매칭·가중 매칭·완전 매칭 전부 제공), 최소비용 완전 매칭 전용의 Blossom V(콜모고로프, 2009), 파이썬의 NetworkX max_weight_matching이 사실상 표준이다. 직접 구현할 이유는 대회 코드 말고는 거의 없다.²

5. 가중 매칭과 매칭 다면체[편집]

간선에 가중치가 붙으면 이야기가 더 깊어진다. 매칭의 특성벡터들이 만드는 볼록포를 매칭 다면체라 하는데, 이분 그래프에서는

x \ge 0, \qquad \sum_{e \ni v} x_e \le 1 \ \ \forall v

만으로 다면체가 완전히 기술된다(전체 단모듈성). 일반 그래프에서는 이것으로 부족하다 — 삼각형에 $x_e = \tfrac12$ 씩 주면 위 제약을 만족하면서 목적값 $\tfrac32$ 가 나오는데, 실제 최대 매칭은 1이다. 에드먼즈(1965)의 매칭 다면체 정리는 빠진 조각이 홀수 집합 제약임을 밝혔다.

\sum_{e \subseteq U} x_e \;\le\; \frac{|U| - 1}{2} \qquad \forall\, U \subseteq V,\ |U| \text{ 홀수},\ |U| \ge 3

제약의 개수가 지수적이지만, 위반된 제약을 다항시간에 찾아내는 분리 알고리즘이 존재하기 때문에 선형계획법의 타원체법 관점에서 여전히 다항시간이다. 이 “지수개 제약 + 다항시간 분리”라는 구도는 이후 정수계획법의 절단면 방법 전반이 물려받는 설계다.

가중 매칭 알고리즘은 이 제약들에 붙는 쌍대변수 $y_v$ (정점)와 $z_U$ (홀수 집합)를 유지하며 원-쌍대로 움직인다. 헝가리안 알고리즘이 정점 퍼텐셜만 갖고 하던 일에, 블로섬을 수축할 때마다 그 홀수 집합의 $z_U$ 를 하나씩 세워 가며 상보 여유를 유지하는 것으로 이해하면 된다. 최선의 복잡도는 $O(V(E + V\log V))$ 급이며, 최소비용 완전 매칭 쪽의 실전 표준 구현이 앞서 언급한 Blossom V다.

6. 튜테-베르지 공식[편집]

이분 그래프의 쾨니그 정리에 대응하는 일반 그래프의 최소-최대 정리가 튜테-베르지 공식이다. $\mathrm{odd}(H)$ 를 그래프 $H$ 의 홀수 크기 연결성분 개수라 할 때

\nu(G) \;=\; \frac{1}{2}\left(n - \max_{U \subseteq V}\bigl(\mathrm{odd}(G - U) - |U|\bigr)\right)

가 성립한다. 즉 매칭이 완전해지지 못하는 이유는 언제나 **“정점 $U$ 를 떼어냈더니 홀수짜리 조각이 너무 많이 쏟아진 것”**으로 요약된다. 홀수 성분은 내부에서 반드시 한 정점이 남고, 그 정점은 $U$ 쪽에서 짝을 구해야 하는데 $U$ 가 작으면 못 구한다. $\max$ 가 0인 특수 사례가 튜테의 1-인자 정리(1947)이고, 여기에 결함을 정량화해 붙인 것이 베르주(1958)다.

구조는 홀의 결혼정리의 결함형과 똑같다 — 최대 매칭 알고리즘이 끝나면 최적성을 증명하는 **장벽 집합 $U$ **가 함께 나온다. 블로섬 알고리즘의 마지막 탐색이 남긴 바깥 정점·수축된 블로섬 정보로 이 $U$ 를 구성할 수 있고, 그래서 “이보다 큰 매칭은 없다”를 반박 불가능하게 제시할 수 있다.

7. 어디에 쓰이는가[편집]

일반 그래프 매칭은 순수 이론처럼 보이지만, 최소 가중치 완전 매칭이라는 형태로 공학 곳곳에 박혀 있다.

중국 우편배달부 문제. 모든 간선을 최소 비용으로 한 번 이상 지나 출발점으로 돌아오는 경로. 오일러 회로가 존재하지 않는 이유는 홀수 차수 정점 때문이고, 그 정점들끼리 최단거리를 가중치로 하는 완전 그래프에서 최소 가중치 완전 매칭을 찾아 중복 통과할 간선을 정하면 최적해가 된다(에드먼즈-존슨, 1973). 제설차 노선, 검침 경로, 플로터의 펜 이동 최소화가 전부 이 형태다. 중국 우편배달부 문제 참고.
크리스토피데스 알고리즘. 거리 삼각부등식이 성립하는 외판원 문제에서 최적해의 $1.5$ 배 이내를 보장하는 고전적 근사 알고리즘. 최소 신장 트리를 만든 뒤 홀수 차수 정점들에 최소 가중치 완전 매칭을 얹어 오일러 회로를 만들고 지름길로 잘라 낸다. 여기서도 매칭이 정확해여야 근사비 보장이 성립한다 — 근사 알고리즘의 부품이 정확 알고리즘인 드문 사례.
사각 요소 격자 생성. 삼각형 메시 생성 결과를 사각형으로 재조합하는 표준 기법이 삼각형을 정점, 인접한 삼각형 쌍을 간선(가중치 = 합쳤을 때의 품질 저하)으로 두고 최소 가중치 완전 매칭을 푸는 것이다. Gmsh의 Blossom-Quad(2012)가 이 방식이며, 유한요소법에서 사각/육면체 요소가 선호되는 문제(박판 구조, 경계층)에 실제로 쓰인다. 들로네 삼각분할로 만든 삼각 격자가 입력이 되는 경우가 많다.
2차원 스핀글라스의 바닥상태. 자기장이 없는 평면 격자 스핀글라스에서 좌절된 결합을 끊는 최소 비용 집합을 찾는 문제가 쌍대 그래프의 최소 가중치 완전 매칭으로 정확히 환원된다. 이징 모형 계열에서 몬테카를로 방법에 의존하지 않고 바닥상태를 정확히 얻을 수 있는 몇 안 되는 경우이며, 그래서 어닐링 계열 휴리스틱의 정답지로 쓰인다.
양자 오류 정정 디코더. 표면 부호에서 신드롬으로 검출된 결함들을 최소 비용으로 짝지어 오류 사슬을 추정하는 것이 최소 가중치 완전 매칭이다. 실시간 디코더 구현이 Blossom V 계열을 기반으로 출발했고, 지금도 성능 비교의 기준선 역할을 한다. 양자 오류 정정 참고.
이합체 배열(dimer)의 계수. 체커보드 격자를 도미노로 덮는 경우의 수는 완전 매칭의 개수를 세는 문제인데, 이쪽은 매칭을 하나 찾는 것과 난이도가 전혀 다르다. 평면 그래프에서는 캐스틀레인의 파피안 방법으로 다항시간에 세지지만 일반 그래프에서는 $\#\mathsf P$ -완전이다. 찾기는 쉽고 세기는 어렵다는 대비의 교과서적 사례.

반면 격자 조대화 쪽에서는 정확 매칭이 잘 안 쓰인다. METIS의 heavy edge matching이나 다중격자법의 응집(aggregation)은 일반 그래프 매칭이 맞지만, 목적이 근사적 코스닝이라 그리디 극대 매칭으로 충분하고 블로섬을 부를 이유가 없다. 정확한 최대 매칭이 필요한지 극대 매칭으로 되는지를 먼저 따지는 것이 실무에서 첫 판단이다.³

8. 관련 문서[편집]

에드먼즈가 논문에서 “good algorithm”을 논한 방식은 지금 읽어도 신선하다. 그는 유한 종료성만으로는 부족하다는 점을 지적하며, 지수적으로 커지는 절차와 다항식으로 커지는 절차 사이에 개념적 선을 그어야 한다고 주장했다. 그 선이 나중에 $\mathsf P$ 대 $\mathsf{NP}$ 라는 이름을 얻는다. 제목의 flowers가 블로섬이라는 것도 나중에 알면 웃긴 부분. ↩
블로섬을 직접 구현해 보면 왜 라이브러리를 쓰라고 하는지 알게 된다. 중첩 블로섬의 전개 순서를 한 번 틀리면 매칭 크기는 그럴듯한데 간선이 겹치는 결과가 나오고, 작은 그래프에서는 우연히 맞는 답이 나와 테스트를 통과해 버린다. 검증은 반드시 무작위 그래프 수천 개에 대해 완전 탐색 결과와 대조하는 방식으로 해야 한다. ↩
“매칭이 필요하다”는 요구가 들어왔을 때 실제로 최대성이 필요한 경우는 생각보다 적다. 조대화·클러스터링처럼 결과를 다시 반복 처리하는 파이프라인에서는 그리디 극대 매칭이 시간의 몇 분의 일로 거의 같은 품질을 내고, 최적성이 진짜로 요구되는 자리는 근사비 보장이 걸린 곳(크리스토피데스)이나 물리적 정답이 걸린 곳(바닥상태·디코더) 정도다. ↩