Graphs(4) - MST(Minimum Spanning Tree)

Minimum Cost Spaning Trees

input : An undirected, connected graph G

output : subgraph of G

 - output의 모든 edge합이 가장 작아야 한다.

 - 모든 vertices들은 연결이 되어 있어야 한다.

 

이때 첫번째 조건은 MST가 cycle이 없음을 의미한다. 만약 cycle이 존재한다면 그 cycle에서 edge를 하나 빼면 (2)의 조건을 만족하면서 더 작은 subgraph가 생기기 때문이다.

 

output은 여러개일 수 있으나 cost는 어떠한 solution에 대해서도 같다.

 

 

 

Prim's MST Algorithm

1. 아무 vertex N에서 시작한다. MST에 N을 추가한다.
2. N과 연결된 edge들 중 가장 작은 edge인 (N,M)를 고른다.
3. M과 (N,M)을 MST에 추가한다.
4. N과 M에 연결된 edge들중 가장 작은 edge를 고르고 다시 같은 방식으로 추가한다..
5. 위를 반복한다.

Proof :

어떤 edge e가 추가될 때 현재 만들어진 tree와 e를 포함하고 있는 MST가 존재하고 있음을 증명하자.

mathematical induciton을 사용한다.

base case - 

v가 starting vertex라고 하면 v에 연결된 가장 작은 cost edge e=(v,y)를 정하자.

MST에 있는 어떤 graph들중 하나라도 e를 가지고 있다면 base case는 만족된다.

만약 어떤 그래프도 가지고 있지 않다고 하자. MST에 속한 graph G*에 e를 더하게 된다면 그 그래프에 cycle이 생기게 된다. 그리고 그 cycle에는 v와 연결된 또다른 edge가 존재한다. 만약 그 edge의 cost가 e보다 크다면 G*보다 cost 총합이 작은 그래프가 생기므로 모순이다. 같아도 cost가 같으므로 e를 포함한 MST가 존재한다.

따라서 base case를 만족한다.

k번째 iteration에서 만족할 때 k+1번째 iteration에서 만족하는 것 보이기 -

g=(x,y)를 k+1번째 iteration에서 고른 edge라고 하자. iteration k번째에서 만들어진 tree를 T라고 하자. 

T*을 MST에 속하면서 T를 포함한 그래프라고 하자. T+g가 T*에 포함이 안되어있다고 가정하자. T*+g는 g를 포함한 cycle이 생기게 될 것이다. 그 cycle은 T에 속한 vertices들과 속하지 못한 vertices들로 나눌 수 있다. 그 경계를 연결하는 edge들은 g를 포함하여 최소 2개인데, k+1번째 iteration에서 g를 선택했으므로 g가 경계를 연결하는 edge들 중 cost가 가장 작다.

따라서 g를 연결하고 나머지 edge를 하나 끊으면 MST는 유지가 된다. 따라서 k+1번째 iteration에서도 MST가 존재한다.

 

 

Running Time of Prim's MST

scan through the distance table : O(|V|^2+|E|)

Min-heap:O((|V|+|E|)log(|V|))

 

 

Kruskal's MST Algorithm

1. 처음에 각자의 vertex들은 자체의 MST에 존재한다.
2. MST에 속한 것들 중 가장 작은 두개의 MST를 merge한다.
3. 반복

자세한 것은 algorithm 카테고리에서 추후 작성하겠다.

 

Total cost :

O(|E|log|E|)

 

 

 

 

출처 : 서울대학교 컴퓨터공학부 강유 교수님 자료구조 수업