> For the complete documentation index, see [llms.txt](https://kde6260.gitbook.io/dev/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kde6260.gitbook.io/dev/minimum-spanning-tree.md).

# 최소신장트리(Minimum Spanning Tree)

최초작성일 \[2020.01.27]

### Minimum Spanning Tree

어떤 그래프를 트리로 간주하기 위해서는 아래의 조건을 만족해야 한다.

* 방향없는 그래프여야 한다.
* 모든 정점이 연결되어 있어야 한다. (적어도 `|V| - 1`개 이상의 간선이 있어야 한다.)
* 사이클이 없어야 한다. (두 정점 사이의 경로는 딱 1개만 있어야 한다.)

**최소신장트리(Minimum Spanning Tree)**란 

1. **그래프 내 모든 정점을 포함**하고
2. **그래프 내 모든 정점이 연결**되어 있으며
3. 임의의 **두 정점 사이의 거리를 최소**로 하고
4. 위 **트리의 조건을 만족**하는 

그래프를 의미한다. 어떤 그래프에서 최소신장트리를 찾기 위해 쓰는 대표적인 알고리즘은 크루스칼(Kruskal알고리즘)과 프림(Prim)알고리즘이다.

### Cut property

* `V` : 그래프 내 모든 정점
* `E` : 그래프 내 모든 간선
* `G` : `V`와 `E`로 이뤄진 그래프
* `X` : `G`에서 찾은 최소신장트리 `T`에 포함된 정점들

이라고 하고 `X`를 상호배타적인 두 부분집합으로 나누었을 때 두 집합을 각각 `S`, `V-S` 라고 하자.

![](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-LzbIVDL1LYylNzph2OT%2F-LzbJPOV-nS9uviRDbXB%2Fmst2.jpg?alt=media\&token=5d5eca44-ca72-4745-86b5-264fd2f1f88f)

가중치가 제일 작은 간선 `e`가 두 부분집합 `S`와 `V-S`를 연결한다면 `X + e` 또한 MST의 정점들이라고 할 수 있다. (이 때의 MST는 `T`와 다를 수 있다.) 이를 **cut property**라고 한다.

![](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-LzbIVDL1LYylNzph2OT%2F-LzbJV2RikQsDTMZXex-%2Fmst3.jpg?alt=media\&token=5a6933e2-3688-4e27-93ca-b32e8ed3ec8d)

**증명**

간선 `e`가 `T`에 포함되어 있지 않은 상태에서 `S` 와 `V-S`를 연결하는 간선 `e'`가 있고 

```
weight(e) < weight(e')
```

라고 하자.

![](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-LzbIVDL1LYylNzph2OT%2F-LzbMdZ7Q3um1R8RfAHZ%2Fmst4.jpg?alt=media\&token=5cbabcae-e3e4-4c38-b71d-5e4de7972d3e)

&#x20;`e`를 `T`에 추가하면 사이클이 생겨서 `T`는 MST 조건을 만족하지 못할 것이다. `e`의 가중치가 `e'`의 가중치보다 작으므로 `e'`를 T에서 제거하고 `e`를 추가하는 게 최적이므로 `T + e` 또한 MST를 만족한다고 볼 수 있다.

출처

* [ratsgo - MST](https://ratsgo.github.io/data%20structure\&algorithm/2017/11/28/MST/)
* [coursera - Algorithm on Graphs](https://www.coursera.org/learn/algorithms-on-graphs?)