최소 신장 트리 (MST) — 정의와 성질

도시들을 도로로 연결하되, 모든 도시가 서로 닿을 수 있게 하면서 공사 비용을 최소로 만들고 싶다. 답의 모양은 무엇일까? 신장 트리(spanning tree) 다.

MST의 정의

가중 무방향 연결 그래프 $G = (V, E, w)$가 주어졌을 때, 최소 신장 트리(Minimum Spanning Tree, MST) 는 다음을 만족하는 간선 부분집합 $T \subseteq E$다. 여기서 “신장(spanning)” 은 정점 집합 $V$를 하나도 빠뜨리지 않고 모두 포함한다는 뜻이다. 즉 MST는 정점 집합은 그대로 둔 채 간선만 고르는 문제다.

조건	의미
모든 정점 연결	$T$만으로 모든 정점 $V$가 서로 도달 가능하다
가중치 최소	$\sum_{e \in T} w(e)$가 모든 정점을 잇는(신장하는) 연결 부분 그래프 중 최소

가중치 부호에 대한 주의: 이 글은 모든 간선의 가중치가 양수라고 가정한다. 위 표는 최소화 범위를 “모든 정점을 잇는 연결 부분 그래프”로 넓게 잡았고, 그 범위에서 음수 간선을 허용하면 최적해가 트리가 아니게 된다. 세 간선의 가중치가 모두 $-1$인 삼각형에서 신장 트리는 어느 두 간선을 골라도 합이 $-2$지만, 세 간선을 다 쓰면 $-3$으로 더 작다. 가중치 $0$인 간선은 “빼면 합이 엄격히 줄어든다”는 아래 논증을 막는다.

표준적인 MST 정의는 최소화 범위를 처음부터 신장 트리로 못 박기 때문에 음수·$0$ 가중치를 그대로 허용한다. 이 글이 범위를 넓게 잡아 두는 것은 “답의 모양이 왜 트리인가”를 전제가 아니라 증명 대상으로 삼기 위해서다.

위 그림에서 회색 선은 그래프의 전체 간선이고, 빨간색 굵은 선이 MST다. MST는 모든 정점을 연결하면서 가중치 합이 최소다. 여기서는 $3 + 4 + 5 + 2 = 14$이다.

연결 전제가 필요한 이유: 그래프가 연결되어 있지 않으면 모든 정점을 잇는 신장 트리 자체가 존재하지 않으므로 MST도 정의되지 않는다. 이때는 각 연결 성분의 MST를 모은 최소 신장 숲(minimum spanning forest) 을 대신 생각한다.

---

MST는 왜 트리(사이클 없음)인가

“최소 비용으로 모든 정점을 연결”이라는 정의에는 트리라는 말이 직접 나오지 않는다. 사이클이 있어도 연결만 되면 답이 될 수 있을 것 같은데, 그렇지 않다.

명제: 모든 간선의 가중치가 양수라면, MST에는 사이클이 존재할 수 없다.

증명 (귀류법): MST $T$에 사이클 $C$가 존재한다고 가정. 사이클 위의 간선 $e$를 임의로 하나 고른다.

• $C$의 다른 간선들이 $e$의 두 끝점을 여전히 연결한다. 따라서 $e$를 빼도 그래프는 연결 상태를 유지한다.
• 간선만 하나 제거했을 뿐 정점은 그대로이므로, $T \setminus \{e\}$는 여전히 모든 정점을 포함한다. 즉 신장(spanning) 조건도 유지된다.
• 가중치가 양수이므로 $w(e) > 0$, 따라서 $T \setminus \{e\}$의 가중치 합은 $T$보다 엄격히 작다.

이는 $T$가 최소라는 가정에 모순이다. 따라서 MST에는 사이클이 없다. 즉 MST는 트리다.

