[Discrete Mathematics] 신장 트리(spanning tree) 및 최소 신장 트리(minimal spanning tree)

---

신장 트리

 

$ T $ 가 그래프 $ G $ 의 모든 정점을 포함하는 부분 그래프이면서 트리라면 $ T $ 를 $ G $ 의 신장 트리라 한다.

일반적으로 그래프는 여러 개의 신장 트리를 가진다.

예를 들어 위와 같은 그래프에는 아래와 같은 신장 트리가 있을 수 있다. 주황색 선으로 표시된 것이 신장 트리이다.

그래프 $ G$ 가 신장 트리 $ T $ 를 가지고 있다는 것과 $ G $ 가 연결되어 있다는 것은 동치이다. 증명은 다음과 같다.

그래프 $ G $ 가 신장 트리 $ T $ 를 가진다 가정하고, $ a, b \in V_G $ 를 가정하자. 그렇다면 $ a, b \in V_T $ 이다. $ T $ 가 트리이므로 $ a $ 에서 $ b $ 로의 경로 $ P $ 가 존재하며 따라서 연결되어 있다.

반대로 $ G $ 가 연결되어 있다고 가정할 때 $ G $ 가 사이클을 포함한다면 사이클에서 간선을 제거함으로써 비순환 그래프로 만들 수 있다. 만약 $ G $ 가 사이클을 포함하지 않는다면 비순환 그래프이다. 그런데 연결된 비순환 그래프는 트리이다. 즉 $ G $ 가 연결되어 있다면 $ G $ 는 모든 정점을 가지는 그래프 $ T $ 를 부분 그래프로 가지고, 이 부분 그래프는 신장 트리이다.

 

---

최소 신장 트리

 

$ G $ 가 가중치 그래프라 할 때 $ G $ 의 최소 신장 트리는 최소 가중치를 갖는 $ G $ 의 신장 트리이다.

예를 들어 위와 같은 가중치 그래프가 있다고 할 때 최소 신장 트리는 아래와 같다.

 

---

프림 알고리즘 (Prim's Algorithm)

 

가중치가 있는 무방향 그래프에서 최소 신장 트리를 구하는 그리디 알고리즘이다. 하나의 정점을 가지고 시작하여 최소 신장 트리가 구해질 때까지 간선들을 반복적으로 추가하며 트리를 구축한다. 이때 각 반복에서 사이클을 형성하지 않는 최소 가중치의 간선들을 추가한다.

입력: $ w $ (간선의 가중치로 $ w[i][j] $ 는 간선 $ (i, j) $ 의 가중치, 만약 $ (i, j) $ 가 간선이 아니라면 $ w[i][j] = \infty $), $ n $ (정점의 수), $ s $ (시작 정점)
출력: $ E $ (최소 신장 트리의 간선 집합)

prim(w, n, s) {
    for i = 1 to n {
        v[i] = 0 // v[i] = 1 은 정점 i 가 mst 에 추가되었음을 의미
    }
    v[s] = 1
    E = EMPTYSET
    for i = 1 to n - 1 {
        min = INFINITY
        for j = 1 to n {
            if (v[j] == 1) {
                for k = 1 to n {
                    if (v[k] == 0 and w[j][k] < min) {
                        add_vertex = k
                        e = (j, k)
                        min = w[j][k]
                    }
                }
            }
        }
        v[add_vertex] = 1
        E = E + e
    }
    return E
}