최소신장트리(Minimum Spanning Tree)

최소신장트리란?  하나씩 분해하면서 살펴보자.

그림1. 최소 신장트리

Q. 신장트리란 ?

그래프는 각 정점과 정점간 연결된 에지의 집합임. G=(V,G).

그런 그래프중 모든 정점을 포함하고 & 정점간 서로 연결(connected)되어 있고 & 사이클(cycle)이 없는 그래프를 말한다. 

트리자료구조가 바로 이 조건에 성립하고 그래서 신장트리라고 함.

그림2 에서 (a)는 무방향 그래프인이고 모든 정점간 연결되어 있으나 사이클(a-b-c, b-c-d등등)이 존재해서 신장트리가 아니다.

(b), (c), (d) 는 모든 정점을 포함하고 & 정점이 서로 연결되어 있고 & 사이클이 하나도 없으니 신장트리라고 할 수 있음.

따라서 신장트리는 그래프의 부분그래프(subgraph) 라고 볼 수 있고 모든 신장트리는 정점 V 가 N개 라면 에지의 개수는 N-1 이 성립한다. 

 

그림2. 그래프(a) 에 대한 신장트리 (b), (c), (d)

 

Q. 그럼 최소신장트리란 ?

그림2. 처럼 그래프(a)의 부문그래프로 신장트리(b),(c),(d)는 여러개 나올수 있음을 확인하였다.
최소신장트리란 부분 그래프 중 연결된 간선의 모든 합이 최소가 되는 신장트리를 말한다.

따라서 최소신장트리가 되려면 그래프의 에지에 가중치가 있어야만 더 정확하게 설명가능. 왜냐하면 위 신장트리 b,c,d 는 모든 가중치가 1이기 때문에 최소신장트리의 개수는 신장트리의 개수와 동일하게된다.

가중치가 있는 그래프를 봐야 좀더 정확하게 이해된다.

 

그림3.  무방향 가중 그래프

그림3를 신장트리로 표현하면 아래 처럼 2가지가 나올수 있음. (사실 더 나올수도 있으나 예를 위해 2가지만 보여줌)

그림4. 최소비용 신장트리

그림4는 모두 신장트리인데 좌측 간선 가중치의 합은 15, 우측그림의 간선 가중치의 합은 10이다.

이렇게 그래프에서 신장트리 부분그래프중 모든 간선의 가중치 합이 최소가 되는걸 최소신장트리라고함.

당연히 가중치의 합이 최소가 되기위해 최소신장트리가 1개만 존재하지는 않다. 즉, 유일한 해만 있다는 뜻이 아니다. 

 

  Q. 최소신장트리를 어디에 쓰려고 만드나?

최소신장트리는 실생활에 아주 유용하게 사용된다. 예를들어 도시끼리 길을 연결하려 하는데 각 도시를 연결할때 최소비용이 드는 것을 구하려고 할때를 상상할 수 있다. 또한 네트워크망 구축이라던지 전기배서느 이미지프로세싱등 공학분야에 굉자히 다양한 방법으로 사용된다.

 

Q. 실생활에 많이 사용된다고하니 중요한건 알겠는데 최소신장트리를 만드는 방법은?

최소신장트리(MST)를 만드는 방법은 대표적으로 2가지 알고리즘이 있다.

첫번째는  크러스컬(Kruskal) 알고리즘  두번째는 프림(Prim's) 알고리즘 이다.