[MST - 1] Minumum Spanning Tree

이번에는 MST(Minumum Spanning Tree)에 관해서 알아봅시다. 한국어로는 최소 신장 트리라고하는데, MST를 보기 전에 먼저 Spanning Treed에 대해서 봅시다.

Spanning Tree ? graph의 최소 연결 부분으로 나타낸 Tree

최소 연결 부분이라는 것이 안 와닿을 수 있는데, n개의 정점을 가지는 graph에서 간선의 수가 최소로해서 나타내는 것입니다. 간선의 수가 최소가 된다는 거는 정점은 일대일로 연결이 되어 있다는 것이겠네요!

이런 경우 반드시 Tree의 형태가 되기 때문에 Spanning Tree라고 한다는 군요. 그림으로 보면 바로 이해가 될 것입니다.

이제 MST를 살펴봅시다. 결국 Minumum Spanning Tree라는 것은 Spanning Tree 중 가중치가 가장 작은 Tree라는 것이겠네요. 그림으로 보면 바로 이해될 것입니다.

MST에서는 숙지할 용어가 몇가지 있어요.

---

1. Cut(단절)
2. Crossing(교차)
3. Light Edge(경량 간선)
4. Respect(따른다, 존중)
5. Safe Edge(안전 간선)

---

1. Cut

---

정점의 전체 집합 V에 대해서 정점 집합 S가 있다고 합시다. 그러면 S와 V-S 두 부분으로 나눠지게 되는데, 이런 경우를 Cut이라고 하고 (S,V-S)라고 표현합니다.

2. Crossing & Light Edge

---

이번엔 Crossing이랑 Light Edge입니다.

그림에서 본 것처럼 두 영역(Cut)을 교차하는 간선 e가 있을 때, 간선 e는 (S,V-S)를 Cross(교차)한다.라고 합니다. 위 그림의 경우는 교차 간선이 1개일 뿐이지만, 교차 간선이 여러개 중 가중치가 가장 작은 간선을 Light Edge, 경량 간선이라고 합니다.

3. Respect

---

제가 MST를 공부하면서 이 단어를 해석하는 것에 따라 조금 표현이 다른데, 어떤 분은 따른다라고 표현하고, 어떤 분은 존중한다라고 표현하더라구요. 전 그냥 Respect라고 하겠습니다.ㅋㅋㅋㅋㅋㅋ

간선 집합 A가 있다고 합시다.(그림에서는 빨간 간선들이에요.) 이 때 간선의 집합이 Cut (S,V-S)를 교차하는 간선을 포함하고 있지 않다면

간선 집합 A는 Cut(S,V-S)를 Respect한다.라고 합니다. 음.. 침범안하니까 존중..?이런 의미..??

4. Safe Edge

---

마지막으로 볼 용어는 Safe Edge입니다. 먼저 Safe Edge의 정의를 보면 이러합니다.

간선 집합 A에 대해서 Cut(S,V-S)를 Respect하고, 간선(u,v)가 Cut(S,V-S)를 교차할 때, (u,v)는 A의 Safe Edge이다.

조금 헷갈리네요!!!! 그림으로 봅시다!

그림에서 집합 A를 빨간 간선들이라고 합시다. 지금 A는 (S,V-S)를 Respect하고 파란 간선은 Cut을 교차하네요. 이런 경우를 Safe Edge라고 하는군요!!!

---

MST는 통신망, 도로망, 유통망에서 길이, 구축 비용, 전송 시간 등을 최소로 구축하려는 경우 사용한다고 합니다.

다음 포스트에서는 MST를 구축하는 알고리즘인 Krustal, Prim Algorithm에 대해서 알아봅시다.

저도 미숙하기 때문에, 제가 작성한 내용에서 틀린 것이 있다면 피드백 부탁드립니다^^ ㅂㅂ~~