Minimum Spanning Tree

Spanning Tree(신장 트리)란 연결 그래프에서 모든 정점과 그래프 내의 간선들을 이용하여 구성하는 트리를 말한다. 즉, 연결 그래프 내의 간선들을 이용하여 모든 정점을 잇는 트리들을 신장 트리라고 부른다.

연결 그래프와 신장 트리

 

Minimum Spanning Tree(MST, 최소 신장 트리)란 가중치를 가진 연결 그래프에서 신장 트리를 만들 때에 간선의 가중치 합이 최소가 되는 신장 트리를 말한다. 이 때의 Minimum Spanning Tree는 연결 그래프 내에서 유일하지 않을 수 있다.

 

가중치 연결 그래프와 최소 신장 트리

 

최소 신장 트리는 전자 회로의 설계 시, N개의 핀을 연결 하기 위해 N-1개의 전선을 이용하여 전기적으로 동등하게 만드는 경우, 전선의 길이를 최소로 사용하는 방법을 고안하는 때에 사용되며, 이 외에 도로망 구축, 통신망 구축등과 같이 전체를 연결하는 데에 비용이 들억나느 경우 구축 비용을 최소로 만드는 때에 사용된다.

 

연결 그래프에서 최소 신장 트리, MST를