가중 그래프

Minimum Spanning Tree (MST)로 들어가기 전에, 가중 그래프가 무엇인지 알아보겠습니다:

  • 가중 그래프는 각 간선에 가중치(또는 비용)를 연관시킨 그래프 모델입니다. 즉, 각 간선 e에는 w(e)로 표기되는 수치 레이블이 연관되어 있습니다.

가중 그래프의 세 가지 일반적인 문제를 해결하기 위한 알고리즘을 살펴보겠습니다:

  1. MST
  2. 최단 경로
  3. 네트워크 흐름

최소 신장 트리

  • MST의 입력: 정점(또는 노드) 𝑉와 간선 𝐸로 구성되며 간선 가중치를 가지는 가중 연결 그래프 𝐺 = (𝑉, 𝐸)입니다.
  • 출력: 𝐺의 최소 신장 트리(MST) 𝑇 = (𝑉, 𝐸𝑇)입니다. 즉, 𝑇는 𝐺의 연결 신장 부분 그래프(𝐸𝑇 ⊆ 𝐸)로서 𝑇가 비순환적이고 𝑇의 총 가중치가 최소화된 것입니다.

MST의 실제 응용 사례는 다음과 같습니다:

  1. 클러스터 분석.

  2. 최대 병목 경로.

  3. 실시간 얼굴 인증.

  4. 오류 정정을 위한 LDPC 코드.

  5. Rényi 엔트로피를 이용한 이미지 정합.

  6. 위성 및 항공 이미지에서 도로 네트워크 찾기.

  7. 단백질의 아미노산 시퀀싱에서 데이터 저장량 줄이기.

  8. 난류 유체 흐름에서 입자 상호작용의 지역성 모델링.

  9. 네트워크의 순환을 방지하기 위한 이더넷 브리징 자동 구성 프로토콜.

  10. NP-난해 문제(예: TSP, Steiner tree)에 대한 근사 알고리즘.

  11. 네트워크 설계(통신, 전기, 수력, 컴퓨터, 도로).

    추가 자료: http://www.ics.uci.edu/~eppstein/gina/mst.html

그래프 G에서 MST를 어떻게 찾을까요?

음, 두 가지 방법이 있습니다:

  1. 브루트 포스로 가능한 모든 신장 트리를 만들어 가장 가벼운 W(G)를 찾을 수 있지만, 브루트 포스의 빅 오가 매우 커질 수 있어 이 방법은 실용적이지 않습니다.
  2. 대신 Prim 또는 Kruskal 알고리즘과 같은 그리디 알고리즘을 사용할 수 있습니다.

Prim 알고리즘:

  • 선택한 단일 정점으로 트리를 초기화합니다.
  • 아직 트리에 없는 가장 가벼운 인접 간선을 찾아 트리에 연결하여 트리를 키우고, 모든 정점이 트리에 포함될 때까지 반복합니다.

Kruskal 알고리즘:

  • 모든 노드로 구성된 포레스트를 초기화합니다.
  • (선택되지 않은) 최소 가중치 간선을 선택하고, 그것이 포레스트의 서로 다른 두 트리를 연결하면 선택하고, 그렇지 않으면 버립니다; 반복합니다.

(계속…)