개발 공부 - [그래프 알고리즘] 순회 - 최소비용신장트리(minimum spanning tree) - 1

 최소신장트리 (Minimum Spanning Tree)

최소 비용 신장 트리 (MST)

입력 : n개의 도시, 도시와 도시를 연결하는 도로 비용

문제 : 최소의 비용으로 모든 도시들이 서로 연결되게 한다.

무방향 가중치 그래프 중 일부 에지만 선택하여 선택한 에지 기반으로 모든 노드들이 선택되게 한다.

선택된 에지가 다를 수 있어서, 해가 유일하지는 않다.

(최소 경로가 여러 개 일 수 있음)

무방향 가중치 그래프로 G=(V,E)

각 에지 (u,v)∈E 에 대해서 가중치 w(u,v) 양수

이게 왜 트리라고 부르냐?

싸이클이 없는 연결된 무방향 그래프가 트리이긴 하다

MST 문제의 답이 항상 트리가 되는 이유는

노드 n개인 트리는 항상 n-1개의 에지를 가져서...

연결이 되어 있긴 함... -.-)

임의의 놈을 루트로 지정을 하고 인접한 노드를 자식으로 그려서 트리처럼 볼 수 있긴 함...

Generic MST 알고리즘

어떤 MST의 부분집합 A에 대해서 Au{(u,v)} 도 역시 어떤 MST의 부분 집합이 될 경우

에지 (u,v)는 A에 대해서도 안전하다(safe)고 한다.

Generic MST 알고리즘:

1. 처음에는 A=Φ 이다.

2. 집합 A에 대해서 안전한 에지를 하나 찾은 후 이것을 A에 더한다.

3. 에지의 개수가 n-1개가 될 때까지 2번을 반복한다.

= MST가 유일하지 않기 때문에, safe 요소를 검토해야 하는 건가 보다.

에지를 추가해도, MST 부분 집합이 될 경우에는 안전하다고 하나 보다.

안전한 에지 찾는 법은

그래프의 정점들을 두 개의 집합 S와 V-S로 분할한 것을 컷(cut)

(S,V-S)라고 부른다.

에지(u,v) 대해서 u∈S이고, v∈V-S일 때 에지(u,v)는 컷(S,V-S)를 cross 한다고 말한다.

에지들의 부분집합 A에 속한 어떤 에지도, 컷 (S,V-S)를 cross하지 않을 떄 컷(S, V-S)는

A를 존중한다(respect)라고 말한다.

= 공집합이 없는, 아무것도 건너가는 에지가 없을 떄 respect 한다고 한다.

컷 : 노드들을 두 그룹으로 분할한 것

크로스 : 다른 쪽에서 다른 쪽으로 건너가는 애

존중(리스펙트) : 에지 집합 A가 속한 어떤 에지도, cut을 cross 하지 않은 것 (겹치는게 없을 때)

정리

A가 어떤 MST의 부분집합이고, (S,V-S)는 A를 존중하는 컷이라고 하자,

이 컷을 cross하는 에지들 중 가장 가중치가 작은 에지 (u,v)는 A에 대해서 안전하다.

A를 존중하는 컷이긴 한데, A랑 (S,V-S)를 연결하는 적어도 한번의 경로를 e라고 하면,

가장 가중치가 작은 애를 고르면 얘는 A에 대해서 안전하단 얘긴가 보다 (복잡!)

그러면 가중치가 작으면서 최소 경로인 MST를 만들 수 있단 얘긴가 보다

아! 다른 에지를 대신하더라도 끊어지지 않게 할 수 있단 얘긴가 보다 -.-);;

Weight가 증가히자 않으면서 안 끊어지게 연결해 주는 방식인가 보다.

↑ 추정의끝

안전하다 = 그 에지를 포함하는 경로를 존재하게 할 수 있다