참고 (사이클 속성, cycle property): 최소화 범위를 신장 트리로 좁히면 가중치 부호와 무관하게 성립하는 성질이 하나 있다. 어떤 사이클 $C$에서 가중치가 유일한 최대인 간선 $e$는 어떤 MST에도 들어가지 않는다. MST가 $e$를 가졌다면 $e$를 빼서 트리가 두 덩어리로 갈라지는데, $C$에서 $e$를 뺀 길이 그 두 덩어리를 다시 잇는다. 그 길 위에는 두 덩어리를 잇는 간선이 있고 $e$가 $C$의 유일한 최대이므로 그 간선은 $e$보다 가볍다. 바꿔 끼우면 더 가벼운 신장 트리가 나와 모순이다. 최대가 동률이면 결론이 “$e$를 쓰지 않는 MST가 존재한다”까지로 약해진다. 다음 글에서 다룰 Kruskal 알고리즘의 정당성이 이 성질과 짝을 이룬다.

---

정확히 $n-1$개의 간선

정점이 $|V| = n$개인 그래프를 트리로 연결하려면 간선이 정확히 몇 개 필요할까?

명제: $n$개의 정점을 가진 트리는 정확히 $n - 1$개의 간선을 가진다.

증명 (수학적 귀납법):

• 기초 ($n = 1$): 정점이 하나뿐이라면 간선도 필요 없다. $1 - 1 = 0$. 성립.

• 귀납 단계: 정점 $n - 1$개인 트리가 $n - 2$개의 간선을 가진다고 가정 (귀납 가정). 정점 $n$개인 트리 $T$에서 리프(leaf), 즉 차수 1인 정점과 그에 붙은 간선을 함께 제거하면, 정점 $n - 1$개·간선 $|E(T)| - 1$개의 트리가 된다. 귀납 가정에 의해 $|E(T)| - 1 = n - 2$, 즉 $|E(T)| = n - 1$이다.

  여기서 “리프가 존재한다”는 사실이 쓰였다. 정점이 2개 이상인 모든 유한 트리에는 리프가 적어도 하나 있다. (가장 긴 경로의 양 끝 정점은 차수가 1일 수밖에 없기 때문이다. 만약 끝 정점의 차수가 2 이상이면 경로를 더 늘릴 수 있어 “가장 긴 경로”라는 가정에 모순이다.)

이 명제의 주어는 트리다. 연결만 요구한다면 간선은 $n - 1$개 이상이면 되고, 정확히 $n-1$개는 그 하한을 채운 경우다. 양수 가중치에서는 하한을 채우는 쪽이 언제나 이득이므로, $|V| = n$인 그래프에서 MST를 찾는다는 것은 $|E|$개의 간선 중 $n - 1$개를 잘 골라 모든 정점을 연결하는 것과 같다.

---

MST는 유일하지 않을 수 있다

같은 그래프에서 MST가 여러 개 존재할 수 있다. 가중치가 같은 간선들이 있을 때, 그중 어느 것을 선택해도 총합이 같다면 그렇다.

위 그림의 두 MST는 서로 다른 간선 집합이지만 가중치 합이 같다 (둘 다 4). 둘 다 정답이다.

반대로, 모든 간선의 가중치가 서로 다르다면 MST는 유일하다는 사실이 알려져 있다.

---

무차별 대입은 왜 비효율적인가

$m$개의 간선 중 $n - 1$개를 고르는 모든 조합을 시도하고, 각각이 신장 트리인지(연결 + 사이클 없음) 확인한 뒤 최소 가중치를 찾으면 답을 얻을 수 있다. 시도해야 할 조합 수는 다음과 같다.

$$\binom{m}{n-1}$$

이 수는 $m$과 $n$이 조금만 커져도 폭발한다. 예를 들어 $n = 20$, $m = 50$이면:

$$\binom{50}{19} = 30{,}405{,}943{,}383{,}200 \approx 3.0 \times 10^{13}$$

게다가 조합 하나하나가 곧바로 답인 것도 아니다. 각 조합마다 그것이 정말 모든 정점을 잇는 신장 트리인지(연결 + 사이클 없음)를 따로 검사해야 하므로, 조합 수 폭발 위에 검사 비용까지 더해진다. 30조 번의 검사는 실용적이지 못하다. 더 영리한 알고리즘이 필요하다.

대표적인 예가 Prim 알고리즘과 Kruskal 알고리즘이다. 둘 다 그리디 전략으로 MST를 직접 구성해 나가지만 관점이 다르다. Prim은 한 정점에서 시작해 연결된 정점 집합을 한 개씩 키워 가고, Kruskal은 간선을 가벼운 순서대로 훑으면서 사이클을 만들지 않는 간선만 골라 모은다.