MST : Prim 증명

0. MST란?

- spanning tree : n개의 노드가 있을때, n-1개의 간선으로 만드는 connected graph. (모든 노드를 방문하지만 cycle이 없어야 하므로 간선의 개수는 n-1개이다.)

- Minimum Spanning Tree : 간선의 가중치의 합이 최소가 된다. 

 

1. Prim 알고리즘

임의의 시작 노드에서 출발. (트리의 첫 노드)

트리에 인접한 엣지들 중에서 가장 작은 weight를 선택한다. 

Spanning Tree가 될때까지 반복한다. (간선이 n-1개가 될때 까지)

 

이렇게 Prim 알고리즘을 따라서 완성한 tree의 가중치를 모두 더하면, 그 합이 최소임을 보장한다는 것이다. 

 

2. 정확성 증명

정답 MST 중에 하나의 정답 트리를 Tmst라고 해보자. 

우리 알고리즘이 만들어 나가고 있는 과정의 트리를 A라고 해보자. 

(Tmst에서 새로운 간선 {e}를 추가하면 항상 사이클이 생긴다. Tmst의 간선은 n-1개 여야 하기 때문이다.)

 

A가 Prim 알고리즘에 따라 트리를 완성해나가고 있는 도중에, 인접 노드의 간선 e와 e' 중에서 선택하는 과정을 보고 있다고 해보자. 이때, Tmst에 속하는 정답은 e인데, A가 e'를 선택했다고 해보자. 

=> e'을 선택하는 과정이 존재하지 않으므로 (Tmst에 어긋나는 과정 {e'} !⊆ Tmst), A는 Tmst를 따라 트리를 잘 구성해 나간다고 보일 것이다. 

 

Case 1. w(e) < w(e') 인 경우 -> A가 prim 알고리즘에 따라서 엣지들을 선택했다는 과정에 모순이 생긴다. (e와 e'은 모두 인접노드에 대한 간선이므로 동시 고려 대상이었음이 분명하다.)

 

Case 2. w(e) > w(e') 인 경우 -> Tmst가 정답이었다는 것이 모순이다. Tmst - {e} + {e'}을 한다면, 분명히 Tmst보다 더 minimum한 값이 나온다. 

 

Case 3. w(e) = w(e') 인 경우 -> Tmst - {e'} + {e} 도 여전히 Tmst이다. 엣지를 바꾸면 된다. Tmst도 여전히 답이고, A도 모순이 생기지 않았다. (?! 누군가의 동의가 필요하다.)

 

3. 구현 및 성능

T <- Empty Set이라고 하자. 

U <- {1} : 트리에 들어간 노드들의 집합. 

while (U != V) do

- 가중치가 가장 작은 간선 선택 -> 우선순위 큐로 구현 : O (2mlogn) => 모든 엣지들이 두 번 들어왔다가 나간다. 

- uv를 T에 추가 (들어간 노드인지 확인 -> 2N)

- v를 U에 추가

 

아직 구현 및 성능이 제대로 O(2mlogn)을 잘 모르겠다. .. 구현 코드를 보러가자.