[알고리즘] MST 알고리즘 (1) - 그래프 분할 (cut property)

1. MST (Minimum Spanning Tree) 란?

 

MST는 "최소 신장 트리"라고 한다. 우리는 알고리즘에서 Minimum이 무엇을 뜻하는 지는 잘 안다. 그렇다면 Spanning Tree 무엇일까?

 

Spanning Tree

그래프의 모든 노드들을 연결하는 "트리" 이다.

즉 N개의 노드를 N - 1개의 링크(edge)를 통해 모두 연결한 트리이다.

완성된 Spanning Tree에는 당연히 사이클과 같은 트리에 없는 특성은 존재하지 않는다.

 

여기서 Minimum이 붙으면, edge들에 있는 가중치를 고려하여 최소 비용의 Spanning Tree를 선택한다는 것을 뜻한다. 만약 모든 edge들의 가중치가 같다면, Minimum을 찾을 이유는 없을 것이다.

 

MST를 정의하자면 다음과 같다.

 

그래프의 모든 Node들을 최소의 edge만을 이용해서 연결한 것 중에서 가장 작은 edge의 가중치를 가진 Tree

 

그래프 분할은 가장 간단하고 기본적인 MST 알고리즘 방식이다.

우리는 그래프를 분할함으로서 MST를 검증하거나 찾을 수 있다.

지금부터 알아보자.

---

2. 그래프를 자른다는 것의 의미

> cut

"그래프를 자르다"라는 의미, 다음 표와 같이 그래프가 완전히 끊겨야 제대로 된 cut이다.

 

> crossing edge

'1-3', '1-2', '7-2', '0-2', '4-6' 이렇게 잘리는 edge를 의미한다.

crossing edge는 모두 노드와 노드를 연결한다. 즉, 자를 수 있는 edge를 의미한다.

 

> cut property (올바르게 자른다.)

MST에서 가장 작은 가중치를 가진 crossing edge들을 통해서 cut을 한다는 것이다. 이에 대해서는 뒤에서 더 알아보자.

 

---

 

3. Cut Property를 이용한 MST 검증

 

우리는 이 cut property를 이용해서 MST를 검증할 수 있다.

다음과 같이 가장 작은 가중치의 edge들(MST)을 찾았다고 가정하자.

여기서 e는  MST에 없다고 가정한다.

 

 

 

만약에 내가 e를 추가하면, cycle이 생기고 더 이상 트리가 아니게 된다. 이것은 다른 edge f또한 crossing edge가 된다는 것을 의미한다. (e를 넣었을 때 f를 포함하여 cycle이 생기는 것이기 때문에)

만약에 f를 빼고 e를 넣으면 minimal 일지는 모르지만, 어쨌든 spanning tree가 된다.

만약 e의 가중치가 f의 가중치보다 작으면, 새 spanning tree가 가중치가 더 낮다는 의미이다.

이는 기존의 MST가 틀렸었다는 것을 증명하는 것이다.

 

---

 

4. 그래프 분할을 이용한 Greedy MST 알고리즘

 

다음과 같이 모든 그래프의 edge들이 파란색으로 시작한다.

우리는 빨간색이 아닌 edge들을 cut 할 것이다.

그리고 이 crossing edge들 중 가장 작은 가중치의 edge를 빨간색으로 칠할 것이다.

전체 node - 1 개수의 빨간색 edge가 남을 때까지 반복 할 것이다. (모든 노드가 연결되었음을 의미한다.)

 

 

(1 - 3), (1 - 2), (7 - 2),  (0 - 2), (0 - 6)를 자른다고 해보자.

여기서 가장 가중치가 작은 값은 (0 - 2)이다. 이를 빨간색으로 칠하자. 이러한 작업을 계속 반복한다.

 

 

이렇게 반복하다 보면, 다음과 같이 edge의 수가 node의 수 - 1이 된다.

이는 MST가 된다. 

 

만약에 빨간색 edge의 수가 node - 1 보다 작으면, 이는 그래프가 아직 연결되지 않은 것이다.

또는 빨간색 edge의 수가 node - 1보다 크면, 이는 사이클이 발생했음을 의미한다.

 

---

5. 마치면서

 

우리는 거의 그래프를 거의 아무렇게나 cut을 해서 MST를 찾았지만, 이렇게 막 자르는 것보다 더 효율적인 방법이 몇가지 있다.

이어서 설명할 알고리즘은 다음과 같다.

 

1. Kruscal's algorithm

2. Prim's algorithm