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

신장트리

신장 트리(spanning tree)란 그래프내의 모든 정점을 포함하는 트리다. 신장 트리는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 또한 사이클을 포함해서는 안된다. 따라서 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다. 하나의 그래프에는 많은 신장 트리가 존재 가능하다. 

 

 

출처 : https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

 

출처 : https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221230994142&proxyReferer=https%3A%2F%2Fwww.google.com%2F

 

 

 신장 트리는 깊이 우선이나 너비 우선 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 또한 신장트리는 그래프의 최소 연결 부분 그래프가 된다. 여기서 최소의 의미는 간선의 수가 가장 적다는 의미이다. n개의 정점을 가지는 그래프는 최소한 (n-1)개의 간선을 가져야 하며 (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것은 바로 신장 트리가 된다. 

 

 

그렇다면 신장 트리는 어디에 사용될까? 

신장트리는 통신 네트워크 구축에 많이 사용된다. 예를들어 n개의 위치를 연결하는 통신 네트워크를 최소의 링크를 이용하여 구축하고자 할 경우, 최소의 링크수는 (n-1)이 되고 따라서 신장 트리들이 가능한 대안이 된다. 

 

 

출처 : https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

그러나 각 링크의 구축 비용은 똑같지가 않다. 따라서 단순히 가장 적은 링크만을 사용한다고 해서 최소 비용이 얻어지는 것은 아니다. 즉 간선에 비용을 붙여서 링크의 구축 비용까지를 고려하여 최소 비용의 신장 트리를 선택할 필요가 있다. 이것이 바로 최소 비용 신장 트리의 개념이다. 

 

 

 

최소 비용 신장 트리 

통신망, 도로망, 유통망 등은 간선에 가중치가 부여된 네트워크로 표현될 수 있다. 가중치는 길이, 구축 비용, 전송 시간 등을 나타낸다. 이러한 도로망, 통신망, 유통망을 가장 적은 비용으로 구축하고자 한다면, 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 최소 비용 신장 트리(MST: minimum spanning tree)가 필요하게 된다.

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

 

 

 

출처 : https://kingpodo.tistory.com/49

출처 : https://kingpodo.tistory.com/49

 

최소 비용 신장 트리를 구하는 방법으로는 Kruskal과 Prim이 제안한 알고리즘이 대표적으로 사용되고 있으며, 이 알고리즘들은 최소 비용 신장 트리가 간선의 가중치의 합이 최소이어야 하고, 반드시 (n-1)개의 간선만 사용해야 하며, 사이클이 포함되어서는 안 된다는 조건들을 적절히 이용하고 있다.