1. Spanning Tree

01. 정의

  • [한 줄] 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 (트리의 성립 조건)
  • 원래 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프
  • 이때 스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야 한다.
    • 트리 형태여야 한다는 말은 선택된 간선들이 사이클을 이루지 않는다는 뜻이다.

02. 특징 (정리)

  • 모든 정점들이 연결되어 있어야 한다.
  • 사이클을 포함해서는 안된다.
  • 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다.
  • 하나의 그래프에는 많은 스패닝 트리가 존재할 수 있다.

03. 예시

올바른 스패닝 트리, 틀린 스패닝 트리

  • (b)는 올바른 스패닝 트리이다.
  • (c)는 스패닝 트리가 아니다. 사이클이 있고, 그래프가 하나로 연결되지 않았다.

04. 사용 사례

스패닝 트리 사용 사례

  • 통신 네트워크 구축에 많이 사용된다.
  • 회사 내의 모든 전화기를 가장 적은 수의 케이블을 사용하여 연결하는 경우

2. Minimum Spanning Tree

01. 정의

  • 최소 비용 신장 트리
  • 가중치 그래프의 스패닝 트리 중 가중치의 합이 가장 작은 트리
  • 추가 설명
    • 각 링크의 구축 비용은 똑같지 않다. 따라서 단순히 가장 적은 링크만을 사용한다고 해서 최소 비용이 얻어지는 것은 아니다.
    • 따라서 각 링크, 즉 간선에 비용을 붙여서 링크의 구축 비용까지 고려하여 최소 비용의 신장 트리를 선택할 필요가 있다.

02. 특징

  • 스패닝 트리 중 가중치의 합이 가장 작은 트리이므로, 스패닝 트리의 특징에 추가로 가중치의 합이 가장 작아야 한다.

03. 사용 사례

  • 통신망, 도로망, 유통망 (간선에 가중치가 부여된 네트워크로 표현 가능한 것들)을 가장 적은 비용으로 구축하려는 경우
  • 도로 건설 : 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제
  • 전기 회로 : 단자들을 모두 연결하면서 전선의 길이가 가장 최소가 되도록 하는 문제
  • 통신 : 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제
  • 배관 : 파이프를 모두 연결하면서 파이프의 총 길이가 최소가 되도록 연결하는 문제

04. MST를 구하는 두 가지 유명한 알고리즘

  • 크루스칼(Kruskal)의 최소 스패닝 트리 알고리즘
  • 프림(Prim)의 최소 스패닝 트리 알고리즘

3. 참고