최소신장트리(Minimum Spanning Tree)

최초작성일 [2020.01.27]

Minimum Spanning Tree

어떤 그래프를 트리로 간주하기 위해서는 아래의 조건을 만족해야 한다.

• 방향없는 그래프여야 한다.

• 모든 정점이 연결되어 있어야 한다. (적어도 |V| - 1개 이상의 간선이 있어야 한다.)

• 사이클이 없어야 한다. (두 정점 사이의 경로는 딱 1개만 있어야 한다.)

최소신장트리(Minimum Spanning Tree)란

1. 그래프 내 모든 정점을 포함하고

2. 그래프 내 모든 정점이 연결되어 있으며

3. 임의의 두 정점 사이의 거리를 최소로 하고

4. 위 트리의 조건을 만족하는

그래프를 의미한다. 어떤 그래프에서 최소신장트리를 찾기 위해 쓰는 대표적인 알고리즘은 크루스칼(Kruskal알고리즘)과 프림(Prim)알고리즘이다.

Cut property

• V : 그래프 내 모든 정점

• E : 그래프 내 모든 간선

• G : V와 E로 이뤄진 그래프

• X : G에서 찾은 최소신장트리 T에 포함된 정점들

이라고 하고 X를 상호배타적인 두 부분집합으로 나누었을 때 두 집합을 각각 S, V-S 라고 하자.

가중치가 제일 작은 간선 e가 두 부분집합 S와 V-S를 연결한다면 X + e 또한 MST의 정점들이라고 할 수 있다. (이 때의 MST는 T와 다를 수 있다.) 이를 cut property라고 한다.

증명

간선 e가 T에 포함되어 있지 않은 상태에서 S 와 V-S를 연결하는 간선 e'가 있고

weight(e) < weight(e')

라고 하자.

e를 T에 추가하면 사이클이 생겨서 T는 MST 조건을 만족하지 못할 것이다. e의 가중치가 e'의 가중치보다 작으므로 e'를 T에서 제거하고 e를 추가하는 게 최적이므로 T + e 또한 MST를 만족한다고 볼 수 있다.

출처

• ratsgo - MST
• coursera - Algorithm on Graphs