Minimum Spanning Tree & Clustering

 

* 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다.

 

 

Minimum Spanning Tree

Spanning tree : 최소 개수의 edge를 사용하여 모든 node를 커버하는 tree (graph)

Minimum spanning tree : 사용된 edge cost의 합이 최소가 되는 spanning tree

 

* Cayley's Theorem : Complete graph에는 가능한 spanning tree가 $n^{n-2}$개 존재한다.

 

 

 

 

Edge의 cost가 모두 다르다는 가정하에,

Cut property : Subset S와 G - S를 잇는 edge가 여러개 있을 때 (cutset), cost가 제일 작은 edge를 e라 하자. 그러면 MST는 e를 포함한다.

Cycle property : cycle C가 있고 cycle을 구성하는 edge중에 가장 cost가 큰 edge를 f라 하자. 그러면 MST는 f를 포함하지 않는다.

 

Claim : cutset과 cycle은 짝수 개수의 edge를 공유한다.

 

Pf ) Cut property 증명

cost가 제일 작은 e가 MST에 속하지 않고 f가 MST에 속한다 하고 이를 $T$라 하자. $T$에다가 f를 빼고 e를 더하여 $T^*$를 만들수 있다. e가 f보다 cost가 더 작기 때문에 $cost(T^*) < cost(T)$이다. 이는 $T$가 MST라는 가정에 모순이다.

 

Pf ) Cycle property 증명

f가 cutset에 속하도록 두 동강내고 f가 속한 것을 $T$라고 하자. Claim에 의해 f보다 cost가 작으면서 cutset에 속하는 e가 존재한다. 역시 $T$에다가 f를 빼고 e를 더하여 $T^*$를 만들 수 있고 e가 f보다 cost가 더 작기 때문에 $cost(T^*) < cost(T)$이다. 이는 $T$가 MST라는 가정에 모순이다.

 

 

 

Prim's Algorithm

처음에 임의의 node를 S에 넣고 cutset을 만든다. Cut property를 이용하여 minimum cost를 edge를 선택하고 그에 맞는 node를 S에 넣는다. 이를 반복하여 모든 node를 넣을 때까지 S를 계속 확장한다.

 

 

 

 

 

a[v]는 S 주위의 v에서 연결된 cost가 가장 작은 edge의 cost이다.

 

* Time complexity : binary heap으로 구현하면 $O(mlogn)$, array로 구현하면 $O(n^2)$

 

 

 

Kruskal's Algorithm

Edge를 cost가 작은 순으로 쭉 나열하고 하나씩 S에 추가한다. Edge를 추가해서 cycle을 만들어진다면 cycle property에 따라 해당 edge를 버린다. 그렇지 않으면 cut property에 의해 S에 추가한다.

 

 

 

* Time complexity : sorting에 $O(mlogn)$ (사실상 $O(nlogn)$), union-find에 $O(m \alpha(m,n))$ 

 

 

- Edge의 cost가 같은 경우에는?

1. 매우 작은 index를 더하여 (0.001, 0.002 ...) 중복이 없도록 한다.

2. edge cost를 비교할 때, cost가 같으면 index를 기준으로 차등을 둔다. 

 

 

 

Clustering

Clustering이란 n개의 object를 classify (grouping) 하는 것이다.

K-clustering : k개의 non-empty group으로 나누는 것이다.Spacing : cluster간의 어떠한 pair에서, 노드간 최소 거리이다.

-> Maximum spacing을 가지는 k-clustering하는 것이 목표

 

 

 

 

 

Single-link k-clustering algorithm

n개의 object를 n개의 노드를 가지는 그래프로 볼 때, 가장 작은 distance를 가지는 edge를 찾는다. 그리고 두 개의 cluster를 병합한다.

K개의 cluster가 생길 때까지는 이를 반복한다.

(이는 Kruskal's algorithm과 비슷한 알고리즘 형태를 보인다.)

 

 

K-clustering 문제는 k-1개의 most expensive edge를 제거한 MST를 찾는 문제와 같다.

 

Pf )  k-1개의 most expensive edge를 제거한 MST 조합을 ($C^*$)라 하자. 그리고 k-1개의 most expensive edge를 제거하지 않는 다른 cluster 조합($C$)이 있고, 이것이 더 큰 spacing을 가진다 하자.

그러면 $C^*$의 모든 edge는 cost가 $d$보다 작다.

또한, $C^*$에서는 하나의 cluster이지만 $C$에서는 다른 cluster인 $(p, q)$ pair가 있다.

 

하지만, $C^*$내에 모든 edge는 $d$보다 작기 때문에 모든 $(p, q)$ 경로 내의 edge는 $d$보다 작다. $C$의 spacing은 적어도 $d$보다 작거나 같기 때문에, $C$가 더 maximum spacing을 가진다는 것에 모순이다.