[ch 14] 그래프_3(최소 비용 신장 트리)

[주제]

- 최소 비용 신장 트리의 개념

[정의]

- 트리도 그래프의 한 유형

- 경로: 두 개의 정점을 잇는 간선을 순서대로 나열한 것

■ 그림(그래프의 사이클)

- 정점 'B에서 D'에 이르는 경로의 경우의 수

▷ B - A - D

▷ B - C - D

▷ B - A - C - D

▷ B - C - A - D

- 위 경로는 '단순 경로'에 속함

  ※ 동일한 간선을 중복하여 포함하지 않는 경로

- 아래 경로는 단순 경로가 아닌 경우의 예

▷ B - A - C - B - A - D

- 오른쪽 그림의 경우 시작지점과 종료지점이 같은 경로를 '사이클'이라 함

- 사이클을 형성하지 않는 그래프의 예

- 사이클을 형성하지 않는 그래프는 회전할 시 트리와 같은 모양새를 갖춤

- 그래서 이런 그래프를 '산장 트리(Spanning Tree)'라고 함

[신장 트리의 특징]

- 그래프의 모든 정점이 간선에 의해서 하나로 연결되어 있음

- 그래프 내에서 사이클을 형성하지 않음

[최소 비용 신장 트리(Minimum Cost Spanning Tree, MST)]  ※ 또는 최소 신장 트리

- 가중치가 있는 그래프에서 모든 간선의 가중치 합이 최소인 그래프

- 최소 비용 신장 트리에 사용되는 대표적인 2개의 알고리즘이 존재

▷ 크루스칼(Kruskal) 알고리즘: 가중치를 기준으로 간선을 정렬한 후에 MST가 될 때까지,

 간선을 하나씩 선택 또는 삭제해 나가는 방식

▷ 프림(Prim) 알고리즘: 하나의 정점을 시작으로 MST가 될 때까지 트리를 확장해 나가는 방식

    ※ 책에는 없으므로 나중에 조사하여 추가

■ 그림(크루스칼 알고리즘 - 오름차순 방식)

- 가중치를 기준으로 간선을 오름차순으로 정렬

- 낮은 가중치의 간선부터 시작해서 하나씩 그래프에 추가

- 사이클을 형성하는 간선은 추가하지 않음

- 간선의 수가 정점의 수보다 하나 적을 때 MST는 완성됨

- 가중치에 중복이 없다는 가정에 오름차순 정렬하여 낮은 값부터 연결하는 방식

- 가장 낮은 '2'부터 연결 시작

- '2 ~ 6'까지 특이사항 없이 반복적으로 연결

- '7' 연결 시 'C - D - F' 사이클이 발생됨

- 그러므로 '7'은 연결되지 않고 넘어가서 '8'을 연결

- '8'이 연결되었을 때 모든 정점이 연결되었으므로, 더 이상 연결을 진행하지 않고 종료

★ 종료 시점: 간선의 개수 + 1 = 정점의 개수

■ 그림(크루스칼 알고리즘 - 내림차순 방식)

- 가중치를 기준으로 간선을 내림차순으로 정렬

- 높은 가중치의 간선부터 시작해서 하나씩 그래프에서 삭제

- 두 정점을 연결하는 다른 경로가 없을 경우 해당 간선은 제거하지 않음

- 간선의 수가 정점의 수보다 하나 적을 때 MST는 완성됨

- 가중치를 내림차순으로 정렬

- 가장 높은 값인 '13'부터 시작 및 간선 제거

- '13 ~ 9'까지 반복

- '8'을 삭제하려 할 때 정점 'A'가 연결되지 않는 문제를 발생하기 때문에 삭제하지 않음

- '8'은 무시되고 '7'이 삭제됨

- '7'이 삭제됐을 때 모든 정점이 간선 하나씩만 유지된 상태이므로 더 이상 진행하지 않고 종료

★ 종료 시점: 간선의 개수 + 1 = 정점의 개수