[Algorithm Part 2] 3. Minimum Spanning Tree

이번 글에서는, Minimum Spanning Tree에 대해 살펴볼 것이다.

---

MST (Minimum Spanning Tree)

Definition

Given $G$ is undirected weighted graph with positive weights (connected).

A spanning tree of $G$ is a subgraph $T$ that is both a free tree (connected and acyclic) and spanning (includes all the vertices).

(spanning tree는 span하고 acyclic이기에, V-1개의 edge를 가지고 있다.)

MST(Minimum Spanning Tree) of G is spanning tree which has minimum total weight.

 

Cut in graph is partition of its vertices into two (non empty) sets.

Crossing edge connects a vertex in one set with a vertex in other.

---

Cut property

Given any cut, the crossing edge of min weight is in the MST.

(임의의 cut으로 그래프를 분할했을 때, 최소 가중치를 가진 crossing edge(=$e$)는 MST에 속한다.)

Proof

"edge $e$(=minimum crossing edge)가 MST에 속하지 않는다"고 가정하자.

위 가정으로 인해, 다른 crossing edges(=$f$) 중 하나 이상이 MST에 있어야 한다. (because MST is spanning.)

1. MST에 $e$를 추가시켜, cycle을 만든다. (becase MST has V edges.)
2. cycle에 crossing edge(s) $f$가 무조건 포함되어 있다.
   (A에서 B로 가는 경로는 2가지(1. $e$로 가는 경로, 2. $f$로 가는 경로)가 있다.
   위 경로를 합치면$e$와 $f$를 포함하는 cycle이 만들어진다.)
3. $f$를 제거해, spanning tree를 재구성한다.
   (cycle에 포함된 임의의 edge 하나를 제거하면,연결성과span이 유지되는 동시에,순환이 없어진다.)
4. 재구성된 spanning tree의 total weight가 MST보다 낮아지는 모순이 발생한다.

Cut property를 활용해 MST greedy algorithm을 설계할 수 있다.

---

Weighted graph representation

graph와 동일하다. 다만, edge의 가중치 값을 추가로 저장해야 한다.

• Graph: if v-w exists, then adj[v][w] = adj[w][v] = true
  (or adj[v].append(w), adj[w].append(v))
• Weighted Graph: if v-w exists, then adj[v][w] = adj[w][v] = weight
  (or adj[v].append((w, weight)), adj[w].append((v, weight)))

---

0. Greedy algorithm

1. 모든 edge를 gray edge로 초기화한다.
2. V-1개의 black edge를 가질 때까지, 다음 과정을 반복한다.
   1. gray crossing edge로만 구성된 임의의 cut을 찾고,
   2. minimum crossing edge를 black edge로 바꾼다.

Correctness of algorithm

black edge는 MST에 속한다. (by cut property)

V-1개 이하의 black edge가 있을 경우, gray crossing edge로만 구성된 cut이 존재한다.

(CC(=black edge로 연결된 vertex)를 기반으로 graph를 분할하면, 쉽게 gray crossing edge로만 구성된 cut을 찾을 수 있다.)

---

1. Kruskal's algorithm

1. weight를 기준으로 edge를 정렬한다. (by PQ)
2. 현재 남은 edge 중 minimum edge(=$e$)를 가져온다.
3. 이때, $e$가 순환을 생성하지 않으면, 트리(=$T$)에 추가한다. (by Union-Find)
4. $T$가 V-1개의 edge를 가질 때까지, 2 ~ 3번을 반복한다.

Correctness of algorithm

$e$(=v-w)는 다음 2가지 조건을 만족한다.

($e$ = 순환을 만들지 않은 minimum edge)

1. $e$는 A(=v의 CC)와 B(=else)로 분할된 cut의 crossing edge다.
2. $e$가 A와 B사이를 순환하지 않으면, "crossing edge가 트리(=$T$)에 없음"을 의미한다.
   $e$가 현재 남은 edge 중 minimum edge이기에, minimum crossing edge다.

위 조건을 만족하기에, $e$는 임의의 cut의 minimum crossing edge다. 

Performance

	sort edge (build PQ)	get min-edge (del edge)	add edge (union)	check cycle (connected)
frequency	1	E	V	E
time per op	$E \log E$	$\log E$	$\log^* E$	$\log^* V$

---

2. Prim's algorithm

1. source vertex를 트리(=$T$)에 추가한다.
2. non-$T$ vertex에서 $T$ vertex로 가는 minimum edge(=$e$)를 $T$에 추가한다.
3. $T$가 V-1개의 edge를 가질 때까지, 2번을 반복한다.

Correctness of algorithm

$e$(=v-w)는 다음 2가지 조건을 만족한다.

($e$ = tree vertex에서 non-tree vertex를 연결하는 minimum edge)

1. $e$는 A(tree vertex)와 B(non-tree vertex)로 분할된 cut의 crossing edge다.
2. $e$의 정의가 minimum crossing edge라는 것을 의미한다.

위 조건을 만족하기에, $e$는 임의의 cut의minimum crossing edge다. 

---

non-$T$ vertex에서 $T$ vertex로 가는minimum edge 찾기

2.1. Lazy algorithm

PQ (key = edge, priority = weight of edge)

임의의 vertex v을 방문(visited[v] = True)한 후, v의 모든 edge를 push한다.

 

pop을 통해 minimum edge $e$(=v-w)를 가져온다.

1. v와 w 모두 방문했으면(visited[v] = visited[w] = True), 다시 pop한다.
2. 둘 중 하나만 방문했으면(if visited[v] = False and visited[w] = True),
   
   1. v를 방문(visited[v] = True)한 후, $e$(=v-w)를 $T$에 추가한다.
   2. 모든 v의 edge(v-x)를 찾은 후, visited[x] = False인 모든 edge를 push한다.

---

2.2. Eager algorithm

PQ (key = vertex(=v), priority = weight of shortest edge connected v to $T$)

임의의 vertex v를 방문(marked[v] = True)한 후, v 인접 정점의 priority를 update한다.

(처음에는, source vertex를 0, 그 외 정점은 ∞로 초기화한다.)

 

pop을 통해 min vertex(=v)를 가져온다.

1. v를 방문(visited[v] = True)한 후, v의 priority(=weight)에 해당하는 $e$(=v-w)를 $T$에 추가한다.
2. 모든 v의 edge(v-x)를 찾은 후, visited[x] = False인 모든 vertex x의 priority를 update한다.
   (if v-x's weight < x's priority, then update x's priority by v-x's weight)

Performance

	Time-Complexity	Space-Complexity
Lazy	$E\log E$	$E$
Eager	$(E + V)\log V$	$V$

---

MST application: clustering

MST algorithm을 활용하면, single-link clustering 문제를 쉽게 풀 수 있다.

Definition

k-clustering divide a set of objects classify into k coherent groups.

single link: distance between two clusters equals the distance between the two closest objects.

single-link clustering: given an integer k, find a k-clustering that maximizes the distance between two closest clusters.

Single-link clustering algorithm

1. 각 클러스터가 하나의 객체만 포함하게 V개의 클러스터를 만든다.
2. 서로 다른 클러스터에 속한 객체 쌍 중 가장 가까운 객체 쌍을 찾아, 두 클러스터를 합병한다. (using MST)
3. 클러스터 개수가 k개가 될 때까지 반복한다.