최소비용신장트리-1

Minimun Spanning Tree(MST)

- 입력 : n개의 도시, 도시와 도시를 연결하는 비용

- 문제 : 최소의 비용으로 모든 도시들이 서로 연결되게 한다.

- 무방향 가중치 그래프 G=(V,E)

- 각 에지 (u,v)∈E에 대해서 가중치 w(u,v)

- 문제 : 다음과 같은 조건을 만족하는 에지들의 부분집합 T⊆E를 찾아라

1. T에 속한 에지들에 의해 그래프의 모든 정점들이 서로 연결된다.

2. 가중치의 합이 최소가 된다.

 

** 왜 트리라고 부를까?

- 싸이클이 없는 연결된 무방향 그래프를 트리라고 부른다.

- MST는 항상 트리가 된다.

서로 연결이 되면서 최소 비용이 되기 위해서는 순환할 필요가 없다. 따라서 노드가 n개가 된다면 에지는 n-1개가 되기 때문이다.

Generic MST 알고리즘

- 어떤 MST의 부분집합 A에 대해서 A∪{(u,v)}도 역시 어떤 MST의 부분집합이 될 경우 에지 (u,v)는 A에 대해서 안전하다고 한다.

• 처음에는 A = null
• 집합 A에 대해서 안전한 에지를 하나 찾은 후 이것을 A에 더한다.
• 에지의 개수가 n-1개가 될 때까지 2번 반복한다.

안전한 에지 찾기

- 그래프의 정점들을 두 개의 집합 S와 V-S로 분할한 것을 컷(cut)(S,V-S)라고 부른다.

- 에지 (u,v)에 대해서 u∈S이고 v∈V-S일 때 에지 (u,v)는 컷 (S,V-S)를 cross한다고 한다.

- 에지들의 부분집합 A에 속한 어떤 에지도 컷(S,V-S)를 cross하지 않을 때 컷(S,S-V)는 A를 존중한다고 말한다.

- 위의 그림은 S와 S-V가 컷되어있다

- A가 어떤 MST의 부분집합이고, (S,V-S)는 A를 존중하는 컷이라고 할 때 이 컷을 cross하는 에지들 중 가장 가중치가 작은 에지 (u,v)는 A에 대해서 안전하다.

 

* 위의 그림들은 "영리한 프로그래밍을 위한 알고리즘" 강좌에서 가져왔습니다.