MST를 알고 있고, 크루스칼과 프림을 알고 있지만 그냥 쓰고있지 않은가? 이 글을 통해서 “왜 돼?” 에 대한 해답을 찾을 수 있었으면 좋겠다.
그래프가 주어졌을 때, 모든 노드를 연결하는 트리를 Spanning Tree라고 하고, 이 중에서 가장 간선의 가중치의 합이 낮은 트리를 Minimum spanning tree(이하 MST)라고 한다.
MST를 만드는 방법으로는 Prim, Kruskal 알고리즘으로 두 가지가 있으며, 각각 $O(ElogV), O(ElogE)$ 가 소요된다.
(그래프가 dense할 수록 $E$ 는 $V^2$ 에 가까워지며, $O(ElogE) = O(ElogV^2) = O(2ElogV)$ 로 비슷한 시간복잡도를 가진다.)
두 알고리즘 모두 그리디로 진행하며, 두 알고리즘의 증명 방법이 거의 같으므로 프림 알고리즘을 증명해 보겠다!
(증명은 수학적 귀납법을 기반으로 한다)
본격적 증명 전에, MST의 특성 중에 사이클이 존재하지 않는 것도 간단하게 알아보자.
만약 Cycle을 포함한 그래프가 정답이라고 한다면, Cycle에 존재하는 간선 하나를 제거해도 Spanning Tree임이 자명하다. 간선 하나를 제거하면서 정답보다 더 낮은 가중치 합을 가지는 Spanning Tree를 얻을 수 있고, 이는 Cycle을 포함한 Spanning Tree가 정답이라는 데에 모순이다. 따라서 MST에는 사이클이 포함돼있지 않다.
따라서, $V$ 개의 정점이 존재할 때 간선은 총 $V-1$ 개여야 한다.
Prim algorithm의 증명
프림 알고리즘은 size가 1인 트리에서부터 시작해서, 해당 트리에 인접한 간선 중에서 가장 낮은 가중치를 고르는 아이디어를 가진 그리디 알고리즘이다. 엄밀하게는 간선의 한 쪽 끝은 해당 트리에, 다른 한 쪽 끝은 해당 트리가 아닌 곳에 속해있는 간선 중에서 고른다.
해당 그리디 아이디어가 정당한지를 증명해야 한다.. (정확히 알고 써야지)
증명하기 위해서 매 반복(iteration)마다 불변한 Invariant를 설정한다.
Invariant: 매 반복마다, 프림 알고리즘이 만들어내는 트리 $T$ 는 MST $M$ 의 부분집합이다. $T \subseteq M$ (이 때의 $M$ 은 MST 중 하나이다)
- 위 Invariant가 항상 참이라는 것을 증명한다면, $V-1$ 번의 반복 이후에 $T=M$ 이 되고, 정당성을 증명하는 것이 된다. 수학적 귀납법을 사용해서 증명해보자.
Base case: $|T| = 0$ 인 경우
- Base일 때에는 당연히 성립한다. ($\emptyset \subset M$)
Inductive step: $k$ 번째 반복에서 알고리즘이 간선 $e$ 를 골랐을 때, $T\cup \{e\} \subseteq M$ 이다.
- 위 명제가 참이라고 (믿고) 가정하고, $k+1$ 번째 반복에서도 성립한다고 보이면, 프림 알고리즘의 Invariant를 증명한 셈이 된다! 두 가지 경우로 나누어서 생각해 보고, 필요에 따라서 더 가지를 쳐서 확실하게 증명해 보자.
Case 1: $e \in M$ 인 경우
- 프림 알고리즘이 선택한 간선 $e$ 가 정답 $M$ 에 속해 있다면, 위 step은 참이다.
Case 2: $e \notin M$ 인 경우
- 프림 알고리즘이 간선을 선택하는 조건은 현재 트리와 인접한 간선을 뽑는 것이므로, $e$ 의 한 쪽 끝은 $T$ 에 속하고, 다른 한 쪽 끝은 $T$ 에 속하지 않는다. $e = (u, v), u\in T, v\notin T$
- 이 때, $M$ 입장에서 해당 간선을 그어보면 사이클이 생기게 된다 ($e \notin M$ 이고, MST의 정의에 따라 $V$ 개의 간선이 생기므로, 해당 구간에서 사이클이 발생한다)
- 해당 사이클 안에는 $T$ 내부의 정점에서 출발해 $T$ 에 속하지 않는 정점을 끝점으로 하는 $e$ 와 다른 간선이 정확히 하나 발생한다. 이 간선을 $e\prime$ 라고 하자. $e\prime = (p, q), p\in T, q\notin T, e\prime \in M$
- $e\prime$ 또한 $T$ 와 인접하므로, 프림 알고리즘은 이번 반복에서 $e\prime$ 을 고를 수도 있었다. 다음과 같은 세 가지 경우를 생각해 보자. $w(x)$ 는 간선 $x$ 의 가중치를 의미한다.
Case 2-1. $w(e) \lt w(e\prime)$
- $M$ 에서 $e\prime$ 를 빼고, 방금 고른 $e$ 을 넣게 된다면 더 작은 가중치의 MST를 만들 수 있다. $M$ 이 MST 중 하나라고 했으므로, 가정에 모순이 된다.
Case 2-2. $w(e) \gt w(e\prime)$
- 이 경우에는 프림 알고리즘이 $e\prime$ 을 고를 수 없다. 트리와 인접한 간선 중 가장 낮은 가중치를 가진 간선을 뽑아내기 때문인데, $e$ 와 $e\prime$ 모두 $T$ 와 인접한다.
Case 2-3. $w(e) = w(e\prime)$
- Case 2-1과 같이, 지금 고른 것을 빼고 $e\prime$ 을 넣을 수도 있지만, 바꾼것과 바꾸지 않은 것 모두 정답이다.
모든 경우에 대해서 Invariant가 깨지지 않으므로 Invariant가 증명되었다. 이제는 Invariant를 통해 정당성을 증명할 수 있다. 한 번의 루프마다 하나의 정점이 추가되므로 $V-1$ 번의 루프를 진행하면 $V$ 개의 정점을 가지게 된다. 이 때, 프림 알고리즘이 만들어내는 트리 $T$ 는 MST $M$ 의 부분집합이므로 $T = M$ 이 돼 프림 알고리즘이 구해내는 트리는 MST임이 증명된다.
Kruskal algorithm의 증명
크루스칼 알고리즘 또한 MST를 만드는 알고리즘 중 하나이다. 크루스칼 알고리즘에서는 간선을 가중치를 기준으로 오름차순 정렬한 뒤, 가중치가 낮은 간선부터 방문하면서 간선의 양 끝이 서로 다른 트리에 속해 있다면, 간선을 추가해 두 트리를 합쳐주는 과정을 반복한다. 정점을 한 개씩 키워나가는 프림 알고리즘과 다른 점이다.
증명은 프림 알고리즘과 동일하게 할 수 있다. 간선 $e$ 를 골랐을 때, $e \in M, e \notin M$ 으로 나누어 생각하고, Case 2에서와 같이 세부 Case를 나누면 똑같이 증명할 수 있다.
다만 크루스칼 알고리즘은 간선의 양 끝 정점이 같은 트리에 위치해있는지를 알기 위해서 Union-Find 자료구조를 사용하는데, 해당 자료구조의 시간복잡도를 생각해줘야 한다.
find 함수의 시간복잡도가 $\alpha(V)$ 정도인데, 애커만 역함수로도 불리는 이 함수는 $\alpha(2^{65535}) = 4$ 정도로 굉장히 느리게 증가하는 함수이다.
따라서 정렬과 find, merge의 총 시간복잡도를 구하면 $O(ElogE)$ 를 도출해낼 수 있다.