최소 신장 트리

수치해석 계산물리 마지막 수정: 2026-08-23 04:36:52

1. 개요[편집]

최소 신장 트리 Minimum Spanning Tree (MST)
입력	연결 무향 가중 그래프
출력	모든 정점을 잇는 최소 가중치 트리 ($V-1$ 간선)
정당성	컷 속성 · 사이클 속성
고전 알고리즘	보루브카(1926) · 크러스컬(1956) · 프림(1957)
최선 복잡도	결정적 $O(E\,\alpha(E,V))$ · 무작위 기대 $O(E)$
기하 버전	유클리드 MST $\subset$ 들로네 삼각분할

모든 마을에 전기를 넣되 전선은 최소로. 1926년 모라비아에서 시작된 이 질문이 아직도 안 늙었다.

최소 신장 트리(minimum spanning tree, MST)는 연결된 무향 가중 그래프에서 모든 정점을 연결하면서 간선 가중치의 합이 최소가 되는 부분그래프다. 사이클이 있으면 간선 하나를 빼도 여전히 연결되므로 최적해는 반드시 트리이고, 정점이 $V$ 개면 간선은 정확히 $V-1$ 개다.

MST가 알고리즘 교과서의 단골인 이유는 탐욕(greedy)이 정말로 최적해를 주는 드문 문제이기 때문이다. 게다가 그 정당성이 매트로이드 이론으로 깔끔하게 설명된다. 하지만 이 위키가 MST를 다루는 이유는 따로 있다 — 점군의 들로네 삼각분할 부분집합이라는 기하적 사실, 단일 연결 군집화와의 완전한 동치, 그리고 무질서계의 침투 현상이 프림 알고리즘 그 자체라는 물리 쪽 얼굴 때문이다.

2. 컷 속성과 사이클 속성[편집]

거의 모든 MST 알고리즘은 두 가지 사실만으로 정당화된다.

컷 속성(cut property). 정점을 두 덩어리로 가르는 임의의 컷 $(S, V\setminus S)$ 에 대해, 컷을 가로지르는 간선 중 가중치가 최소인 것은 어떤 MST에 반드시 들어간다. 유일하게 최소면 모든 MST에 들어간다. 증명은 교환 논법 한 줄이다 — 그 간선 $e$ 를 안 쓰는 신장 트리 $T$ 에 $e$ 를 더하면 사이클이 생기고, 그 사이클은 컷을 홀수 번 가로지르므로 $e$ 말고도 컷을 가로지르는 간선 $f$ 를 포함한다. $f$ 를 빼고 $e$ 를 넣으면 여전히 신장 트리이고 가중치는 늘지 않는다.

사이클 속성(cycle property). 임의의 사이클에서 가중치가 최대인 간선은 (유일하게 최대라면) 어떤 MST에도 들어가지 않는다. 컷 속성의 쌍대다.

두 속성을 뒤집어 읽으면 알고리즘 설계가 된다. 컷 속성 = 안전한 간선을 넣어라(프림·보루브카), 사이클 속성 = 위험한 간선을 빼라(역-삭제법). 크러스컬은 둘 다로 읽힌다. 이 구조가 매트로이드의 탐욕 최적성 정리의 특수 사례이며, “탐욕이 통하는 문제”의 원형으로 인용된다.

3. 세 가지 고전 알고리즘[편집]

보루브카(Otakar Borůvka, 1926)가 가장 오래됐다. 모라비아 지역 전력망 설계 의뢰에서 나온 알고리즘이라는, 응용수학의 교과서 같은 출생 배경을 가졌다.¹ 각 라운드에서 모든 연결 성분이 동시에 자기에게 가장 싼 인접 간선을 고른다. 컷 속성에 의해 전부 안전하고, 성분 수가 매 라운드 최소 절반으로 줄므로 라운드는 $O(\log V)$ , 총 $O(E\log V)$ . 성분마다 독립이라 본질적으로 병렬이어서, GPU·분산 MST 구현의 뼈대는 대부분 보루브카다. 단 가중치에 동점이 있으면 서로를 고르다 사이클이 생길 수 있으므로 (간선 번호 같은) 전순서 동점 처리가 필수다.

