[Algorithms] 5.1 Minimum spanning trees

in Devlog on Algorithm


해당 글은 Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani를 정리한 스터디 노트입니다. 해석하면서 정리한 글입니다.

5.1 Minimum spanning trees

문제 상황

  • 여러 대의 컴퓨터와 그것들을 서로 연결할 네트워크를 찾고 있습니다.
  • 이를 그래프 문제로 해석한다면, 각 노드가 컴퓨터이며 엣지가 연결관계로 볼 수 있습니다.
  • 이때, 엣지에는 유지 비용으로 edge’s weight로 반영됩니다.
  • 그렇다면, 최소한의 비용으로 가능한 네트워크는 무엇일까요?

Property 1: Removing a cycle edge connot disconnect a graph
결국, 문제 상황에서 원하는 네트워크 구조는 트리 구조임을 알 수 있습니다.

  • tree = connected & acylic & undirected graph

특히, total weight가 가장 낮은 트리를 minumum spanning tree라고 부릅니다.

Formal Definition(finding MST)

  • Input: An undirected graph $G = (V, E)$; edge weights $w_e$.
  • Output: A tree $T=(V, E’)$, with $E’ \subseteq E$, that minimizes

$weight(T) = \sum_{e \in E’} w_e$

5.1.1 A greedy approach

Kruskal’s minimum spanning tree algorithm은 empty graph에서 시작해서 아래와 같은 룰에 의해 $E$로부터 추가될 엣지를 선택합니다.

  • cycle이 발생하지 않는 가장 lightest edge를 반복적으로 추가합니다.

즉, 매순간마다 다음과 같은 선택을 하겠다는 뜻입니다.

  • avoid cycles
  • picks chepest edge(어느 edge가 가장 저렴한지 선택)

이들을 탐욕 알고리즘 과정이며, 모든 decision은 가장 명백한 즉각적인 이점을 가지고 있습니다.

img

빈 그래프에서 시작하여 edge들을 weight 순으로 오름차순 정렬해줍니다.
cycle은 피하면서 edge를 선택합니다.

  • B - C 연결 → C - D 연결 → B - D 연결(X) → C - F 연결 …

Kruskal의 방법의 정합성은 특정 cut property로부터 얻을 수 있습니다. 사실, 이 cut property로부터 다른 많은 MST 알고리즘들을 justify할 수 있습니다.

Property 2: A tree on $n$ nodes has $n-1$ edges.
빈 그래프에서 하나씩 엣지를 추가하는 과정으로 보일 수 있습니다.

  • 빈 그래프 = n개의 노드들이 서로 disconnected = 각 노드들 자체가 connected component
  • 엣지를 추가할 때 마다, 하나씩 merge되므로 트리가 완성되기 위해서 총 $n-1$개의 엣지가 필요합니다.

또한 특정 엣지 {$u, v$}가 연결된다는 것은 u, v 노드가 분리된 connected component에 각각 놓여져 있다는 것을 뜻합니다.(만약 그 사이에 path가 있었다면, uv에 의해 cycle을 만드는 결과가 나올 것입니다)

이렇게 하나의 엣지를 추가함으로써 connected component의 총 개수를 줄여나가는 것입니다.
계속 반복하면서, $n$개의 component들은 마지막 1개로 통합될 것이고, 이는 $n-1$ 엣지들이 추가된다는 뜻입니다.

Property 3: Any connected, undirected graph $G = (V, E)$ with $\vert E \vert = \vert V \vert -1$ is a tree.
$G$가 acyclic임을 보이기만 하면 끝입니다.

  • 다음의 절차를 반복합니다 : 그래프에 cycle가 존재할 경우, 해당 cycle 내의 edge를 제거합니다.
  • $G’ = (V, E’), E’ ⊆ E$, s.t.acyclic 라는 그래프가 되는 순간 process terminates.
  • By Property 1, $G’$ is also connected.
  • 따라서, $G’$는 Tree이므로 Property 2에 의해 $\vert E’ \vert = \vert V \vert -1$이 됩니다.
  • $E’ = E$이므로, 즉 어떤 엣지도 제거되지 않았다는 뜻입니다.
  • 이는 $G$ 자체가 이미 cycle이 없다는 뜻입니다. = acyclic

이 성질에 의해, 어떤 connected graph의 edge 수를 세서 tree인지 아닌지 파악할 수 있습니다.

Property 4: An undirected graph is a tree if and only if there is a unique path between any pair of nodes.
트리에서 어떤 두 노드 사이는 오직 하나의 path만 존재합니다. 만약 두 paths가 있다면 이들은 cycle을 가집니다.

반면에, 그래프가 두 노드 사이에 path를 가지고 있으면 연결됩니다. 이러한 경로가 고유하면 그래프도 순환됩니다. (cycle은 두 개의 노드 사이에 두 개의 경로를 가지기 때문입니다)

