[Tech, etc.] Minimum Spanning Tree(MST, 최소 신장 트리)

 MST를 알아보기에 앞서 Spanning Tree에 대해 알아보자. Wikipedia에 따르면 Spanning Tree에 대한 정의는 아래와 같다.

 

 In the mathematical field of graph theory, a spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree (see spanning forests below). If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T (that is, a tree has a unique spanning tree and it is itself).

: 수학 그래프 이론에서 방향을 갖지 않는 그래프 G의 Spanning Tree T는 하위 그래프로서 G의 모든 꼭지점(Vertex)를 포함하는 Tree다. 일반적으로 그래프는 여러 Spanning Tree를 갖지만 연결되지 않은 그래프(Not connected Graph)는 Spanning Tree를 갖지 않는다. G의 모든 간선(Edge)이 G의 Spanning Tree인 T의 간선(Edge)이기도 하면, G는 Tree고 T와 동치이다(즉, Spanning Tree를 하나만 갖는 Tree는 그 자체가 Spanning Tree다).

 조금 더 쉽게 이해하자면 Spanning Tree는 Cycle을 갖지 않고, 모든 꼭지점(Vertex)이 연결돼 있는 그래프로 생각하면 된다.

 

 MST에 대한 Wikipedia의 정의는 아래와 같다.

 

 A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

: MST 또는 Minimum weight spanning tree는 연결된 간선(Edges of a connected)의 부분집합으로, 모든 꼭지점(Vertex)을 함께 연결하는 가중치가 있고, 방향성이 없는 그래프이며, Cycle을 갖지 않고 간선의 가중치(Weight)의 합을 최소로 갖는다. 즉, Spanning Tree 중 간선의 가중치의 합을 최소로 갖는 Tree를 말한다. 좀 더 일반적으로 말하자면, 가중치를 갖는 간선으로 이뤄진 방향성이 없는 그래프(꼭 연결될 필요는 없는)는 Minimum Spanning Forest를 갖는다, 즉, 연결된 요소들을 갖는 MST의 합집합이다.

 

 MST의 조건 자체가 여러개라 이해하기 복잡하지만, 우선 Spanning Tree와 간선의 가중치의 합이 최소라는 것으로 나눠서 이해하면 조금 쉽다. MST는 실생활 여러 곳에서 실용적으로 적용된다. 대표적인 예로는 인터넷 케이블의 연결이 있고, 이외에도 도로와 가스 배관 등을 예로 들 수 있다. 가령 인터넷 케이블을 설치할 때 각 가정집에 모두 연결하면서 최소한의 비용이 발생하도록 설치할 것이다.

 

 MST에 대해 설명하는 그림을 찾아보면 일반적으로 그래프의 형태인 것을 알 수 있는데 Tree라고 부르는 것은 Tree의 정의가 Cycle을 갖지 않기 때문이다.

 

 MST에는 Kruskal's algorithm, Reverse Delete algorithm, Prim's algorithm과 같은 유명한 알고리즘이 있다.

 

참고

- https://en.wikipedia.org/wiki/Minimum_spanning_tree

- https://en.wikipedia.org/wiki/Spanning_tree

- https://new93helloworld.tistory.com/184