컴퓨터알고리즘#17
LeeMir, 26 May 2021
최소신장트리
가중그래프
- 각 간선이 무게라 부르는 수치값을 가지는 그래프
- 무게(weight) : 거리, 비용, 시간 등
최소신장트리
- 신장 부그래프 : 그래프 G의 모든 정점을 포함하는 부그래프
- 신장트리 : (자유)트리인 신장 부그래프
- 최소신장트리 : G의 신장트리 가운데 간선 무게의 합이 최소인 것
- 싸이클 속성과 분할 속성을 가짐
- 싸이클 속성 : 최소신장트리에 간선 하나를 추가해 싸이클을 만들었을 때, 싸이클의 모든 간선은 새로 추가된 간선보다 무게가 작거나 같음
- 분할 속성 : G의 노드들을 두 개의 부분집합 U,V로 분할 후 간선 e를 분할을 가로지르는 최소 무게의 간선이라고 한다면, 간선 e를 포함하는 G의 최소신장트리가 반드시 존재