최소 비용 신장 트리 (1)

Minimum Spanning Tree

최소비용 신장 트리 (MST)

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

- 출력 : 최소의 비용으로 모든 도시들이 서로 연결된 상태

- 무방향 가중치 그래프이며 가중치들은 전부 양수라고 가정한다.

- (b, c) 엣지대신 (a, h) 엣지를 연결하는 등 문제에 대한 해가 유일하지 않다.

- 무방향 가중치 그래프 G = (V, E) / 가중치들은 양수들이다.

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

Ex) 아래와 같은 조건을 만족하는 엣지들의 부분집합인 T ⊆ E를 구해라.

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

2) 가중치의 합 $\sum _{ (u,v)∈T }{ w(u,v) } $이 최소가 된다.

트리라고 부르는 이유

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

- MST 문제의 해답들은 전부 트리가 된다. 노드들이 전부 연결됨과 동시에 사이클이 발생하지 않기 때문이다.

Generic MST 알고리즘

-  Kruskal과 Prim 알고리즘이 공통적으로 가지고 있는 구조가 Generic MST 알고리즘이다.

- 어떠한 MST의 부분집합 A에 대해서 A ∪ {(u, v)}도 역시 어떠한 MST의 부분 집합이 될 경우 엣지 (u, v)는 A에 대해서 안전하다고 할 수 있다. 안전한 엣지일 경우에는 알고리즘이 오류 없이 정상적으로 진행되고 있다는 것을 뜻하기 때문에 계속 알고리즘을 진행하더라도 문제가 없다.

- Generic MST 알고리즘

1) 처음에는 A = ∅이다.

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

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

- 슈도 코드

GENERIC-MST(G, w)

A <- ∅

while A does not from a spanning tree

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하지 않는다면 컷은 A를 존중한다(respect)고 칭한다. (양 컷 사이를 잇는 엣지가 없다는 뜻)

아래 그림을 보았을 때 각 그림들 모 선을 따라서 두 컷으로 나누었을 때 두 예시들 다 양 컷을 가로지르는 엣지가 존재하지 않기 때문에 각 컷은 반대쪽 컷을 존중(respect)한다라고 말할 수 있다.

MST 정리

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

- 빨간 엣지들은 MST의 부분집합들이라고 할 수 있으며, 가중치가 가장 작은 파란 엣지는 MST의 부분집합에 대해 안전하며 이에 따라 MST의 부분집합에 포함시켜도 문제가 없다는 것을 의미한다.

Kruskal 알고리즘

1) 엣지들을 가중치의 오름차순으로 정렬한다.

2) 엣지들을 그 순서대로 하나씩 선택해나간다. 단, 이미 선택된 엣지들과 사이클을 형성하는 결과를 낳는다면 해당 엣지는 선택하지 않고 다른 엣지를 선택한다.

3) n - 1개의 엣지가 선택된다면 프로그램을 종료한다.

(d)상태를 집합으로 나누어보면 {a, b}, {i, c}, {h, g, f}, {d}, {e}로 나눌 수 있다.

(f)에서의 (i, g)엣지와 (h)에서의 (h, i)엣지를 선택하게 되면 사이클이 형성되기 때문에 가중치가 작더라도 선택하지 않는다.

(k)에서 모든 노드를 지나게 되었기 때문에 더 이상의 엣지를 찾지 않고 프로그램을 종료할 수 있게된다.

- 슈도 코드

MST-KRUSKAL (G, w)

A = null;

for each vertex v ∈ V[G] // 초기화

MAKE-SET(v); // 각 노드들을 유일한 원소로 만드는 집합들을 만든다(n개) 

sort the edges of E into non decreasing order by weight w

for each edge (u, v) ∈ E, taken in non decreasing order by weight

if FIND-SET(u) != FIND-SET(v) // u와 v가 속한 집합을 찾는다. 둘 모두 같은 집합이면 사이클이 발생한것

A = A ∪ {(u, v)}

UNION(u, v); // u와 v가 속한 두 집합을 하나로 합침

return A;

MST가 찾아지는 이유

- Kruskal 알고리즘의 임의 한 단계를 본다.

- A를 현재까지 알고리즘을 진행하며 선택한 엣지들의 집합이라 하고, A를 포함하는 MST가 존재한다고 한다.

- u와 v는 빨간 엣지들에 의해 연결되지 않은 엣지이다. 또한 알고리즘이 (u, v)를 선택했다면 이 엣지를 선택했을 때 빨간 엣지들이 사이클을 만들지 않는다는 것을 의미한다. 또한 A에 대해 안전하다고 할 수 있고 A집합에 해당 엣지를 추가하더라도 MST가 유지된다.

사이클 검사 과정

- 초기 상태 : 선택된 엣지 없음 (null)

- 엣지로 이어진 노드들은 하나의 집합으로 표현한다. (UNION)