프림 알고리즘 증명 Prim's Algorithm Proof

그리디 알고리즘은 매 순간 최적의 결과만 추구하기 때문에 최종적으로 얻게 되는 결과가 최적의 결과인지는 알 수 없다.

그렇기 때문에 그리디 알고리즘은 최적의 결과인지 판단하는 것이 필요하다.

 

프림 알고리즘 역시 그리디 알고리즘에 속한다.

그러므로 프림 알고리즘을 통해서 얻는 결과가 최적 결과인지 확신할 수 없다. 

그런데 프림 알고리즘 결과는 항상 최적의 결과라고한다. 이를 증명하는 법을 알아보자.

 

G는 가중치가 있고 방향성이 없는 그래프이다.

이는 전체 정점 V와 전체 간선 E로 이루어져있다.

 

F는 방문한 간선이다. F는 E에 속한다. 

Y는 V에 속하면서 간선 F를 통해 방문 했던 정점들이다. 

그래서 G = (V,E) 이고 F ⊆ E, Y ⊆ V, F는 promising하다고 해보자.

 

이 때 

promising하다는 것은 F가 우리가 찾고자하는 MST(minimum spanning tree)가 될 수 있다는 뜻이다.

promising하지 않은 것은 예를 들어 Cycle이 존재하여 MST가 될 수 없는 경우이다.

 

[Lemma]

e가 Y의 원소중 하나인 v1에서  V-Y의 원소중 하나인 v2로 이어져 있고

F와 e를 합한 집합은 promising 할 것이다. 

 

왜?

 

F가 promising 하기 때문에 MST가 (V,F')라면 F는 F'에 속할 것이다. (만들어가는 과정이니까!)

만약 최소라고 찾은 간선 e가 F'의 원소라면 F와 e를 합한 집합 역시 F'에 속할 것이다. 

그러므로 F ∪ {e}역시 promising하다고 할 수 있다.

 

반면에 만약 e가 F'원소가 아닌 경우라면, F' ∪ {e}는 반드시 cycle을 형성 할 것이다.

(왜냐하면 F'는 최소스패닝트리로 모든 정점들 사이에 간선이 연결되어있는데

F'의 원소가 아닌 간선 e가 합쳐진다면 연결 된 해당 두 정점에는 간선이 추가적으로 더 생기는 것이기 때문이다.)

 

그렇다면 F'에는 e가 연결하고 있는 v1, v2대신에

MST를 구성하는 Y의 원소중 하나인 v1과 V-Y의 원소중 하나인 v3을 잇는 간선 e'을 가지고 있을 것이다.

 

만약 F'  ∪ {e} - {e'}가 Spanning Tree라면 cycle이 사라졌다는 것이다.

e는 최소였으므로 e <= e'일 것이다. 그렇다면 F'  ∪ {e} - {e'}이 MST일 것이다.  (e'보다 작은 e로 교체했으므로)

그렇다면 더 최소인 MST에 

F  ∪ {e}가 F'  ∪ {e} - {e'}에 속해야한다. 

그런데 e'가 F만 가진 원소이므로 속하는게 성립하지 않는다.

 

따라서 e가 F'원소가 아닌경우 MST를 구성하는 간선이 존재한다는 것에 모순이 생기므로

F  ∪ {e}는 promising하다.

 

그럼 이제 프림 알고리즘이 항상 MST를 생성한다는 것을 증명하자.

 

F는 빈 집합이고 이는 promising하다.

i번째 반복 후에도 F가 promising하다고 가정하자.

이 때 e가 i+1 번째 선택된 간선이라면 F ∪ {e} 도 promising한 것을 증명하면 된다.

 

lemma에 의하여 F ∪ {e} 은 promising했다.

그러므로 프림 알고리즘은 항상 MST를 만든다. [Theorem]

 

 

흑 어렵다. lemma 마지막 결론부가 살짝 이해 안된다.