자료구조 | 신장 트리(ST), 최소 신장 트리(MST)

그래프와 트리의 개념을 배우고나면, 그 다음으로 딱 봐도 '실생활에서도 자주 응용되겠는데?' 싶은 개념이 등장한다. 

바로 '신장 트리'와 여기서 파생되는 '최소 신장 트리' 개념이다. 

---

신장 트리(Spanning Tree, ST)

신장 트리의 정의

그래프는 V(정점)와 E(간선)의 집합이다. 그리고 어떤 한 그래프에는 수많은 조합의 하위 그래프가 존재할 것이다.

이중에서 특별한 조건을 만족한 하위 그래프를 '신장 트리'라고 부른다. 

[신장 트리의 조건]
1. 주어진 연결 그래프의 모든 정점을 지나야 한다.
2. 동시에 트리여야 한다. 
     1) 사이클을 포함하지 않아야 한다.
     2) V = E+1 이어야 한다. (V: 정점의 수, E: 간선의 수)

 

 

신장 트리(Spanning Tree)에서 '신장'은 원래 이름인 'Spanning'을 그대로 번역해온 것으로 보인다. Spanning은 '확장하다', '포함하다'의 의미를 지니고 있다. 신장 트리의 조건을 생각해보면, Tree이긴 한데 모든 정점을 포함한다고 해서 Spanning이라는 이름이 붙은 것 같다.

 

 

어떠한 그래프가 연결 그래프라면 반드시 하나 이상의 신장 트리를 갖고 있다.

이 사실은 다음과 같이 증명할 수 있다.

1. 비어 있지 않은 연결 그래프를 가정:
   • 비어 있지 않은 연결 그래프 G를 가정한다.
2. 연결성 유지:
   • 그래프 G에서 임의의 간선을 제거하면서도 그래프의 연결성을 유지한다.
     • 만약 간선을 제거한 후에도 그래프가 연결 그래프를 유지한다면, 이 간선을 제거한다.
     • 이 과정을 더 이상 간선을 제거할 수 없을 때까지 반복한다.
3. 신장 트리 도달:
   • 위의 과정을 통해 더 이상 간선을 제거할 수 없게 되면, 남은 그래프는 연결 그래프의 모든 정점을 포함하며 사이클이 없는 트리 구조를 가지게 된다. 이렇게 얻은 트리는 신장 트리이다.

 

 

신장 트리의 유용성 (최소 신장 트리의 필요성)

'신장 트리라는 개념이 왜 유용한가?'라는 질문에 대해서는 백준 사이트의 '상근이의 여행' 문제를 예시로 들 수 있다. 

백준 9372번 (상근이의 여행) 문제:
상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다. 하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려고 한다. 이번 방학 동안의 비행 스케줄이 주어졌을 때, 상근이가 가장 적은 종류의 비행기를 타고 모든 국가들을 여행할 수 있도록 도와주자. 상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐 가도(심지어 이미 방문한 국가라도) 된다.

(https://www.acmicpc.net/problem/9372) 

뭔가.. 실제 현실에서도 해당 문제 상황과 비슷한 경우가 많을 것 같지 않나?

 

이 문제는 결국 모든 정점을 방문하면서, 최소한의 간선만을 거치는 신장 트리를 찾는 문제이다. 이처럼 '최소한의 간선', '최소한의 비용' 등 최소 비용을 구하는 조건까지 더해져야 비로소 신장 트리를 경제적인 측면, 효율성 측면에서 활용할 수 있게 되는 경우가 많다.

 

때문에 이러한 조건까지 추가된 그래프를 우리는 따로 '최소 신장 트리' 라고 부른다. 

 

(사실 위 문제처럼 최소한의 간선만을 원하는 문제라면 Unweighted Graph에서의 MST를 구하라는 건데, 그런 상황에서 MST를 찾는 알고리즘을 적용시키면 단순히 특정 연결 그래프의 ST를 찾았을 때의 결과와 동일한 결과가 출력된다.)

 

최소 신장 트리(Minimum Spanning Tree, MST)

"최소 신장 트리가 뭔가요?"

최소 신장 트리는 연결된 그래프에서 모든 정점을 포함하며, 간선의 가중치 합이 최소가 되는 트리이다.

 

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

 

2차원 그래프로 표현될 수 있는 현실 세계의 문제에서, 모든 지점(정점)을 연결해야 할 때, 최소 신장 트리는 연결 비용(간선의 가중치 합)을 최소화하는 경로를 제공한다.

 

그러나 이것은 '모든 정점을 순서대로 방문하는 최단 경로'를 의미하는 것은 아니다. 대신, 모든 정점을 연결하는 데 필요한 최소한의 비용을 찾는 것이다. 

 

즉, 최소 비용을 찾는 것이지 최단 경로를 의미하는 건 아니다. (그건 다른 개념으로 따로 정리돼있다.)

 

최소 신장 트리의 실제 응용 사례

• 도시 설계(도로 건설): 가장 적은 비용으로 여러 지역을 연결해야 하는 경우 이를 통해 이상적인 버전을 그려볼 수 있다.
• 통신 네트워크 구축: 최소한의 케이블로 모든 기기나 컴퓨터를 연결하도록 설계할 수 있다.
• 전력 그리드 설계: 전력을 효율적으로 전송하기 위한 전력선 구성을 설계할 수 있다. 

 

최소 신장 트리를 구하는 법

최소 신장 트리를 구하기 위해 다양한 알고리즘이 개발되었다. 이중 가장 대표적인 것들은 다음과 같다.

1. Kruskal 알고리즘: 간선을 가중치의 오름차순으로 정렬한 후, 사이클을 형성하지 않는 간선을 차례대로 선택한다.
2. Prim 알고리즘: 특정 정점에서 시작하여, 가장 가중치가 작은 간선을 선택하며 트리를 확장한다.

둘 다 그리디 알고리즘 원리를 기반으로 전개된다는 공통점이 있다.

자세하게는 다음 포스팅으로 따로 정리!