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

프림 알고리즘의 최적 여부 검증 Optimality Proof

프림 알고리즘은 매 결정을 할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택하는 그리디 알고리즘에 기반한다. 그 순간의 선택은 그 당시에는 최적일 수도 있지만 순간순간 최적이라고 생각했던 해답을 모아서 최종적인 해답을 만들었을 때, 그 해답이 궁금적으로 최적이라는 보장이 없다. 따라서 그리디 알고리즘은 항상 최적의 해답인지 검증할 필요가 있다.

 

프림 알고리즘이 찾아낸 신장트리가 최소비용인지 검증해야 한다. 다시 말해서, 프림 알고리즘이 최적인지를 보여야 한다.

 

비방향성 그래프인 G = (V, E)가 주어진다. G는 가중치가 있는 그래프이고, 이것은 전체 정점의 집합V와 전체 간선의 집합E로 이루어져 있다. F는 방문한 간선이고 E에 속한다. MST의 간선 집합은 F'이다. Y는 F의 간선들로 연결된 정점의 집합이다.

만약 E의 부분집합 F에 MST가 되도록 간선을 추가할 수 있다면, F는 유망하다(promising)라고 한다. 

 

여기서 유망하다(promising)는 것은 F에 간선이 더 추가되거나 혹은 F 그 자체로 MST가 될 가능성이 있다는 의미이다.

만약 F에 사이클이 있다면 그것은 MST가 될 수 없으므로 유망하다고 할 수 없다.

 

Lemma 4.1

Y에 있는 어떤 정점과 V-Y에 있는 어떤 정점을 잇는 간선 중에서 가중치가 가장 작은 간선 e라고 한다면 F∪{e}는 유망하다.

 

왜냐하면

 

일단, F는 promising하기 때문에 F'에 속한다. 여기에서

1) 만약 간선 e가 F'에 속한다면

F에 e를 추가한 집합 역시 F'에 속할 것이다. 따라서 F∪{e}는 유망하다고 할 수 있다. ⊆

 

2) 만약 간선 e가 F'에 속하지 않는다면

(V, F')는 신장 트리이기 때문에 e를 F'에 추가한다면 반드시 사이클이 생기게 되고 e는 반드시 사이클을 만드는 간선에 속할 것이다. 이 때 Y의 한 정점에서 V-Y의 한 정점을 연결하고 F'에 속하는 또 다른 간선 e'가 사이클 안에 반드시 존재한다. 

 

- 여기서 만약 F'∪{e} 에서 e'를 제거한다면

사이클은 없어지고 다시 신장트리가 될 것이다. 그런데 e는 Y에 있는 한 정점에서 V-Y에 있는 한 정점을 연결하는 가장 작은 가중치를 가진 간선이기 때문에 e의 가중치는 e'의 가중치보다 작거나 같아야 한다. (실제로 반드시 같게 된다.)

>> 개인적으로 이 단락 이해가 어려웠어서 더 자세히 설명하자면,

여기에서 e가 가장 작은 가중치를 가진 간선인 이유는 프림 알고리즘 구현 코드를 보면 알겠지만 간선을 추가할 때 기본적으로 아무 간선이나 추가하는 것이 아니라, 인접 노드(Y집합에 들어가지 못한 노드)와 연결된 간선 중 가중치가 가장 작은 간선을 추가하기 때문이다.

>> 또, e의 가중치가 e'의 가중치보다 작거나 같아야 하는 이유는

이 단락에서 Y는 이미 V가 된 상태고 V-Y는 공집합이 된 상태이다. 왜냐하면 얘네는 이미 신장트리였고 e를 넣었을 때는 순환경로까지 생긴 상태였기 때문이다. 

 

그러면 F'∪{e} - {e'} 는 MST가 된다.

결론적으로 e'는 F 안에 절대로 속할 수 없다. (F 안에 있는 간선들은 Y 안에 있는 정점들만을 연결한다.)

결국 F∪{e} ⊆ F'∪{e} - {e'}가 되고 따라서 F∪{e} 는 유망하다.