모든 정점을 최소 비용으로 연결하는 MST - Minimum Spanning Tre

MST는 그리디 알고리즘을 이용해서 구할 수 있는 트리의 한 형태이다.
연결 그래프(하나의 Connected Component로 이루어진 그래프)에서 생성할 수 있는 부분 그래프이기도 하다.
그래프의 형태를 한 네트워크 회선이 존재할 때, 네트워크 구축 비용을 최소로 하는 경우의 수를 찾고 싶을 때 쓰이기도 한다.

그래프 G=(V,E)와 같고, 각 edge에 weight가 주어져 있을 때,
아래의 두 조건을 만족하는 G'( V(G), T )가 MST이다.

1️⃣ G'은 Connected하다.
2️⃣ G'은 포함할 수 있는 edge들의 cost 총 합을 최소로 한다.

연두색: MST

해당 그래프에서는 연두색으로 칠해진 edge들을 선택했을 때 모든 vertex를 포함할 수 있으면서, cost의 합을 최소로 할 수 있기 때문에 MST라고 말할 수 있다.
물론 위의 그래프에서 MST는 여러 형태로 발생할 수 있다.

MST를 선택할 때에는 주의 사항이 있는데, Cycle을 포함해서는 안 된다는 것이다.
mst의 생성 과정에서 cycle이 포함되어 있을 시에는, 해당 cycle을 이루고 있는 edge 중 어느 것을 제거해도 connected 조건은 성립하기 때문에(=cost의 총합은 반드시 줄어든다) cycle을 생성할 수 있는 edge는 선택하지 않는다.

따라서 MST는 언제나 Acyclic하고, Connected하다는 조건을 가지고 있기 때문에 Tree로 정의된다.
이 때,MST의 성질은 유지하면서 2️⃣번 조건만 불충족할때는 Spanning Tree라고한다.