[고급 자료구조] Graph: Minimum spanning tree

1. Minimum spanning tree

가중 그래프 + 무방향 그래프의 하위 트리 중,

그래프의 모든 정점을 포함(spanning subgraph)하고, 사이클이 없으며, 가중치의 합이 최소인 하위트리를 말합니다.

 

2. Cut

• 그래프의 정점들을 두 개의 분리된 집합으로 나누는 것을 의미합니다.
• 각 집합은 비어있지 않습니다.

 

Cut-Set

• 컷을 통해 나뉜 두 집합의 정점들 사이를 잇는 모든 간선의 집합
  • 한 집합의 정점들과 다른 집합의 정점들 사이의 연결을 나타냅니다.
• Cut-Set에 속한 간선들을 제거하면, 그래프는 두 개의 연결되지 않은 부분 그래프로 나뉘게 됩니다.

 

Cut Property

• cut-set의 간선 중, 가중치가 가장 작은 간선들은 반드시 모든 MST에 포함됩니다.
  • 가장 가벼운 간선을 선택함으로써, 최소 신장 트리를 구성하기 때문입니다.
  • MST 알고리즘의 근간 개념입니다.
• 가장 가벼운 간선이 여러 개일 경우, MST가 여러개일 수 있음을 의미합니다.

 

3. 예시

전화망

• unique minimum spanning tree

 

 

출처

• Wiki - Minimum spanning tree
• Wiki - 신장 부분 그래프