MST, minumum spanning tree
최소신장트리
최소신장트리
입력 : n개의 도시가 있고, 도시와 도시를 연결하는 도로 비용이 주어진다.
출력 : 최소 비용으로 모든 도시들이 서로 연결되도록 하려고 한다.
무방향 그래프
무방향 가중치 그래프 G=(V, E)
이때 가중치는 양의 정수이다.
각 엣지 (u, v) 가 E에 속할 때, 가중치 w(u, v) 가 주어진다.
문제는 다음과 같은 조건을 만족하는 엣지들의 부분집합을 찾는 것이다.
T에 속한 엣지들에 의해 그래프의 모든 정점들이 서로 연결된다.
가중치의 합이 최소가 된다.
왜 트리라고 부르는가
일반적으로 컴공에서는 사이클이 없는 연결된 무방향 그래프를 트리라고 부른다.
MST 문제의 답은 항상 트리가 된다.
MST 를 찾으면 우선 모든 엣지들이 서로 연결되어있고 사이클을 만들지 않게 된다.
사이클을 이루게 될 경우, 사이클 상에서 하나의 노드를 버려도, 나머지 노드들이 서로 연결될 수 있기 때문이다. 그렇게 되면 애초에 MST가 되지 않는다. 왜냐하면 사이클을 이루는 노드들을 모두 제거해서 사이클이 안만들어질 때가지 제거하면 가중치가 최소값이 되므로, 굳이 사이클을 이룰 필요가 없는 것이다.
따라서 MST 의 경우는 항상 무방향이고 사이클을 이루지 않으며, 트리모양을 띄게 된다.
노드가 n개인 트리는 항상 n-1개의 엣지를 가지게 된다.
사용
네트워크 디자인에서 많이 사용된다. 반드시 사용된다고는 할 수 없지만, 가장 기본적인 기준점이 될 수 있다.
통신망, 도로망, 자전거도로 등
generic MST 알고리즘
어떤 MST 의 부분집합 A에 대하여 A에 새로운 엣지 (u, v)를 추가한다고 하더라도, 여전히 MST의 부분집합이 될 만큼 안전하다라고 표현할 수 있다.
어떤 엣지를 포함하는 MST에 대하여 엣지 1을 포함하는 MST 가 존재한다고 해서 "엣지 1은 MST에 반드시 소속된다"고 표현할 수 없다.
"엣지 1을 포함하는 MST가 존재할 수 있다."로 표현할 수 있을 뿐이다.
MST의 해는 하나가 아니라 여러개일 수 있기 때문이다.
진행순서
먼저 처음에는 MST의 부분집합 A는 공집합으로 시작한다.
그 뒤, 집합 A에 대해서 안전한 엣지 하나를 찾은 후, 이것에 A를 더한다.
엣지의 개수가 n-1이 될 때가지 2번을 반복한다.
엣지의 개수가 n-1이라는 뜻은 n개의 노드가 모두 연결되었음을 의미한다.
문제는 어떻게 "안전한 엣지"를 찾는가...?
안전한 엣지 찾기
그래프의 정점들을 두 개의 집합 S와 V-S 로 분할하고 이를 컷(S, V-S)이라고 부르자.
에지 (u, v)에 대해서 u가 S에 소속되어있고, v가 V-S에 소속되어있을 때, 에지 (u, v)는 컷(S, V-S)을 크로스한다고 말할 수 있다.
엣지들의 부분집합 A에 속한 어떤 엣지도 컷(S, V-S)를 크로스 하지 않을 때, 컷(S, V-S) 는 부분집합 A를 존중한다(respect)고 말한다.
즉, A가 어떤 MST 의 부분집합이고(A를 포함하는 MST가 존재할 때), (S, V-S)는 A를 존중하는 컷이라고 한다면, 이 컷을 cross 하는 엣지들 중에서 가장 가중치가 작은 엣지(u, v)는 A에 대해서 안전하다.
결국, A가 어떤 MST의 부분집합이므로, 빨간 트리로 표시되고 있는 A는 MST를 이룬다는 것을 보장하는 상태이다.
이때, S와 V-S를 cross 하는 엣지 중에서 최소의 가중치를 가진 엣지를 선택하면 MST가 될 수 있다.
Last updated
