신장 트리(Spanning Tree)

신장 트리란?(What is a Spanning Tree?)

---

앞서 포스팅에서 깊이 우선 탐색과 너비 우선 탐색에 대해 다루었다. 연결 그래프 G = (V, E)에 대해서 깊이 우선 탐색이나 너비 우선 탐색을 하게 되면 정점들을 방문하면서 지나는 엣지들을 보면 트리 형태의 모양을 띄게 된다. 이러한 그래프를 탐색하면서 지나게 되는 엣지들의 집합을 트리 엣지(tree edge)라고 하고 트리 엣지를 제외한 나머지 엣지들을 비트리 엣지(nontree edge)라고 한다. 깊이 우선 탐색이나 너비 우선 탐색을 하게 되면 생기는 트리엣지로 이루어진 사이클을 갖지 않는  최소 부분 그래프가 생기는데 이 부분 그래프를 그래프 G에 대한 신장 트리라고 한다. 만약 n개의 정점을 가지는 그래프가 있다면 n개의 정점을 모두 연결할 수 있는 n-1개의 엣지로 이루어진 부분 그래프는 모두 신장 트리가 될 수 있다. 다음은 신장 트리의 예시를 그림으로 나타낸 것이다.

 

그래프에 대한 4개의 신장 트리

 

신장 트리는 깊이 우선 탐색으로 만들어진 신장 트리(depth first spanning tree)와 너비 우선 탐색으로 만들어진 신장 트리(breath first spanning tree)로 나누어 진다. 다음은 각 트리에 대한 예시이다.

 

 

최소 비용 신장 트리(Minimum Cost Spanning Tree)

---

각 엣지에 가중치가 부여된 무방향 그래프에서 만들어지는 신장 트리중 가중치의 합이 가장 작은 신장 트리를 특별히 최소 비용 신장 트리(minimum cost spanning tree)라고 한다. 이는 통신 네트워크나 빠른 길찾기등의 문제에서 많이 활용되고 있다.

 

위 그림을 보면 가중치가 부여된 그래프에서 나온 4개의 신장 트리가 있다. 각 신장 트리의 가중치의 합을 구해보면 가중치의 합에 대한 함수를 W(t)라고 정의했을 때 W(a) = 9, W(b) = 8, W(c) = 7, W(d) = 6이 된다. 4개의 트리중 가중치의 합이 가장 작은 신장 트리는 d이므로 위 그래프의 최소 비용 신장 트리는 d가 된다. 우리는 이러한 최소 비용 신장 트리를 실생활에서 많이 사용하고 있는데 항상 손으로 그려서 찾을 수는 없다. 최소 비용 신장 트리를 구하는 알고리즘은 크루스칼(Kruskal), 프림(Prim), 솔린(Sollin) 알고리즘이 있다.