1. 최소 신장 트리 Minimum Spanning Tree )

최소 신장 트리( MST )란, 주어진 그래프에서 최소한의 비용으로 트리를 만드는 것을 의미합니다.

이전 글에서 살펴봤던 BFS, DFS는 각 규칙에 따라 모든 정점들을 연결하는 트리를 생성했었습니다.

MST도 마찬가지로 모든 정점들을 연결하는 트리를 생성하는데, 이 때 규칙은 최소한의 비용이 되는 그래프가 되도록 하는 것입니다.


이해를 돕기 위해 예제를 살펴보도록 하겠습니다.

MST는 이와 같이 연결된(connected) 무방향(undirected)의 가중치(weight) 그래프를 가정합니다.

각 간선의 가중치들은 방금 전에 언급한 비용(cost)을 의미합니다.


다시 말하면 MST는 모든 정점을 연결하여 트리를 생성하는데,

그 규칙으로써 가중치(비용)의 합을 최소화 하는 트리를 찾는 것이 목적입니다.




결과를 살펴보기 전에 어떤 정점들이 연결이 될지 예상해 볼까요?

각 간선들의 비용을 정렬해보았습니다.

MST의 정의대로라면 비용이 가장 적은 간선들이 연결되어 트리를 생성해야 할 것입니다.




MST의 결과는 위의 빨간색 간선들로 이루어진 트리입니다.

이 외의 간선들을 연결하는 순간 cycle이 형성되므로 트리가 될 수 없습니다.


현재 예제에서는 MST가 오직 한 개의 트리 밖에 생성할 수 없지만 

만약, ( v1 , v4 ) 간선이 없다고 가정한다면 ( v1 , v3 ) 간선 또는 ( v4 , v5 ) 간선이 선택될 수 있습니다.

즉 이 경우에는 두 개의 트리를 생성할 수 있게되죠.

이 처럼 MST는 여러 개의 트리를 생성할 수 있습니다.



지금까지 MST가 무엇인지 조금 느낌을 잡아봤습니다.


MST를 이용하는 대표적인 알고리즘은 Kruskal , Prim 알고리즘이 있습니다.

이 두 알고리즘에 대해서는 이어지는 글에서 설명하도록 하고, 그 전에 MST의 주요 용어에 대해 알아보도록 하겠습니다.





2. 주요 용어

MST에서 핵심이 되는 용어는 안전간선(Safe edge)입니다.

안전간선을 정의하기 위해서는 4가지의 용어가 필요하므로, 이 용어들을 살펴보고 안전간선을 정의하도록 하겠습니다.



1) 단절

단절은 트리의 모든 정점들의 집합을 V라고 할 때, 어떤 정점들의 집합 S가 있어서 두 개의 집합 ( S , V - S )로 나누는 것을 말합니다.

단순히 모든 정점들을 두 집합으로 분리했다고 생각하면 됩니다.



2) 교차한다

단절된 두 집합( S , V-S )에 대해, 간선( u , v )의 한 종점이 S, 다른 종점이 V-S에 속한다면 간선( u , v )는 단절( S , V - S )와 교차한다고 합니다.



3) 따른다

MST의 부분집합 A에 대해 단절을 건너는 간선이 없다면 단절이 집합 A를 따른다고 합니다.



여기서 파란색 간선들은 MST의 결과가 될 트리의 부분집합입니다.

즉, A는 파란색 간선들을 모두 갖는 집합이라고 할 수 있습니다.


단절이 A를 따른다는 것은 A의 간선 중 단절과 교차하는 것이 없다는 것을 의미합니다.

따라서 1번 그림은 단절이 A를 따르지만, 2번 그림은 단절이 A를 따르지 않습니다.




4) 경량간선

단절과 교차하는 간선 중 가중치가 최소인 간선을 경량간선이라고 합니다.




5) 안전간선

연결된 무방향 그래프 G=( V , E )에 대해서 A를 MST의 부분집합이라 하고,

( S , V - S )가 A를 따르는 어떤 단절이라 하며, ( u , v )를 단절과 교차하는 경량간선이라 할 때 ( u , v )는 A의 안전간선이라고 합니다.


안전간선은 위에서 언급한 용어들이 전부 언급되어 정의됩니다.

이해가 안되시면 정의의 용어들을 하나하나 생각해보시면 이해가 될 것입니다.


안전간선이 중요한 이유는 MST가 안전 간선들을 연결하여 트리를 생성하기 때문입니다.

즉, MST는 안전간선을 연결하여 트리를 생성하는 것이 규칙입니다.





이상으로 MST와 안전간선에 대해서 알아보았습니다.

이어지는 Kruskal 과 Prim 알고리즘에서 어떤 식으로 안전간선을 연결하여 트리를 생성하는지 눈여겨 보시기 바랍니다.