크러스컬(1956)은 간선을 가중치 오름차순으로 정렬해 놓고, 사이클을 만들지 않는 것만 차례로 채택한다. “사이클을 만드는가”를 판정하는 것이 분리 집합(union-find) 자료구조이며, 랭크 합치기 + 경로 압축을 쓰면 연산당 상각 $O(\alpha(n))$ — 사실상 상수 — 이라² 전체 비용은 정렬이 지배해 $O(E\log E) = O(E\log V)$ 다. 간선이 이미 정렬돼 있거나 가중치가 작은 정수라면 $O(E\,\alpha)$ 로 떨어진다.

프림(1957, 그전에 야르니크 1930, 그다음 다익스트라 1959가 독립 재발견)은 한 정점에서 시작해 트리를 한 간선씩 키운다. 코드가 다익스트라 알고리즘과 거의 글자 단위로 같고, 차이는 완화식뿐이다.

\text{다익스트라: } d[v] \leftarrow \min\big(d[v],\ d[u] + w(u,v)\big) \qquad \text{프림: } d[v] \leftarrow \min\big(d[v],\ w(u,v)\big)

“시작점에서의 거리”를 “트리에서의 거리”로 바꾼 것이 전부다. 그래서 복잡도표도 통째로 공유한다 — 우선순위 큐를 이진 힙으로 하면 $O(E\log V)$ , 피보나치 힙이면 $O(E + V\log V)$ , 조밀 그래프에서 큐 없이 배열로 하면 $O(V^2)$ .

이론적 한계는 아직 열려 있다. 샤젤(2000)이 소프트 힙으로 결정적 $O(E\,\alpha(E,V))$ 를 얻었고, 카거-클라인-타잔(1995)은 무작위화로 기대 선형 시간을 달성했다. 페티-라마찬드란(2002)은 “최적인 알고리즘”을 제시했는데, 정작 그 알고리즘의 복잡도가 무엇인지는 모른다. 반면 주어진 트리가 MST인지 검증하는 것은 결정적 선형 시간에 된다는 것이 알려져 있다.

4. 유일성[편집]

가중치가 전부 서로 다르면 MST는 유일하다. (동점이 있어도 유일할 수 있으니 역은 성립하지 않는다.) 정확한 판정 기준은 이렇다 — 신장 트리 $T$ 가 유일한 MST일 필요충분조건은, 트리에 없는 모든 간선 $e=(u,v)$ 가 $T$ 위의 $u \to v$ 경로에 있는 모든 간선보다 엄격히 무거운 것이다. 하나라도 같으면 교환해서 같은 가중치의 다른 MST를 만들 수 있다.

실무적으로 이건 꽤 중요하다. 좌표에서 계산한 유클리드 거리처럼 부동소수 가중치는 동점이 사실상 안 생기므로 유일성이 보장되지만, 격자 위 정수 가중치나 이산 비용 모델에서는 동점이 흔하고 구현·컴파일러·정렬 안정성에 따라 결과 트리가 달라진다. 재현성이 필요하면 (가중치, 간선 인덱스) 사전식으로 전순서를 강제하는 것이 국룰이다.

5. 유클리드 MST와 들로네 삼각분할[편집]

평면 위 점 $n$ 개에 대해 모든 쌍을 간선으로 놓고 MST를 구하는 것이 유클리드 MST(EMST)다. 소박하게 하면 간선이 $\binom{n}{2}$ 개라 $O(n^2\log n)$ 인데, 다음 사실이 판을 뒤집는다.

\text{EMST}(P) \subseteq \text{Delaunay}(P)

증명은 컷 속성과 들로네의 빈 원 성질을 붙이면 된다. MST에 들어가는 간선 $pq$ 를 잡고 $pq$ 를 지름으로 하는 원을 그리자. 그 원 안에 다른 점 $r$ 이 있다면 $|pr|$ 과 $|rq|$ 가 둘 다 $|pq|$ 보다 짧아, $pq$ 가 만드는 사이클에서 $pq$ 가 최대가 되므로 사이클 속성에 걸려 MST에 못 들어간다. 따라서 그 원은 비어 있고, 빈 원을 갖는 간선은 정의상 들로네 간선이다.

