전체 연결 비용
세 정점 A,B,C 사이의 가중치가 AB=2, BC=3, AC=8이라면 AB와 BC를 고른 트리의 비용은 5다. 모든 정점을 연결하는 다른 두 간선 선택보다 합이 작으므로 최소 신장 트리다.
모든 신장 트리의 간선 수
정점이 n개인 유한 그래프의 신장 트리는 모두 간선이 n−1개다. 따라서 최소라는 말은 간선 개수만 비교한다는 뜻이 아니다. 가중치 합이 비교 대상이다.
답이 여러 개일 수 있다
삼각형의 세 간선 가중치가 모두 1이면 어느 간선을 빼도 합이 2인 신장 트리가 된다. 최소 비용이 같더라도 선택된 간선 집합은 여러 개일 수 있다.
최단 경로와의 구별
최소 신장 트리는 정점 쌍별 이동 거리를 모두 최소화하는 구조가 아니다. 특정 출발점에서 각 정점으로의 최단 경로를 모은 트리와도 목적이 다르다. 전체 연결 비용과 이동 경로 비용을 구별한다.
관련 문서
신장 트리 / 가중 그래프 / 최단 경로 / 연결 그래프 / 트리 (그래프 이론) / 무향 그래프 / 간선 (그래프 이론)