최소신장트리

최소신장트리(MST)

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

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

정점 = 도시 

위의 그림에서 d와 f를 연결하는 도로건설하려면 비용이 14가 든다고 볼수있다.

예산은 항상 부족하기 마련이므로 비용을 최소로 들여서..

이그래프중 edge 중 일부의 edge만 선택을해서

내가 선택한 edge에 의해서 이 그래프의 모든 node가 연결이 되면서

비용이 최소가 되는..

무방향 가중치 그래프..(가중치는 다 양수다)

 

 위 그림의 굵은 선이 MST

- MST는 유일하지 않다!

 

왜 트리라고 부르나?

-싸이클이 없는 연결된 무방향 그래프를 트리라고 부른다.

-MST 문제의 답은 항상 트리가 됨 . 왜?

위의 그래프는 서로 연결됨..

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

연결: 직접 edge로 연결되어있지않더라도 edge를 거쳐서 갈 수 있따.

인접 : 직접 edge로 연결되있다.

-싸이클이 없다.

 

Generic MST 알고리즘

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

-에지 (u, v)는 A에 대해서 안전하다(safe)고 합니다.

Generic MST 알고리즘

-처음에는 A = 0.

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

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

 

GENERIC-MST(G, w)
    A <- zero
    while A does not form a spanning tree
        do find an edge(u, v) that is safe for A
            A <- A U {(u, v)}
    return 

 

안전한 에지 찾기

-그래프의 정점들을 두 개의 집합 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)고 말합니다.

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

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