[Algorithm] Spanning Tree와 MST (Minimum Spanning Tree)

Idea

Spanning Tree

Spanning tree는 그래프 내의 모든 정점을 포함하는 트리를 의미합니다. 그래프의 일부 간선을 이용해 만든 트리로서 항상 그래프의 부분집합이 됩니다. 이때 간선의 개수가 최소이어야 하며, 따라서 최소 연결 부분 그래프라고도 합니다.

N개의 정점에 대해서 모든 정점을 포함하는 트리를 만들기위해서는 최소 N-1개의 간선이 필요합니다. 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결합니다. 이때 사이클을 포함해서는 안됩니다.

 

MST (Minimum Spanning Tree)

MST는 한 그래프에 대한 Spanning Tree 중에서 간선들의 가중치 합이 최소인 트리를 의미합니다.

그림에서 아래 3개의 신장 트리 중에서 가중치 합이 가장 적은 가운데 신장 트리가 바로 MST가 되는 것입니다.

 

정리

정리하면 아래와 같습니다.

신장 트리 (Spanning Tree)

• 위의 그림 그래프에서 아래 그래프 3개 모두 신장 트리(3개 말고 더 있을 수 있음)
• 그래프의 모든 정점을 포함하는 트리
• 그래프의 최소 연결 부분 그래프로 사이클이 없음
• 정점의 개수 n개면 간선의 개수 n-1개 가짐
• 하나의 그래프에 많은 신장 트리 존재

최소 신장 트리 (MST, Minimum Spanning Tree)

• 신장 트리 중 간선의 가중치 합이 최소인 트리