정점은 모두 남긴다
삼각형에서 간선 하나를 빼면 세 정점을 잇는 경로가 남는다. 원래의 모든 정점이 있고 연결되며 순환이 없으므로 신장 트리다. 정점을 하나 빼서 만든 작은 트리는 원래 그래프의 신장 트리가 아니다.
여러 선택이 가능하다
삼각형에서는 어느 간선을 제거하느냐에 따라 서로 다른 신장 트리가 나온다. 원래 그래프가 연결되어 있다고 신장 트리가 하나뿐인 것은 아니다. 원래 그래프가 트리라면 그 자체가 유일한 신장 트리다.
연결되지 않은 그래프
서로 떨어진 연결 성분들을 원래 간선만으로 하나의 트리로 이을 수는 없다. 이 경우 각 성분에서 신장 트리를 골라 신장 숲을 생각할 수 있다. 없는 간선을 새로 만들어 추가하는 것은 신장 트리 선택과 다르다.
가중치가 있을 때
간선마다 비용이 있으면 신장 트리들 가운데 간선 가중치 합이 가장 작은 것을 찾는 최소 신장 트리 문제가 된다. 단순히 간선 개수가 적다는 조건만으로 비용의 최솟값이 정해지지는 않는다.
관련 문서
트리 (그래프 이론) / 연결 그래프 / 연결 성분 / 최소 신장 트리 / 무향 그래프 / 순환 그래프 / 간선 (그래프 이론)