들로네 삼각분할의 간선은 평면에서 $O(n)$ 개뿐이므로, 삼각분할 $O(n\log n)$ + 그 위의 MST $O(n\log n)$ = 전체 $O(n\log n)$ 으로 끝난다. 이 사실 때문에 점군 처리 파이프라인에서 EMST는 사실상 공짜 부산물 취급을 받는다.

차원이 올라가면 이 지름길이 막힌다. $d$ 차원 들로네의 크기가 최악 $\Theta(n^{\lceil d/2 \rceil})$ 까지 커지기 때문이다. 그래서 고차원에서는 잘 분리된 쌍 분해(WSPD)나 공간 분할 자료구조 위의 이중트리 보루브카로 후보 간선을 추려 낸다.

6. 단일 연결 군집화와의 동치[편집]

MST와 단일 연결 군집화(single-linkage clustering)는 같은 것의 두 얼굴이다. 단일 연결은 “두 군집 사이 거리를 가장 가까운 원소 쌍의 거리로 정의하고, 가장 가까운 두 군집을 반복해 합치는” 응집형 계층적 군집화인데, 이 합치기 순서가 크러스컬이 간선을 채택하는 순서와 정확히 같다. 결과적으로

MST를 구한 뒤 가장 무거운 간선 $k-1$ 개를 끊으면 정확히 단일 연결 $k$ -군집이 나온다.
덴드로그램의 높이 = MST 간선 가중치. 즉 덴드로그램은 MST를 정렬한 것에 지나지 않는다.

이 동치 덕분에 $O(n^2)$ 짜리 소박한 단일 연결 대신 EMST를 써서 $O(n\log n)$ 에 끝낼 수 있고, 밀도 기반 군집화의 현대적 구현(상호 도달가능 거리 위의 MST를 쓰는 계열)도 같은 뼈대를 쓴다. 단일 연결의 고질병인 체이닝(가느다란 다리 하나로 두 덩어리가 붙어 버리는 현상)도 MST 관점에서 보면 당연하다 — 트리는 다리 하나만 있으면 잇는다. k-평균 군집화가 구형 덩어리를 좋아하는 것과 정확히 반대 성향이다.

7. 침투와 무질서계 — 프림 = 침입 침투[편집]

물리 쪽 얼굴이 여기다. 격자의 각 결합(bond)에 독립 난수 임계값 $t_e$ 를 주고, 한 점에서 시작해 현재 클러스터의 경계 결합 중 임계값이 가장 낮은 것을 매번 하나씩 침입시키는 과정을 침입 침투(invasion percolation, Wilkinson·Willemsen 1983)라 부른다. 그런데 이 규칙은 프림 알고리즘의 정의 그 자체다. 즉 침입 침투 클러스터는 무작위 가중 격자 위에서 프림이 자라는 모습이고, 두 분야가 같은 알고리즘에 서로 다른 이름을 붙여 온 셈이다.³

크러스컬 쪽도 물리적으로 읽힌다. 간선을 가중치 오름차순으로 넣는 과정은 정확히 결합 퍼콜레이션에서 점유 확률 $p$ 를 0에서 1로 올리는 과정이다. $p$ 가 임계점 $p_c$ 를 지날 때 거대 클러스터가 생기고, MST가 그 순간 흡수하는 간선들이 침투 임계 상태의 프랙탈 구조를 물려받는다. 그래서 무질서계 연구에서 MST는 ” $T \to 0$ 극한의 바닥 상태” 부류로 다뤄지고, 그 경로의 프랙탈 차원이 침투 지수와 연결된다. 스핀글라스나 무작위 저항망의 최저 비용 경로 문제에서 MST가 반복해 등장하는 이유다.

무작위 그래프 쪽 결과 하나는 외워 둘 만하다. 완전그래프 $K_n$ 의 각 간선에 독립 균등 $U(0,1)$ 가중치를 주면 MST의 총 가중치가 $n \to \infty$ 에서

