신장 트리 (Spanning Tree)

  • 조건 : 그래프 G는 connected graph이다.
  • 정의 : 그래프 G의 spanning tree는 다음 성질을 만족하는 G의 부분 그래프이다.
    1. G의 모든 정점들이 포함되어야 한다.
    2. connected 그래프이어야 한다.
    3. 사이클을 포함하지 않아야 한다.
  • 신장트리는 다음 두 가지 방식으로도 구할 수 있다.
    • DFS : DFS를 돌린 후 각 노드 v마다 (pred[v], v) 간선을 선택한다.
    • BFS : BFS를 돌린 후 각 노드 v마다 (pred[v], v) 간선을 선택한다.
  • 그래프 G의 신장트리 G'는
    • V(G') = V(G)이고
    • G'는 연결 되어있는
    • 최소 부분 그래프(Minimal Subgraph)이다.
  • 정점수 n인 그래프의 신장 트리는 n - 1개의 간선 가짐

최소비용 신장트리(Minimal-cost Spanning Tree)

  • 최저 비용을 갖는 신장 트리
  • Kruskal, Prim, Sollin 알고리즘
  • 탐욕 알고리즘 (greedy method)
    • 최적해를 단계별로 구한다
    • 각 단계에서는 몇 개의 판단 기준에 따라 최상의 결정을 내린다
    • 한 번 내려진 결정은 뒤에 번복이 불가능하므로 각각의 결정이 가능한 해를 도출해낼 수 있는지 확인
  • 신장트리를 만드는 제한 조건
    • 그래프 내에 있는 간선들만을 사용
    • 정확하게 n - 1개의 간선만을 사용
    • 사이클을 생성하는 간선을 사용 금지

Kruskal 알고리즘

  • 알고리즘

    1. 먼저 초기에 G로부터 부분그래프 T를 생성한다.
      • 처음에 T는 정점들만 가진 부분 그래프에서 시작한다.
    2. 다음과 같이 한 번에 하나씩 T에 간선을 추가해 간다.
      • 단, 추가할 경우 T에 사이클이 나타나지 않게 하는 간선을 선택해야 함
      • 종료 조건 : 총 선택된 간선의 수 = n - 1이면 종료함
      • T는 n개의 정점을 가지며 사이클 없이 n - 1개의 간선만이 T에 포함됨
  • 매 단계에서 T는 여러 개의 트리를 가짐 (통틀어서 Forest라고 부른다)

  • 과정 예시

Prim 알고리즘

  • Kruskal 방식과 달리 매 단계에서 T는 하나의 트리임

  • 방법

    1. 하나의 정점으로 된 트리 T에서 시작
    2. T에는 없는 간선 중 한 정점이 T에 속하는 간선 하나를 선택
      • 이러한 간선을 찾을 수 없으면 알고리즘을 종료함 (실패로 종료)
      • 그런 것들 중에서 최소의 비용의 것을 선택
        -> 이 경우 사이클을 일으키지 않음. 한 노드가 T에 없으므로
      • 이 간선을 T에 추가함
        -> 이 결과로 커진 T는 트리 하나로 구성됨
    3. T에 n - 1개의 간선이 포함되어 있으면 성공으로 종료. 그렇지 않으면 다시 위의 작업을 반복
  • 과정 예시

Sollin 알고리즘

  • 알고리즘

    1. 각 단계에서 여러 개의 간선을 선택
    2. 각 단계에서는 포레스트에 있는 각 트리에 대해 하나의 간선을 선택
      • 이 간선은 오직 하나의 정점만 그 트리에 속한 최소 비용의 간선
    3. 선택된 간선을 구축중인 신장 트리에 추가
    4. 오직 하나의 트리만이 존재하거나 더 이상 선택할 간선이 없으면 종료
  • 과정 예시

profile
💪 🥩 🍺 ✈ 💻

1개의 댓글

comment-user-thumbnail
2020년 6월 7일

잘 보고가요

답글 달기