[Algorithm] Minimum Spanning Trees

Definitions

Spanning Tree : 연결된 무방향 그래프 G에 대해,모든 정점을 포함하면서 사이클이 없고,연결된 부분 그래프 (subgraph) 를 말함.
즉, G의 모든 정점을 포함하는 트리. 이때, 노드가 n개일경우 간선은 n-1개.

Minimun Spanning Tree: 최소 가중치를 가지는 G의 Spanning Tree

MST사용 예시로는 Prim's Algorithm과 Kruskal's Algorithm이 있다.

 

Prim's Algorithm

특정 정점 집합 Y에 가장 가까운 정점을 찾는 과정에서 사용 배열을 사용하여 구현 

 

• W[i][j]: 정점 i와 j 사이의 가중치 (무방향이므로 대칭)
• nearest[i]: 정점 Vi에 대해, 현재까지 집합 Y에 속한 정점 중 가장 가까운 정점의 인덱스
• distance[i]: Vi와 nearest[i] 사이의 간선 가중치
• nearest[i] 는 1로 초기화 = 시작점을 1이라 가정.
• distance[i] 는 W[1][i]로 초기화 = 1에서 다른 정점 i까지의 거리

1에서 시작하여(이때 집합 Y에는 1이 들어가 있음) 1번과 연결된 노드들중 최소 가중치를 가지는 노드(편의상 vnear라 칭함)를 집어 넣음

이 간선의 가중치를 관리하는 집합 F를 만들어 집어 넣은 후 이 간선은 사용했다는 의미로 간선을 -1과 같은 값으로 설정하여 관리한다.

그 후 새로 연결된 정점 vnear가 있으므로 이 정점에서 다른 정점으로 가는 거리가 vnear가 연결되기 전 정점의 거리보다 짧은 경우 이 거리를 갱신해주는 작업을 수행해준다.

 

그러면 이 Prim's Algorithm이 어떻게 최적해를 보장하는지 설명해보자.

우리는 이를 증명하기 위해 Promising한 edge의 집합을 찾는것을 보이자 이때 promising 하다는 것은 Edge의 집합 E의 subset F에 몇개의 edge를 추가해 MST가 만들어 지는 경우.

공집합은 Promising하다 왜냐면 최소 간선들을 추가해 Promising 할수 있기 때문이다.

2,4번 경우는 최소 가중치 edge가 아니므로 Promising 하지 않다.

1,3,5번은 MST일때 Edge들의 부분집합이므로 Promising하다 즉 Promising하다는 것은 MST를 이루는 간선들이 있을때 그 간선들의 부분집합들을 뜻하는 것이다.

자 그러면 우리는 귀납법을 통해 증명해보자 

우선 공집합은 Promising 하다는 것을 알 수 있다.

그리고 반복중에 선택된 간선의 집합을 F라하고 이 F는 Promising하다고 하면 우리는 F에 특정 간선 e가 추가될 때 

이때 e는

• 현재 MST에 포함된 정점 집합 Y와,
• 아직 포함되지 않은 정점 집합 V − Y를 나누고,
• 이 둘을 잇는 간선 중 가중치가 가장 작은 간선 e를 선택한다

이 경우에 Promising 하다는 것을 보이자

이때 F를 포함하고 있으며 MST를 이루는 어떤 간선 집합 **F′**가 존재한다는 것이 귀납 가정이다.

즉, **F ⊆ F′**이고, (V, F′)는 MST이다.

 

그렇다면 e ∈  F' 일 경우 F ⊆ F' 이므로 F에 e가 추가되어도 F'의 부분집합이고 MST이므로 Promising 하다는 것을 알수 있다.

그렇다면 e ∉ F′ 일 경우는 어떨까? F'에 e는 포함되어 있지 않으므로 F'에 e를 추가하면 F'은 사이클이 생길 것이다(F'은 MST이므로 모든 노드가 연결되어 있기 때문이다)

이때 F'에 포함되어 있으며 사이클에 포함되는 간선 e'이 있으며 이 간선은 이미 선택된 집합 Y와 선택되지 않은 집합 V-Y를 잇는 간선이라 하자. 그렇다면 F'에 e를 추가해 사이클이 있는 집합 F'에서 e'을 빼면 사이클이 사라지며 이는 spanning tree기 된다. 또한 이때 골라진 e는 Prim algorithm에 의해 골라진 Y와 V-Y를 잇는 최소 가중치 간선이기 때문에  e는 e'보다 작거나 같은 값을 가지게 될 것이다.

이를 그림으로 보면

이렇게 될 것이다. 따라서 F 에 간선 e를 추가한 것은 Promising 함을 알 수 있다.