Minimum Spanning Tree (MST)

연결된(connected), 무방향(undirected), 가중치(weighted) 한 그래프 중에 총 weight(edge의 weight의 합) 이 가장 최소인 spanning tree.

 

connected graph에서 vertice가 n개 있을 때, edge가 n-1개 있어야 한다.  => tree (cycle이 없다.)

 

MST

 

총 weight의 합이 minimal한 것을 골라야 하기 때문에 Greedy algorithm 이다.

 

• 특징

1. 간선(edge)의 가중치의 합이 최소여야 한다.

2. n개의 정점(vertice)을 가지는 그래프에 대해 반드시 n-1개의 간선만을 사용해야 한다.

3. 사이클이 포함되어서는 안된다.

MST는 여러개일 수 있다.

 

 

 

• Generic MST

어떤 A에 대하여 A U {(u,v)}도 역시 어떤 MST의 부분 집합이 될 경우 edge(u,v)는 A에 대해서 safe하다고 한다.

 

1. 처음 A=ø 이다.

2. 집합 A에 대해서 safe한 edge를 하나 찾은 후, A에 더한다.

3. edge의 개수가 n-1개가 될 때까지 2번을 반복한다.

 

- safe한 edge를 찾는 방법

1. 그래프의 정점들을 두개의 집합 S와 V-S로 분할한 것 (위 사진의 빨간 선) 을 cut(S,V-S)이라고 부른다.

2. edge (u,v) 에 대해서 u가 집합 S에 속하고, v가 집합 V-S에 속할 때, edge(u,v)는 cut(S,V-S)를 cross한다고 말한다.

3. edge들의 부분 집합 A에 속한 어떤 edge가 cut(S,V-S)를 cross하지 않을 때 cut(S,V-S)는 A를 respect한다고 한다.

4. crossed edge 준에 edge의 weight이 가장 작은 edge를 light edge라고 한다. 즉, lighte edge를 MST의 성분으로 골라도 된다.