15-1강. 최소비용신장트리(Minimum spanning tree)

최소비용신장트리 (Minimum Spanning Tree)

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

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

 

예시 그래프

 

최소비용신장트리

해가 유일하지는 않다..

예) (b, c) 대신에 (a, h)가 되어도 된다.

-> 비용이 같고, 다 연결되기 때문이다.

 

 

* 최소비용신장트리의 답은 항상 트리가 된다. 왜?

(트리 : 싸이클이 없는 연결된(connected) 무방향 그래프)

 : cycle이 있다는 말은 이쪽 방향으로 가도 저쪽 방향으로 가도 되는데, 이 경우 한 쪽의 길이 끊어져도 반대 방향으로 갈 수 있게 된다. 따라서 우리는 최소비용을 원하므로 cycle이 있는 그래프는 이 경우에서 제외한다.

 

 

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

 

- Generic MST  알고리즘 : 

   1. 처음에는 A=ø이다.

   2. 집합 A에 대해서 안전한 에지를 하나 찾은 후 이것을 A에 더한다.

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

 

 

Generic-MST(G, w)
{
	A <-ø
    while A does not form a spanning tree
    	do find an edge (u, v) that is safe for A
        	A <- A∪{(u, v)}
    return A
}

 

 

 

안전한 에지 찾기

* 안전한 에지 찾기

- 그래프의 정점들을 두 개의 집합 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, V-S)는 A를 존중한다(respect)고 말한다.

 

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

 

 

www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C/lecture/4109?tab=curriculum

영리한 프로그래밍을 위한 알고리즘 강좌 - 인프런