가중 그래프
Minimum Spanning Tree (MST)로 들어가기 전에, 가중 그래프가 무엇인지 알아보겠습니다:
- 가중 그래프는 각 간선에 가중치(또는 비용)를 연관시킨 그래프 모델입니다. 즉, 각 간선 e에는 w(e)로 표기되는 수치 레이블이 연관되어 있습니다.
가중 그래프의 세 가지 일반적인 문제를 해결하기 위한 알고리즘을 살펴보겠습니다:
- MST
- 최단 경로
- 네트워크 흐름
최소 신장 트리
- MST의 입력: 정점(또는 노드) 𝑉와 간선 𝐸로 구성되며 간선 가중치를 가지는 가중 연결 그래프 𝐺 = (𝑉, 𝐸)입니다.
- 출력: 𝐺의 최소 신장 트리(MST) 𝑇 = (𝑉, 𝐸𝑇)입니다. 즉, 𝑇는 𝐺의 연결 신장 부분 그래프(𝐸𝑇 ⊆ 𝐸)로서 𝑇가 비순환적이고 𝑇의 총 가중치가 최소화된 것입니다.
MST의 실제 응용 사례는 다음과 같습니다:
-
클러스터 분석.
-
최대 병목 경로.
-
실시간 얼굴 인증.
-
오류 정정을 위한 LDPC 코드.
-
Rényi 엔트로피를 이용한 이미지 정합.
-
위성 및 항공 이미지에서 도로 네트워크 찾기.
-
단백질의 아미노산 시퀀싱에서 데이터 저장량 줄이기.
-
난류 유체 흐름에서 입자 상호작용의 지역성 모델링.
-
네트워크의 순환을 방지하기 위한 이더넷 브리징 자동 구성 프로토콜.
-
NP-난해 문제(예: TSP, Steiner tree)에 대한 근사 알고리즘.
-
네트워크 설계(통신, 전기, 수력, 컴퓨터, 도로).
그래프 G에서 MST를 어떻게 찾을까요?
음, 두 가지 방법이 있습니다:
- 브루트 포스로 가능한 모든 신장 트리를 만들어 가장 가벼운 W(G)를 찾을 수 있지만, 브루트 포스의 빅 오가 매우 커질 수 있어 이 방법은 실용적이지 않습니다.
- 대신 Prim 또는 Kruskal 알고리즘과 같은 그리디 알고리즘을 사용할 수 있습니다.
Prim 알고리즘:
- 선택한 단일 정점으로 트리를 초기화합니다.
- 아직 트리에 없는 가장 가벼운 인접 간선을 찾아 트리에 연결하여 트리를 키우고, 모든 정점이 트리에 포함될 때까지 반복합니다.
Kruskal 알고리즘:
- 모든 노드로 구성된 포레스트를 초기화합니다.
- (선택되지 않은) 최소 가중치 간선을 선택하고, 그것이 포레스트의 서로 다른 두 트리를 연결하면 선택하고, 그렇지 않으면 버립니다; 반복합니다.
(계속…)