\mathbb{E}\big[W(\text{MST})\big] \longrightarrow \zeta(3) = \sum_{k=1}^{\infty} \frac{1}{k^3} \approx 1.202

로 수렴한다(Frieze, 1985). 정점을 아무리 늘려도 총 길이가 상수로 수렴하고, 그 상수가 하필 아페리 상수라는 점이 이 결과의 매력이다.

8. 그 밖의 쓰임[편집]

근사 알고리즘의 재료. MST를 두 번 훑는 오일러 순회로 외판원 문제의 2-근사가 나오고, 홀수차 정점에 최소 완전 매칭을 붙이면 크리스토피데스의 $3/2$ -근사가 된다. 근사 알고리즘 수업의 첫 예제.
슈타이너 트리와의 대비. 새 점을 추가하는 것을 허용하면 총 길이가 더 줄어든다. 유클리드 평면에서 슈타이너 최소 트리 길이가 MST 길이의 $\sqrt{3}/2 \approx 0.866$ 배 밑으로는 내려가지 않는다는 것이 길버트-폴락의 슈타이너 비 추측인데, 1990년대에 나온 증명에 결함이 지적된 뒤로 아직 완전히 정리되지 않았다. 어느 쪽이든 MST가 슈타이너 문제의 손쉬운 상수배 근사라는 사실은 변하지 않는다. MST는 다항식, 슈타이너는 NP-난해라는 차이가 핵심.
영상 분할·미로 생성. 픽셀 격자에 밝기 차이를 가중치로 주고 MST를 자르면 그래프 기반 영상 분할이 되고, 무작위 가중치로 MST를 만들면 완벽한 미로(사이클 없음 + 모든 칸 연결)가 나온다. 게임의 절차적 던전 생성에서 크러스컬·프림 미로가 그대로 쓰인다.
전자기해석의 트리-코트리 게이지. 변 요소(에지 요소) 기반 자기벡터퍼텐셜 정식화는 컬-컬 연산자의 널공간(그래디언트 성분)이 커서 행렬이 특이해진다. 메시 그래프의 신장 트리 위 자유도를 0으로 고정해 게이지를 잡는 것이 트리-코트리 방법이며, 여기서 트리는 꼭 최소일 필요가 없지만 가중치를 잘 주고 MST를 쓰면 결과 행렬의 조건수가 개선되는 것이 보고돼 있다.
네트워크 설계·클러스터 배선. 원래의 응용이 여전히 살아 있다. 다만 현실의 통신망은 고장 대비 이중화가 필요해서 트리가 아니라 2-연결 그래프를 요구하고, 그 순간 문제는 다항식 세계 밖으로 나간다.

9. 관련 문서[편집]

보루브카는 1926년에 체코어로 두 편의 논문을 냈고, 그래프 이론이라는 분야가 성립하기 전이라 용어도 완전히 달랐다. 서방에는 오래 알려지지 않아 이후 30년간 여러 사람이 같은 알고리즘을 재발견했다. 참고로 프림 알고리즘도 야르니크(1930)의 재발견이고, 다익스트라도 1959년 그 두 쪽짜리 논문에서 같이 다뤘다. 이 문제는 재발견 횟수로도 기록을 세운 셈. ↩
$\alpha$ 는 아커만 함수의 역함수라, 우주의 원자 수만큼 원소를 넣어도 4를 안 넘는다. “상수는 아니지만 상수라고 생각해도 인생에 지장 없는” 대표적인 함수. 타잔(1975)이 이 상계를 증명했고, 나중에 프레드먼-사크스가 그것이 하계이기도 함을 보여 분리 집합 문제는 완전히 닫혔다. ↩
엄밀히 말하면 물리에서 말하는 침입 침투에는 “갇힌 영역은 침입할 수 없다”는 트래핑 규칙이 붙은 변종이 있고, 그 경우엔 프림과 갈라진다. 트래핑 없는 표준판이 프림과 일치한다. 어느 쪽이든 지질학에서 물이 기름을 밀어내는 이차 회수(secondary recovery) 모형에서 나온 것이라, 알고리즘 교과서와 석유공학 논문이 같은 그림을 그리고 있다. ↩