Kruskal 알고리즘

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

 * 구조

1. 그래프의 각 node를 각각 하나의 node를 가진 tree로 만든다.

2. 모든 edge중 cycle을 만들지 않는 가장 작은 edge를 T에 추가한다.

3. 모든 edge를 볼 때까지 2를 반복한다.

(여기서 T는 edge의 집합이다.)

 * 증명

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

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

1. Spanning tree를 만든다.

- T에 포함된 edge의 개수는 n-1보다 같거나 작다. ( node의 개수와 같거나 더 많으면 반드시 cycle이 생긴다. )

- weight가 적은 edge부터 cycle을 만들지 않는 모든 edge를 추가하므로, 연결되지 않은 node가 있을 수 없다.

2. Minimum tree가 된다.

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

- 정답 tree를 만드는 edge의 집합을 Tmst라고 하면, 알고리즘의 모든 단계에서 T ⊂ Tmst 가 된다.

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

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

base) 최초에 T는 공집합이다. 

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

이 때 T' ⊂ Tmst가 된다.

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

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

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

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

(왜냐하면 Tmst에 e를 추가하면 총 n개가 되기 때문이다. n개의 node에 n개의 edge를 가진 그래프는 cycle이 존재한다.)

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

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

그리고 Tmst에서 f를 제거하고 e를 추가한 집합을 T''이라 하자.

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

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

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

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

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