Biconnected Components/최소 비용 신장트리

단절점(articulation point)

 그래프 G의 vertex, v로서 v와 v에 부속된 edge들을 삭제할 경우, G가 두 개 이상의 connected component들로 분할되는 vertex들

 

이중 결합 그래프(biconnected graph)

 단절점이 없는 connected graph

 

이중 결합 부분 그래프(biconnected component)

 

(a)는 connected graph인데,

빨간색으로 그어놓은 vertex를 삭제하게 되면 그래프가 끊어지게 된다.

이 빨간 vertex들이 단절점(articulation point)인 것이다.

 

(b)는 biconnected components들이다.

단절점이 없어 무엇 하나를 끊어도 모두 연결되어있다는 뜻이다.

vertex가 두개 뿐인 것도 biconnected component이다.

하나를 끊으면 나머지 하나는 혼자서 연결되어있다고 생각하면 되겠다.

 

---

최소 비용 신장트리

가중치가 부여된 무방향 그래프에서 가장 비용이 적은 신장트리(spanning tree)

 

최소비용신장트리 알고리즘

1. 그래프 내에 존재하는 edge들만 사용
2. n-1개의 edge만 사용
3. Cycle을 형성하는 edge는 사용 불가

최소 비용 신장트리를 구하기 위한 알고리즘

• Kruskal
• Prim
• Sollin

---

Kruskal

Edge들을 비용의 오름차순으로 정렬한 후(싼 순으로 정렬), 가장 비용이 적은 edge부터 선택.

선택된 edge는 기존에 선택된 edge들과 사이클을 형성하지 않을 경우에만 그래프에 포함시킨다.

 

정렬 해놓고 사용하기 vs min heap 이용하기

사이클 판별은 union-find 사용

 

알고리즘의 시간복잡도는 O(e log e)가 되는데,

간선 e는 최대 n(n-1)/2이고 최소 n-1이므로

최악의 경우는 O(n^2 log n^2)이 되고,

최적의 경우는 O(n log n)이 된다.

 

---

Prim

시작 vertex가 있다.

이 vertex와 연결된 edge중 가장 저렴한 것을 선택하고 트리에 포함시킨다.

이후, 포함되어있는 vertex와 연결된 것 중 저렴한 것을 찾아 포함시킨다(반복)

 

시간복잡도는 O(n^2)

 

크루스칼과 비교하면, 

엣지가 많은 경우는 크루스칼 알고리즘의 시간복잡도가 O(n^2logn^2)에 달하므로 프림이 유리하다.

 

---

Sollin

각 단계별로, 모든 vertex에서 가장 저렴한 edge를 동시에 선택하고, 선택된 엣지들을 트리에 포함시킴.