Minimum Spanning Tree, MST - 최소 신장 트리

임의의 그래프에서 가중치의 합이 최소인 최소 연결 부분 그래프.

 

부분 그래프 : 임의의 그래프에서 일부 간선을 제거한 그래프. 전체 그래프의 부분 집합.

연결 그래프 : 부분그래프 중에 그래프의 모든 두 노드 사이의 경로가 존재하는 그래프.

 

최소 신장 트리는 그래프의 특수한 경우인 트리, 트리의 특수한 경우이기 때문에

두가지 조건을 만족한다.

 

1. 사이클이 존재하지 않는다. - 트리의 특징.

2. 모든 노드가 연결되어 있다.