5.1.2 The cut property

MST를 만드는 과정에 있어서, 이미 몇가지 edges을 선택했고 올바른 방향으로 진행하고 있는 중 입니다. 어떤 edge를 다음에 추가할 수 있을까요?

img

  • cut: 노드들을 partitions into two groups, S and V - S
  • 이 property는 어떤 cut을 가로지러 가장 가벼운 edge를 추가하는 것은 항상 MST를 형성하는 방법임을 설명합니다.

pf) Edges X를 MST의 일부분이라고 하겠습니다.
1) 만약 새로운 edge $e$가 $T$의 일부분이면 증명할 필요가 없습니다. 2) 따라서, 새로운 edge $e$가 $T$에 없다고 가정하겠습니다.

  • T의 edge 하나를 바꿔서 $X ∪ e$를 포함하는 새로운 mst $T’$를 construct합니다.
    • T에 edge $e$를 추가합니다.
    • $T$가 connected 하기 때문에 이미 $e$의 끝점 사이에 path가 하나 존재합니다.
    • 즉 $e$를 추가함으로써 cycle을 만들었습니다.
    • 이 cycle로 인해, the cut$(S, V-S)$을 가로지르는 다른 edge $e’$가 분명히 있습니다.
    • img
    • 이 엣지를 제거함으로써, 새로운 $T’$를 얻게 됩니다. $T’ = T∪ e-e’$
    • Property 2, 3에 의해 $T’$는 tree입니다.
  • 게다가 $T’$는 MST입니다.
    • $weight(T’) = weight(T)+ w(e) - w(e’)$
    • $e$와 $e’$ 모두 S와 V - S 사이에 놓여진 edge 이지만, $e$가 더 가볍습니다. (=$w(e)≤w(e’))$
    • 즉, $weight(T’) ≤ weight(T)$
    • T가 MST 이므로, $weight(T’) = weight(T)$.
    • 따라서 $T’ = MST$가 됩니다.

5.1.3 Kruskal’s algorithm

주어진 순간, 이미 선택한 edges는 하나의 partial solution을 형성하는데, 이 partial solution은 각각 tree 구조를 가진 connected components의 집합이라고 볼 수 있습니다.
새롭게 추가된 edge $e$는 이러한 components 중 특정 2개의 components $T_1$과 $T_2$ 사이를 연결하게 됩니다.
$e$는 가장 가벼우면서 cycle을 형성하지 않는 path이므로, $T_1$과 $V−T_1$ 사이의 가장 가벼운 edge 입니다.
따라서 cut property를 만족합니다.

각 단계마다, 알고리즘은 현재의 partial solution에 추가시킬 edge 하나를 선택합니다. 그렇게 하기 위해서는, 각 후보 edge $u−v$에 대해 종점인 u와 v가 각각 서로 다른 components에 놓여져 있는지 체크해봐야 합니다. (그렇지 않은 경우는 cycle을 만들게 됨)
그리고 edge가 선택되고 나면, 해당하는 components들은 서로 합쳐지게 됩니다. 이러한 연산에 적합한 자료 구조는 어떤 종류일까요?

img

모델링

  • 알고리즘의 상태를 각각 특정 구성요소의 노드를 포함하는 disjoint sets 집합으로 모델링합니다.

사용함수

  • makeset(x): x만 포함하는 singleton 집합을 만듭니다. (처음에 각 노드는 그 자체로 구성요소에 있습니다)
    • 노드 쌍이 동일한 집합에 속하는지 확인하기 위해 반복적으로 테스트 해줍니다.
  • find(x): x는 어느 set에 속하는지 찾습니다.
    • 그리고 edge를 추가할 때마다 두 개의 구성 요소를 병합합니다.
  • union(x, y): x와 y를 포함하는 집합을 병합합니다.

사용되는 연산 수

  • $\vert V \vert$ makeset
  • $2\vert E \vert$ find
  • $\vert V \vert -1$ union(tree)

5.1.4 A data structure for disjoint sets

Union by rank

집합을 저장하는 방법 중 하나로 directed tree가 있습니다. (아래의 사진 참조) img

트리의 각 노드들은 집합의 원소입니다. 이들은 특정 순서 없이 배열되어 있습니다. 각 노드는 *parent pointers $\pi$를 가지고 있습니다.

  • 이 parent pointers를 따라가면, tree의 root가 나옵니다.
  • 이 root 원소를 집합의 representative 혹은 name이라고 부릅니다.
  • 이 root 원소가 다른 원소들과 차이가 있는 부분은 parent pointer가 self-loop 형태입니다.

각 노드들은 rank를 가집니다.

  • 노드에 걸려 있는 subtree의 높이로 해석이 가능합니다.

