Spanning Tree
- A connected subgraph that contains all the vertices in G and is a tree.
- 비방향성 그래프 G의 모든 정점을 포함하고 있는 연결된 부분그래프이며 트리(사이클이 제거됨)이다.
Minimum spanning Tree
- A spanning tree with minimum weight in G and is a tree
- 신장트리중에 비용이 최소인 트리
최소비용신장트리의 적용 예
- 도로 건설 : 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는문제
- 통신 : 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제
- 배관 : 파이프의 총 길이가 최소가 되도록 연결하는 문제
관련 알고리즘
- Kruskal's Algorithm
- Prim's Algorithm