최소 신장 트리(MST, Minimum spanning tree)란
정점(Vertex)의 집합 V와 가중치를 갖는 에지(edge)의 집합 E로 구성된 그래프 G = <V, E>가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 트리 T를 구하는 방법입니다.
길이가 최소가 되는 것이 좋다
실생활에서 찾아볼 수 있는 MST 문제의 예로 상수도관 네트워크 또는 도로 네트워크 설계가 있습니다. 상수도관 네트워크 설계의 겨우, 모든 사람에게 수돗물이 전달되어야 하고 전체 상수도관의 길이는 최소가 되는 것이 좋습니다. 이러한 문제를 해결할 때 최소 신장 트리가 적합합니다.
귀류법을 이용한 증명
- 귀류법이란 한 명제가 참인 것을 증며하려고 할 때에, 그 명제의 부정을 참이라고 가정하여 거기에서 나타나는 불합리성을 증명함으로써 원래의 명제가 참인 것을 보여주는 증명법이며 배리법이라고도 한다.
- 그래프 G의 정점으로 구성된 최소 신장 트리 T가 있다고 가정하면, T에서 에지 e를 하나 선택하여 제거합니다. e를 제거하면 T가 더 작은 트리인 T_1과 T_2로 나눠집니다.
MST문제가 최적 부분 구조 속성을 갖지 않는다고 가정했으므로 T_1`보다 작은 가중치를 갖는 신장 트리 T_1이 존재해야 합니다. 이 신장 트리 T_1`과 T_2를 에지 e로 연결한 새로운 신장 트리를 T`이라고 하겠습니다.T`의 전체 가중치가 T의 전체 가중치보다 작기 때문에 처음에 T가 최소 신장 트리라고 가정했던 가설이 틀리게 됩니다. 그러므로 MST문제는 최적 부분 구조 속성을 만족해야 합니다.
그리디로 선택
MST문제가 그리디 선택 속성을 갖는다면 정점 v와 연결된 에지 중에서 최소 가중치 에지는 반드시 최소 신장 트리 T에 속해야 합니다. 귀류법을 사용하여 기 사설을 증명할 수 있습니다.
- 정점 v에 연결되어 있는 에지 중에서 최소 가중치를 갖는 에지를 (u, v)라고 가정합니다.
- 만약 (u, v)가 T에 속하지 않는다면 T는 v와 연결되어 있는 다른 에지를 포함해야 합니다. 이 에지를 (x, v)라고 가정합니다. (u, v)가 최소 가중치 에지이기 때문에 (x, v)의 가중치는 (u, v)의 가중치보다 커야 합니다.
- T에서 (x, v)를 제거하고 (u, v)를 추가할 경우, 전체 가중치가 더 작은 트리를 얻을 수 있습니다. 이는 T가 최소 신장트리라는 가정에 위배됩니다. 그러므로 MST문제는 그리디 선택 속성을 만족해야 합니다.