최소 신장 트리: 모든 정점을 가장 적은 총비용으로 연결하기
최소 신장 트리는 연결된 무방향 가중 그래프에서 모든 정점을 연결하면서 간선 가중치 합을 최소화한 트리다. 신장이라는 말은 원래 정점들을 모두 포함한다는 뜻이다. 사이클이 없는 연결 트리는 V개 정점에 정확히 V-1개 간선을 가진다.
모든 정점을 연결하되 사이클을 만들지 않으며 선택한 간선은 세 개다.
최단 경로와 목적이 다르다
도시들에 통신 케이블을 깔 때 어느 출발점에서 한 도시까지의 거리보다 설치하는 간선 전체 비용이 중요할 수 있다. 최소 신장 트리는 이 총합을 줄인다. 트리 위에서 특정 두 정점 사이의 경로가 원래 그래프의 최단 경로일 필요는 없다.
삼각형 A—B 비용 2, B—C 비용 2, A—C 비용 3이면 최소 신장 트리는 앞 두 간선을 골라 총합 4다. 그 트리에서 A→C 경로 비용은 4지만 원래 그래프의 직접 경로는 3이다. 목적 함수 차이가 결과 차이를 만든다.
컷을 가로지르는 안전한 간선
정점을 두 그룹으로 나누는 컷을 생각하자. 현재 선택한 안전한 간선들이 컷 내부에 있고, 컷을 가로지르는 가장 가벼운 간선을 고르면 최소 신장 트리에 포함할 수 있다. 다른 트리에 그 간선이 없으면 연결 경로의 더 무거운 횡단 간선과 교환하는 논리로 설명한다.
이 원리를 간선 중심으로 쓰면 크루스칼, 하나의 성장 중인 트리 중심으로 쓰면 프림 알고리즘이 된다. 알고리즘 이름보다 어떤 컷에서 최소 간선을 고르는지가 정확성의 근거다.
Vertices: A, B, C
Edges:
A -- B : 2
B -- C : 2
A -- C : 3
Chosen spanning tree:
A -- B : 2
B -- C : 2
Total tree weight: 4
Path A to C in the tree: 4
Shortest path A to C in the original graph: 3
같은 가중치의 간선이 있으면 최소 트리가 여러 개일 수 있다. 모든 간선 가중치가 서로 다르면 최소 신장 트리는 유일하지만, 가중치가 중복된다고 반드시 여러 답이라는 뜻은 아니다. 유일성과 총합 최적성은 따로 판단한다.
음수 가중치도 문제 정의와 알고리즘에 허용된다. 사이클을 반복해 비용을 줄이는 경로 문제와 달리 트리는 간선을 중복 사용하지 않는다. 그래프가 연결되지 않았다면 전체를 잇는 신장 트리는 없고 각 연결 요소의 최소 신장 숲을 구할 수 있다.
모든 정점 연결, 간선 수 V-1, 사이클 없음만 확인해도 신장 트리는 검증할 수 있지만 비용 최적성까지 자동으로 증명되지는 않는다. 실제 설계에서는 간선의 설치 비용, 장애 대비 중복 연결 요구, 방향성 여부도 확인해야 한다. 최소 트리는 중복 경로가 없어 장애 내성이라는 별도 목표에는 부족할 수 있다.
최소 신장 트리는 간선 수를 최소화한 다음 아무 간선이나 고르는 문제도 아니다. 모든 신장 트리는 V-1개를 가지므로 그중 가중치 합을 다시 비교해야 한다. 정점이 하나라면 선택 간선은 0개이며 총합 0인 자명한 트리가 된다. 이런 작은 경계 사례도 정의를 분명히 해 준다. 간선이 없다는 사실만으로 오류인 것은 아니다.