img

  • makeset: constant-time operation
  • find: parent pointers를 따라서 트리의 root까지 가므로, 트리의 높이에 비례하여 시간이 걸립니다.

img

  • union: union by rank schema인 이유
    • tree의 높이가 계산 효율성의 주된 장애물이므로, 더 짧은 tree의 root가 더 높은 tree의 root를 가리키도록 하는 것이 좋은 전략입니다.
    • 그렇게 하면, 병합되는 두 tree의 높이가 같아져야 전체 높이가 증가합니다.
    • 트리의 높이를 명시적으로 계산하는 대신 root node의 rank numbers를 사용합니다.
      • 이로 인해, 이 scheme는 union by rank라고 불립니다.

Property 1: For any $x$, rank($x$) < rank($\pi$($x$)).

  • follow by induction
    • rank $k$인 루트 노드는 rank $k-1$인 루트를 가진 두 트리가 합쳐지면서 탄생하였습니다.
  • 이는 자기 부모보다 랭크는 항상 낮다는 것을 의미합니다.

Property 2: Any root node of rank $k$ has at least $2^k$ nodes in its tree.

  • collorary: a node of rank $k$ has at least $2^k$ descendants.
    • 결국, 모든 노드들은 루트 노드였던 적이 한 번씩은 있었으며, 루트 노드에서 탈출하면 자신의 rank 또는 descendants의 집합들 둘다 변하지는 않습니다.
    • 게다가, 서로 다른 rank-$k$ 노드들은 공통된 descendants를 가질 수 없습니다. (Property 1에 의해 어떤 원소든 rank $k$인 ancestor가 최대 1개를 갖고 있기 때문)

Property 3: If there are n elements overall, there can be at most $n/2^k$ nodes of rank $k$.

  • 이 말은, 최대 $rank$가 $logn$이라는 뜻 입니다.
  • 모든 트리들의 높이가 $≤ log n$ 입니다.
  • find와 union 연산의 실행 시간의 upper bound가 바로 $log n$이 된다는 뜻 입니다.

추가 Union에 대해서

  • rank가 같은 트리가 합쳐지는 경우는 한 쪽이 rank가 올라갑니다.
  • rank가 다른 트리가 합쳐지는 경우는 큰 rank를 가진 트리가 올라갑니다(먹어버림).

Path compression

데이터 구조를 효율적으로 쓰는 방법

  • 실제로 Kruskal’s algorithm total time = $O(\vert E \vert log \vert V \vert)$ for sorting edges + $O(\vert E \vert log \vert V \vert)$ for the union, find operations
  • (sorting 알고리즘이 $n logn, n = \vert E \vert$이지만, $log \vert E \vert ≈ log \vert V \vert$라고 할 수 있습니다)
  • 이 때, 엣지들이 이미 sorting 되어 있거나, weight가 작아서 충분히 linear time안에 수행가능하다면?
  • 자료구조가 bottleneck이 될 것 입니다.
  • 따라서 연산마다 $log n$보다 더 좋은 성능을 찾아야 합니다.

그럼 어떻게 하면, $log n$보다 좋은 union, find 연산을 수행할 수 있을까요?

  • 정답은 자료구조를 좀 더 좋은 모양으로 가져가야 합니다.

img

각 find 동작 중에, 일련의 상위 포인터가 트리 루트까지 추적될 때 포인터가 루트를 직접 가리키도록 포인터를 모두 변경합니다.(그림 참조)

path compression heuristic은 find에 필요한 약간의 시간만 늘리며, 이로써 코드 구현이 쉬워집니다.

img

5.1.5 Prim’s algorithm

img

각 iteration 마다, $X$로 정의된 subtree는 한 개의 edge를 추가하면서 자라납니다.

  • 노드 $v ∉ S$를 $S$에 추가하는데, $cost(v) = min_{u \in S}w(u, v)$를 최소화하는 비용으로 해줍니다.

이는 Dijkstra’s algorithm과 비슷합니다.
차이를 보이는 건, priority queue가 key values에 의해 정렬되어 있다는 것 입니다.
node value에서도 차이를 보이는데, Prim 알고리즘에선 node의 value가 집합 $S$로부터 가장 가벼운 incoming edge의 가중치값 입니다. 반면에, Dijkstra 알고리즘은 시작점으로부터 해당 노드까지의 전체 path 길이 입니다.
그럼에도, 같은 실행 시간입니다.(특정 priority queue 구현에 따라 다름)
final MST는 prev 배열에 최종 저장됩니다.



Reference

  1. Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani(http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf)
  2. https://bowbowbow.tistory.com/26#union-find-%EB%9E%80
  3. http://seclab.cs.sunysb.edu/sekar/cse548/ln/amort1.pdf
  4. https://victorydntmd.tistory.com/102



© 2020. by GeonKimdcu

Powered by aiden