MST

MST(최소신장트리) 란 가중치가 주어진 그래프에서 가중치의 합을 최소로 하는 spanning tree를 말한다.

그래프의 유용한 속성

다음 세 가지 명제 중 두 개가 참이면 나머지 하나도 참이다.

• 그래프가 연결되어 있다.
• 그래프가 acyclic하다.
• 그래프가 |V|-1개의 간선만을 가진다.

Kruskal's algorithm

크루스칼 알고리즘은 최소신장트리를 찾는 하나의 알고리즘으로, 그리디 알고리즘에 속한다.

• 최소신장트리 T를 공집합으로 두자.
• 간선의 가중치를 기준으로 가장 작은 가중치를 가지는 간선부터 순회한다.
• 해당 간선이 T에 cycle을 형성하지 않으면 T에 추가한다.
• |T| = n-1이 될 때까지 반복한다. 만약 n-1이 되지 않고 종료된다면, 주어진 그래프가 disconnected인 것.

Proof

• 간단한 가정 : 모든 가중치가 구별 가능하다고 하자.

Lemma. ${S \subsetneq V}$가 공집합이 아닌 vertices의 집합일 때, 만약 S의 한 vertex와 V의 한 vertex를 endpoint로 삼고 최소 가중치를 가지는 간선 e가 있다면, 모든 MST는 e를 포함한다.

증명

${u \in S}$이고 ${v \notin S}$라고 할 때, 두 점을 endpoint로 잡는 최소 가중치를 갖는 간선 ${e = (u,v)}$가 있다고 하자.
귀류법을 위해, 해당 e를 포함하지 않는 MST인 T, 즉 ${e \notin T}$인 T가 있다고 가정하자.
그러면 ${T}$ 안에는 u와 v의 unique하고 simple한 path가 존재하고, 이는 ${S}$와 ${V/S}$, 즉 분리된 두 connected component를 연결하는 최소 하나의 간선을 포함한다. 이를 ${f}$라고 하자.
${e}$가 ${S}$와 ${V/S}$ 내에서 최소 가중치를 가지는 간선이므로 ${c(e) < c(f)}$가 된다.
이에 ${T}$에서 ${f}$를 제거하고 ${e}$를 포함시킨 ${T'=T \cup e / f}$도 신장 트리라고 할 수 있다.
그러면 cycle을 이루지 않고 n-1개의 간선을 가지는 것을 알 수 있다. 또한 연결이 해제되지 않는다.
그런데 ${c(e) < c(f)}$이므로 ${T'}$의 가중치는 ${T}$보다 반드시 작게 된다.

따라서 귀류법에 의해 S와 V의 임의의 vertex를 양 끝점으로 삼는 최소 가중치 간선 e를 포함하지 않는 Minimum Spanning Tree는 모순이다.

⌛️ Time Complexity

${O(|V|*|E|)}$.
O(|V|+|E| + |E|log|E| + |E||V|)이다.
V+E는 edge의 정렬을 위해 배열에 담는 시간과 adjacent matrix 혹은 list를 만드는 시간,
|E|log|E|는 간선을 정렬하는 시간,
|E|*|V|는 간선이 cycle을 만드는지 검사하는 시간이다. 이 때 이미 형성된 최소신장트리에서 edge는 V-1개보다 같거나 작기 때문에 BFS 혹은 DFS에 소요되는 시간이 O(|V| + |V-1|)보다 작고, 이를 모든 간선에서 돌리기 때문에 O(|E||V|)라는 복잡도가 나온다.