신장트리
- 정의 : G의 간선들로만 구성되고 G의 모든 정점들이 포함된 트리
- `깊이-우선 신장트리 (depth-first spanning tree)
- 너비-우선 신장트리 (breadth-first spanning tree)
- 신장트리는 G의 최소부분 그래프 (minimal subgraph) G'로서 V(G') = V(G)이고 G'는 연결되어 있음.
- 최소 부분 그래프 : 간선의 수가 가장 적은 부분 그래프
- 신장트리는 n-1개의 간선 가짐
- 통신 네트워크 설계에서 응용
- 정점이 도시, 간선이 도시 간의 통신 링크
- 통신 링크의 구축 비용이나 통신 링크의 길이에 가중치를 부여. 총비용이나 총 길이가 최소로 되는 신장 트리를 구함
최소비용 신장트리
- 최소비용 신장트리 (minimum-cost spanning tree) : 최저의 비용을 갖는 신장트리
- Kryskal, Prim, Sollin 알고리즘
- greedy method
- 최적의 해를 단계별로 구한다
- 각 단계에서는 몇 개의 판단 기준에 따라 최상의 결정을 내린다
- 한 번 내려진 결정은 뒤에 번복이 불가능하므로 각각의 결정이 가능한 해를 도출해낼 수 있는지 확인
- 신장트리의 제한 조건
- 그래프 내에 있는 간선들만을 사용
- 정확하게 n-1개의 간선만을 사용
- 사이클을 생성하는 간선을 사용 금지
Kryskal 알고리즘
- 최소비용 신장부분트리를 찾는 알고리즘
- 한번에 하나씩 T에 간선을 추가해가면서 최소비용 신장트리 T를 구축
- T에 포함될 간선을 비용의 크기순으로 선택
- 이미 T에 포함된 간선들과 함께 사이클을 형성하지 않는 간선만을 T에 추가
- G는 연결되어 있고 n > 0개의 정점을 가지므로 정확하게 n-1개의 간선만이 T에 포함됨
Prim 알고리즘
- 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성나무를 찾는 알고리즘
- 한 번에 한 간선씩 최소 비용 신장 트리를 구축
- 각 단계에서 선택된 간선의 집합은 트리
- 하나의 정점으로 된 트리 T에서 시작
- 최소 비용 간선 (u, v)를 구해 T ∪ {(u, v)}이 트리가 되면 T에 추가
- T에 n-1개의 간선이 포함될 때까지 간선의 추가 단계를 반복
- 추가된 간선이 사이클을 형성하지 않도록 각 단계에서 간선 (u, v)를 선택할 때 u 또는 v 중 오직 하나만 T에 속한 것을 고른다.
Sollin 알고리즘
- 간선이 하나도 없는 그래프의 모든 정점들로 구성된 숲에서 시작
- 각 단계에서 여러 개의 간선을 선택
- 각 단계에서는 포리스트에 있는 각 트리에 대해 하나의 간선을 선택
- 이 간선은 오직 하나의 정점만 그 트리에 속한 최소 비용 간선
- 선택된 간선은 구축 중인 신장트리에 추가
- 오직 하나의 트리만이 존재 or 더 이상 선택할 간선이 없을 때 종료