최소비용신장트리-01

강의 사이트

• http://www.kocw.net/home/search/kemView.do?kemId=1148815

최소 신장 트리 (Minimum Spanning Tree)

1. 최소 비용 신장 트리

• 무방향 가중치 그래프
• 각 엣지 (u, v) ∈E 에 대해서 가중치 w(u,v)
• 입력 : N개의 도시, 도시와 도시를 연결하는 비용
• 문제 : 최소의 비용으로 모든 도시들이 서로 연결되게 한다.
• 문제: 다음과 같은 조건을 만족하는 에지들의 부분집합 T⊆E를 찾아라.

• (b, c)의 가중치도 8이고 (a, h)의 가중치도 8인데 어느 것을 연결해도 모든 도시가 연결되기 때문에 상관 없다. 즉, 해가 유일하지는 않다는 의미.

2. 왜 트리라고 부르나?

• 싸이클이 없는 연결된 무방향 그래프를 트리라고 부른다.
• MST 문제의 답은 항상 트리가 됨.

3. Generic MST 알고리즘

• 어떤 MST의 부분집합 A에 대해서 A∪{(u,v)}도 역시 어떤 MST의 부분 집합이 될 경우 에지 (u,v)는 A에 대해서 안전하다(safe)고 한다.
• Generic MST 알고리즘
  1. 처음에는 A=∅이다.
  2. 집합 A에 대해서 안전한 에지를 하나 찾은 후 이것을 A에 더한다.
  3. 에지의 개수가 n-1개가 될 때까지 2번을 반복한다.

4. 안전한 에지 찾기

• 그래프의 정점들을 두 개의 집합 S와 V-S로 분할한 것을 컷(cut) (S,V-S)라고 부른다.
  • V-S는 전체 V에서 S를 뺀 나머지를 의미. 이때 s와 V-s 나누는 것을 컷이라고 부른다.
• 에지 (u,v)에 대해서 u∈S이고 v∈V-S일 때 에지 (u,v)는 컷 (S,VS)를 cross한다고 말한다.
• 에지들의 부분집합 A에 속한 어떤 에지도 컷 (S,V-S)를 cross하지 않을 때 컷 (S,V-S)는 A를 존중한다(respect)고 말한다.

5. 정리

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