Prim 알고리즘 - 1

이번 포스팅에서는 Prim Algorithm을 소개하고, 그 정확성을 증명해보고자 한다.

 

다음 그림을 보자.

 

 

• 정점이 다섯 개가 있고 간선(edge)이 총 10개 있는 연결 그래프이다.
• 각 간선의 숫자는 노드에서 노드까지의 거리를 나타낸다.
• 위 그래프에서 MST(최소 비용 신장 트리)를 구하라.

 

 

 

 

 

 

 

 

용어

신장트리(Spanning Tree)

• 그래프 내 모든 정점을 포함하는 트리를 의미.
• 모든 정점이 연결되어 있어야 하고, 사이클을 포함해서는 안된다.
• 따라서 신장트리는 노드가 n개라면 정확히 (n-1) 개의 간선을 갖는다.

신장트리의 예시로는 다음이 있다.

 

이처럼 모든 노드가 연결되어 있고, 사이클을 만들지 않으면 Spanning Tree 완성이다.

간선의 수는 자연스레 (노드수 - 1) 이 된다.

 

우리가 위 문제에서 구하려는 건 MST(Minumum Spanning Tree) 로,

edge 숫자의 합이 가장 작은 스패닝 트리를 구하면 되는 문제이다.

MST는 그래프의 모양에 따라 답이 한 개일수도, 여러 개일 수도 있다. edge의 가중치 합이 가장 작은 것을 구하자.

 

즉 문제의 연결 그래프의 MST를 구하면 되는 문제이다. 이를 Prim 기법으로 풀어볼 것이다.

 

 

Prim 알고리즘

위 연결 그래프에서 시작 정점에서 출발해 신장트리의 집합을 단계적으로 확장하는 방법이다.

쉽게 시작 정점을 1번 노드라고 하겠다.

 

과정

1. 시작 단계에서 시작 정점만이 집합 MST 에 들어간다.

2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중 가장 낮은 가중치를 선택.

3. 위 과정을 (N-1)개의 edge 가 나올 때까지 반복한다.

단, 알고리즘이 간선을 선택할 때 사이클이 만들어지지 않도록 선택하는 것임! => mst 정의를 위반하면 안되기 때문이다.

 

위 과정을 통해 점차적으로 mst 집합을 확장해나가고, 정답이 나온다는 것인데

 

왜....?

저렇게 트리를 확장해가면서 최소 간선만 고른다고 mst 를 구할 수 있다니, 이해가 잘 되지 않았다. 따라서 이 Prim 의 정확성을 증명해보겠다.

 

 

정확성 증명

우선 prim 알고리즘이 선택한 답 외에도, 정답이 여러 개 있을 수 있다. 당연한 것이다.

노드에 간선이 많이 얽혀있다면 가중치의 합이 같은 여러 mst가 나올 수 있을 것이다.

 

그림은 mst 정답 중 하나라고 가정하자.

 

집합 T를 다음과 같이 정의하자.

• T: 간선들의 집합(edge set).
• T(mst): 정답들 중 하나인 mst의 edge set.

알고리즘이 단계를 거듭하면서 edge 를 하나씩 T 에 추가하며 T를 확장해나간다.

 

Invariant 를 통한 정확성 증명

Invariant: 

모든 단계에서 Prim이 만들어가는 답: T 라 하자. (T는 edge set)

이때 적어도 하나의 정답 T(mst)에 대하여 모든 단계에서 T ⊆ T(mst) 이다.

 

 

위 불변 조건이 알고리즘의 모든 단계에서 깨지지 않을 때, Prim 알고리즘의 정확성이 증명된다.

이제 이것을 수학적 귀납법으로 증명해보겠다.

 

proof by Induction

base:  |T| = 0
성립(OK). (edge 가 0개일 때 맨 처음 시작을 의미한다. 할 것이 없음)

 

step:  |T| = k 일 때, T ⊆ T(mst) 성립한다고 가정.

Prim은 계속해서 T를 늘려나갈 것이고, 늘려나갈 동안 정답 중에 적어도 하나의 T(mst)에 대해 T ⊆ T(mst) 이 성립함을 보이면 된다.

 

알고리즘이 한 번의 선택을 진행. 간선 e를 골랐다.

T -> T'

T' = T U {e}

 

case 1. T' ⊆ T(mst)

OK. 알고리즘이 고른 엣지 e가 정답 T(mst) 에 포함되는 경우. 성립.

 

case 2. T' ⊄ T(mst)   ( -> 다른 정답의 일부임을 보이면 된다.)

이 케이스의 경우 알고리즘이 고른 간선 e ∉ T(mst) 임을 의미한다. 이 경우 T'이 다른 mst의 일부임을 보이면 된다.

 

위처럼 빨간 선이 T, 초록색 선까지 이어진 부분이 T'이라고 하자.

T는 정답인 T(mst)에 포함되지만, 초록색 선은 정답에 포함되지 않은 간선을 그어 우리가 맨 처음 지정한 정답 중 하나인 T(mst) 에 사이클이 발생했다.

여기서 유의할 점은 알고리즘은 애초에 사이클이 생기지 않게 간선을 고른다. 싸이클이 발생했다고 적은 건 T(mst) 완료된 정답에서 보았을 때를 얘기한 거다.

 

• e는 T 에 맞닿아있는 노드(a) 에 인접.
• e의 양쪽 노드 중 T의 엣지에 인접하지 않은 노드가 있다 : b 노드
• 즉 간선 e의 양쪽 노드 중 하나는 T 에 인접하고, 하나는 그렇지 않다는 뜻이다.

 

a에서 싸이클을 돌아 b로 오는 길을 생각해보자. => e' 를 거쳐 옴. e' 도 고려대상이다. 

이때 e의 weight와 e'의 weight를 비교해보자.

 

1) w(e) < w(e')

(T(mst) - {e'}) U {e} = T''(mst) 즉 원래 가중치의 합보다 더 작으므로, 더 좋은 정답이 된다.

그런데 그림을 보면 원래 T(mst)는 e'을 포함하고 있는데, 그렇다면 이는 정답이 아니게 된다. => 가정에 모순!

애초에 T(mst)는 정답이 아니었던 것. 모순이다.

 

2) w(e) > w(e')

Prim 알고리즘이 애초에 e를 고르지 않는다. e'을 골랐겠지... => 모순

 

3) w(e) = w(e')

(T(mst)-{e'}) U {e}  => 이것도 정답이 된다.

어차피 e와 e'의 가중치는 같고 경로만 바뀌게 되는 것. 따라서 또다른 T(mst)의 정답이 된다.

 

P(N-1) 이 성립한다고 가정했을 때, P(N) 또한 성립함을 보였가. 따라서 귀납적으로 Invariant 는 성립하게 된다.

 

Conclusion

base, step 이 모두 만족하므로 귀납적 논리에 의해 Invariant 는 성립하게 된다.

불변 조건이 어디서나 만족하므로, Prim 알고리즘은 성립한다.

 

이렇게 Prim 알고리즘의 정확성을 증명해보았다.

 

다음 포스팅에서는 Prim 알고리즘을 직접 코드로 구현해보자.