Prim 알고리즘

Minimum Spanning Tree 문제를 풀기 위한 알고리즘.

 * 구조

1. 최초에 하나의 node를 tree인 T에 추가.

2. 현재 tree에 인접한 edge중 가장 작은 가중치를 가진 edge를 T에 추가,(단, 그 edge는 사이클을 만들지 않음)

3. 모든 node를 추가할 때까지 2를 반복.

 * 증명

- 알고리즘이 MST문제를 정확히 풀어내는지 증명.

- 알고리즘이 만들어낸 tree가 Spanning tree인지 증명한 후, 그 tree가 minimum tree임을 증명.

1. Spanning tree를 만든다.

- 알고리즘은 매번 edge를 추가할 수 있다. (입력이 connected graph임을 가정했음)

- 알고리즘이 매번 edge를 추가할 때 마다, T는 tree임을 유지, 즉, tree의 정의 ( undirected, acyclic, connected graph )를 계속 만족함.

2. Minimum tree가 된다.

- 정답이 하나라고 가정. (즉, 같은 비용인데 다른 edge를 가지고있는 정답이 없음.)

- 정답 tree를 Tmst라고 하면, 알고리즘의 모든 단계에서 T ⊂ Tmst 가 된다.

- 따라서 알고리즘이 종료되면 T = Tmst가 된다. ( 어떤 tree에 속한 tree인데 edge의 수가 같다면 두 tree는 동일한 tree이다.)

* 2번의 "알고리즘의 모든 단계에서 T ⊂ Tmst 가 된다."를 증명하기 위해, 수학적 귀납법 사용

base) 최초에 T ⊂ Tmst 이다. (노드가 하나밖에 없으므로 포함관계 성립)

step) 알고리즘이 T에 edge인 uv를 추가해서 T'가 됬다고 하자. ( T' = T ∪ {uv} )

이 때 T' ⊂ Tmst가 된다.

* step의 " T' ⊂ Tmst "를 증명하기 위해, 귀류법 사용.

- T'가 Tmst에 포함되지 않는다면, uv 또한 Tmst에 포함되지 않는다.

( T와 T'의 차이는 uv 뿐이므로 )

- Tmst ∪ {uv} 는 cycle을 가진다. 

(왜냐하면 Tmst는 Spanning tree인데, 거기에 edge를 추가한 상황이기 때문에 반드시 cycle을 가지게 된다.)

- 그 cycle은 uv를 포함하고 있지만, 그 cycle의 모든 edge가 T에 포함된 것은 아니다. (uv는 알고리즘이 선택한 edge이기 때문에.)

- 만들어진 cycle중에서 T에 포함되지 않는 edge를 ab라 하자. 

그리고 Tmst에서 ab를 제거하고 uv를 추가한 tree를 T''이라 하자.

- ab는 uv보다 weight가 더 크다.. 왜냐하면 알고리즘이 T에 uv를 추가했기 때문이다.(알고리즘은 최소 weight를 가진 edge를 추가한다.)   

- 따라서 T''은 Tmst보다 더 작은 weight를 보유한 정답이다. 하지만 Tmst는 유일한 정답이다. 따라서 모순이 생겼다.

모순이 생겼으므로 가정은 거짓이다.

그래서 step의 T' ⊂ Tmst 는 참이다.

따라서 알고리즘은 정확히 동작함을 증명하였다.