그래프 $G$의 부분 그래프 $T$가 어떤 최소 신장 트리의 부분 그래프이면, 이를 안전한 부분 그래프라고 부릅시다.
간선을 부분 그래프 $T$에 추가했을 때 얻어지는 부분 그래프 $T’$ 역시 안전하다면, 즉 어떤 최소 신장 트리의 부분 그래프라면, 그 간선을 안전하다고 부르겠습니다.
연결 그래프의 컷이란 정확히 두 개의 연결 요소를 가지는 부분 그래프를 이루는 간선과 정점의 부분집합을 말합니다. 어떤 간선을 추가했을 때 그래프가 다시 연결 그래프가 된다면, 그 간선은 주어진 컷을 가로지른다고 합니다.
최소 신장 트리를 찾는 모든 알고리즘은 다음 명제에 기반합니다:
안전한 간선에 관한 보조정리. 최소 신장 트리의 어떤 부분 그래프에 대해 임의의 컷을 생각해 봅시다. 그러면 이 컷을 가로지르는 간선 중 가중치가 최소인 간선은 안전합니다.
증명: 이 간선이 포함되지 않은 어떤 최소 신장 트리를 생각해 봅시다. 이 간선을 추가하면 사이클이 생기는데, 그 사이클에서 가중치가 이 간선보다 작지 않은 간선을 제거하면 확실히 더 나쁘지 않은 답을 얻을 수 있습니다. 모순입니다.
따라서 최소 신장 트리를 구성할 때는 탐욕적으로 행동할 수 있습니다. 즉, 각 단계에서 이미 구성된 신장 트리의 부분을 확장하는 최소 가중치의 간선을 추가하면 됩니다. 이를 수행하는 방법은 여러 가지가 있으며, 이에 대해서는 이어서 살펴보겠습니다.
#따름정리
- 모든 간선의 가중치가 서로 다르면 신장 트리는 유일합니다.
- 최소 신장 트리는 간선 가중치의 곱이 최소인 신장 트리이기도 합니다(모든 간선의 가중치를 그 로그로 바꾸어 보십시오).
- 최소 신장 트리는 가장 무거운 간선의 가중치가 최소인 신장 트리이기도 합니다.
- 신장 트리는 매트로이드의 특수한 경우입니다.