MST, minumum spanning tree
최소신장트리
Last updated
최소신장트리
Last updated
입력 : n개의 도시가 있고, 도시와 도시를 연결하는 도로 비용이 주어진다.
출력 : 최소 비용으로 모든 도시들이 서로 연결되도록 하려고 한다.
무방향 가중치 그래프 G=(V, E)
이때 가중치는 양의 정수이다.
각 엣지 (u, v) 가 E에 속할 때, 가중치 w(u, v) 가 주어진다.
문제는 다음과 같은 조건을 만족하는 엣지들의 부분집합을 찾는 것이다.
T에 속한 엣지들에 의해 그래프의 모든 정점들이 서로 연결된다.
가중치의 합이 최소가 된다.
일반적으로 컴공에서는 사이클이 없는 연결된 무방향 그래프를 트리라고 부른다.
MST 문제의 답은 항상 트리가 된다.
MST 를 찾으면 우선 모든 엣지들이 서로 연결되어있고 사이클을 만들지 않게 된다.
사이클을 이루게 될 경우, 사이클 상에서 하나의 노드를 버려도, 나머지 노드들이 서로 연결될 수 있기 때문이다. 그렇게 되면 애초에 MST가 되지 않는다. 왜냐하면 사이클을 이루는 노드들을 모두 제거해서 사이클이 안만들어질 때가지 제거하면 가중치가 최소값이 되므로, 굳이 사이클을 이룰 필요가 없는 것이다.
따라서 MST 의 경우는 항상 무방향이고 사이클을 이루지 않으며, 트리모양을 띄게 된다.
노드가 n개인 트리는 항상 n-1개의 엣지를 가지게 된다.
네트워크 디자인에서 많이 사용된다. 반드시 사용된다고는 할 수 없지만, 가장 기본적인 기준점이 될 수 있다.
통신망, 도로망, 자전거도로 등
어떤 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가 될 수 있다.
