최소신장트리 (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가 증가히자 않으면서 안 끊어지게 연결해 주는 방식인가 보다.
↑ 추정의끝
안전하다 = 그 에지를 포함하는 경로를 존재하게 할 수 있다
댓글
댓글 쓰기