최소 신장 트리(Minimum Spanning Tree) - 3

1. 지금까지 정리

• 최소 신장 트리는 어떤 무방향 가중치 그래프가 주어졌을 때, 그 그래프의 모든 정점을 연결하면서, 가중치의 합이 최소가 되는 간선의 부분집합으로 정의했다.
• 최소 신장 트리를 구하는 Generic한 알고리즘은 아래와 같은 과정을 거친다.
  • 먼저 $A = \emptyset$ 인 집합을 선언한다.
  • 이 집합 $A$에 대해 안전한 간선을 하나 찾은 후, 이를 $A$에 더한다(Union)
  • $A$에 속한 간선의 개수가 $N - 1$개가 될 때 까지 2번을 반복한다.
• 이때 "안전하다(safe)" 라는 개념을 아래와 같이 정의했었다.
  • 어떤 MST의 부분집합 $A$에 대하여 $A \cup \{(u, v)\}$를 수행할 때 그 결과 역시 어떤 MST의 부분집합이 될 때 이 간선 $E(u, v)$가 $A$에 대하여 안전하다(safe) 라고 정의한다.
• 그리고 이 "안전한"간선을 찾기 위해서 필요한 정리를 알아보기 위해 용어 정리를 수행하였다. 각 용어의 정의는 아래와 같다.
  • 어떤 그래프 $G = (V, E)$가 있을 때, 그래프의 정점들을 두 개의 집합 $S$와 $V-S$로 분할한 것을 컷 $(S, V-S)$라고 부른다.
  • 어떠한 간선 $E(u, v)$에 대하여, $u \in S$이고, $v \in (V-S)$일 때 $E(u, v)$는 컷 $(S, V-S)$를 cross한다 라고 정의한다.
  • 간선들의 부분집합 $A$에 속한 어떤 간선도 컷  $(S, V-S)$를 cross 하지 않을 때 컷 $(S, V-S)$는 간선들의 부분집합 $A$를 존중한다(respect)라고 정의한다.
• 그리고 "안전한" 간선을 찾는 정리는 아래와 같았다.
  • 임의의 컷 $(S, V-S)$가 존재하고 이 임의의 컷이 어떤 MST의 부분집합 $A$를 respect 할 때, 컷 $(S, V-S)$를 cross하는 간선 중 그 가중치가 가장 적은 간선은 $A$에 대해 safe하다.

 

 

 

2. Kruskal 알고리즘

• Kruskal 알고리즘은 위에서 설명한 Generic MST 알고리즘을 구체화한 알고리즘이다. 해당 알고리즘은 매우 심플한데 대략적인 과정은 다음과 같다.
  • 어떤 MST의 부분집합 $A$를 선언한다. 이때 $A = \emptyset$ 이다.
  • 이후 모든 간선들을 가중치에 대해 오름차순으로 정렬한다.(sorting)
  • 이후 간선들을 그 순서대로 하나씩 선택한다. 이때 이미 선택된 간선들과 연결되었을 때 사이클을 형성한다면 선택하지 않는다.
  • 선택된 간선의 수가 $N - 1$개가 될 때 까지 3번을 수행한다.
• 보면 위에 있는 Generic MST와 거의 유사하다. 차이점이라면 safe한 간선을 찾는 것을 구체화시켜놓은 것이다.
• 여기에선 모든 간선들을 가중치에 대해 오름차순으로 정렬하므로, 안전한 간선을 찾는 정리를 만족시킨다.
• 이때 연결시켰을 때, 사이클이 형성되는지를 살펴보게 되는데 어떤 방식으로 사이클이 만들어지는걸 감지하는지는 조금 뒤에 알아보도록 하자.
• 여기서 유의해야 할 것은 "안전한" 간선을 찾는 것과. 이 간선을 선택해서 사이클이 발생하는것을 찾는 것은 별개의 문제이다. 즉 안전한 간선이지만 그것을 선택함으로서 사이클이 발생할 수 있다.
• 그림으로 어떻게 수행하는지를 살펴보자

• MST의 부분집합 $A$를 선언하였다.
• 이후 모든 간선들을 가중치에 대해 오름차순으로 정렬한다.(sorting)
• 이제 정렬한 간선들을 하나씩 선택해보자. 처음 1의 가중치를 가지는 $E(8, 7)$을 선택한다. 해당 간선을 선택함으로서 부분집합 $A$내부에서 사이클이 발생하지 않는다. 따라서 $A = \{A \cup E(8, 7)\}$을 수행한다.
• 이후 2를 가지는 간선 $E(7, 6)$을 선택한다. 해당 간선을 선택함으로서 사이클이 발생하지 않는게 명확하다. 따라서 동일하게 $A = \{A \cup E(7, 6)\}$를 수행한다.
• 이후 2를 가지는 간선 $E(9, 3)$을 선택한다. 역시 해당 간선을 선택함으로서 사이클이 발생하지 않는게 명확하다. 따라서 동일하게 $A$와 합친다.
• 이후 4를 가지는 간선 $E(2, 1)$, $E(6, 3)$을 선택한다. 둘 다 선택함으로서 사이클이 발생하지 않으므로 $A$에 포함시킬 수 있다.
• 여기까지 진행한 후의 그래프는 아래와 같다. 진한 색으로 칠해진 간선들이 $A$에 속해있는 간선들이다.

• 다음 6의 가중치를 가지는 간선 $E(9, 7)$을 선택해보자. 해당 간선을 선택할 경우에, $A$ 내부에서 사이클이 발생한다. 따라서 해당 간선은 적합하지 않으므로 다음으로 이어진다.
• 이후에 선택되는 7의 가중치를 가진 $E(9, 8)$도 동일하다. 사이클이 발생하기 때문에 선택해서는 안된다.
• 이후에 선택되는 7의 가중치를 가진 간선 $E(4, 3)$을 보자. 선택해도 사이클이 발생하지 않기 때문에 $A$에 포함시킬 수 있다.
• 이후에 선택되는 8의 가중치를 가진 간선들 $E(8, 1)$은 선택해도 사이클이 발생하지 않는다. 따라서 $A$에 포함시킬 수 있다. 하지만 그 다음 선택되는 간선 $E(3, 2)$는 선택할 경우 사이클이 발생해 선택할 수 없다.
  
  • 사실 이것은 반대로 $E(3, 2)$를 먼저 선택할 경우 $E(8, 1)$은 선택될 수 없다. 즉 MST는 유일하지 않다.
• 여기까지 진행하면 아래 그림과 같게 된다.

• 9의 가중치를 가지는 간선 $E(5, 4)$를 보자. 해당 간선을 $A$에 포함시켜도, 사이클이 발생하지 않는다. 따라서 해당 간선을 $A$에 포함시키고, 정점의 수가 $N$일 때, $N - 1$개의 간선인 8개의 간선을 모두 선택하였으므로 알고리즘을 종료한다.
• 최종적인 MST의 부분집합 $A$는 다음과 같을 것이다.

 

 

3. 정리

• Kruskal의 알고리즘의 대략적인 진행 방식을 살펴보았다.
• 현재 아직 설명되지 않은건 어떤 간선 $e \in E$를 선택할 때, 이 간선을 선택함으로서 사이클이 완성되는지를 어떻게 감지할 수 있는가? 가 있다.
• 다음 글에서 사이클의 감지를 kruskal 알고리즘에서 어떻게 수행하는지에 대해 알아보도록 한다.