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

 신장 트리란 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리를 일컫는다.

 

그렇다면 최소 신장 트리는 무엇일까?

최소 신장 트리는 위에서 구한 신장 트리 중에서, 사용된 간선들의 가중치의 합이 최소인 트리를 말한다.

 

즉 모든 정점을 방문하는 간선의 부분 집합은 무수히 많지만,

 

그 중에서 간선이 가지는 가중치의 합이 가장 작은 트리를 말하는 것이다.

 

최소 신장 트리의 특징으로는

 

- 무방향성이고 가중치를 가지는 그래프

 

- 그래프에서 간선이 가지는 가중치의 합이 최소

 

- N개의 정점을 가지는 그래프에서 반드시 (N-1)개의 간선을 사용

 

- 사이클 미포함

 

등을 들 수 있다.

 

 

최소 신장 트리를 사용하는 이유는 각 정점을 잇는 작업에서 비용을 최소화해야 할 때 사용할 수 있기 때문에 

 

도로망, 통신망, 유통망 등을 설계할 때 쓰일 수 있기 때문이다.

 

 

최소 신장 트리의 대표적인 방법으로는 크루스칼, 프림 알고리즘 등을 들 수 있다.

 

 

라고 이해했다.