최소 신장 트리(Minimum spanning tree)

마을 열 곳을 전선으로 이어 모두 전기가 통하게 하려 합니다. 전선 값은 길이에 비례하고, 어느 두 마을 사이에든 전선을 놓을 수 있습니다. 가장 싸게 잇는 방법은 무엇일까요? 모두 이어지기만 하면 되니 순환은 낭비입니다. 순환이 있으면 그 위의 가장 긴 전선을 걷어 내도 여전히 이어져 있으니까요. 그래서 답은 언제나 모든 점을 잇는 트리, 곧 신장 트리입니다. 문제는 후보가 너무 많다는 것입니다. 점 10개 사이의 신장 트리⁠(spanning tree)⁠는 케일리 공식⁠(Cayley's formula)⁠ $n^{n-2}$에 따라 $10^8$개, 곧 1억 개입니다.

1956년 미국의 수학자 조지프 크러스컬이 내놓은 방법은 단순합니다. 모든 변을 짧은 것부터 정렬해 놓고 차례로 보면서, 이미 이어진 두 점을 다시 잇는 변(순환을 만드는 변)이면 버리고 아니면 받아들입니다. 매 순간 가장 좋아 보이는 것을 고르고 되돌아보지 않는 욕심쟁이 알고리즘⁠(greedy algorithm)⁠인데, 이 문제에서는 정확히 최적입니다.

방법: . 새 마을 점을 끌어 옮기면 트리가 바로 다시 계산됩니다.

고른 변의 길이 합은 입니다. A에서 나머지 모든 점으로 곧장 잇는 별 모양은 입니다.

왜 욕심이 통할까요? 점들을 아무렇게나 두 무리로 가르면, 두 무리를 잇는 변 가운데 가장 짧은 것은 반드시 어떤 최소 신장 트리에 들어 있습니다(절단 성질⁠, cut property⁠). 그 변이 빠진 최소 신장 트리가 있다고 합시다. 거기에 이 변을 더하면 순환이 하나 생기고, 그 순환은 두 무리 사이를 한 번 더 건너야 제자리로 돌아옵니다. 그렇게 다시 건너는 변을 빼고 이 변을 넣으면, 여전히 신장 트리이면서 더 짧거나 같습니다. 크러스컬이 받아들이는 변은 언제나 '그 변의 한쪽 끝 조각'과 나머지를 가르는 절단⁠(cut)⁠에서 가장 짧은 변입니다. 두 점이 이미 같은 조각인지는, 조각들을 동치류⁠(equivalence class)⁠로 보고 조각마다 대표 점 하나를 정해 두어 두 점의 대표가 같은지 비교하는 합집합-찾기⁠(union-find)⁠ 구조로 거의 즉시 알 수 있어서, 전체 시간은 변 m개를 정렬하는 $O(m \log m)$이 좌우합니다(점근 표기법⁠, asymptotic notation⁠).

1957년 벨 연구소의 로버트 프림이 발표한 방법(체코의 수학자 보이테흐 야르니크가 1930년에 먼저 찾았습니다)은 한 점에서 출발해, 지금 트리에서 밖으로 나가는 변 가운데 가장 짧은 것을 하나씩 붙여 나갑니다. 가장 짧은 변을 꺼내는 데 우선순위 큐⁠(priority queue)⁠를 씁니다. 변 길이가 모두 다르면 최소 신장 트리는 하나뿐이라, 순서는 달라도 결과는 같은 트리입니다. 길이가 같은 변이 있으면 최소 신장 트리가 여럿일 수 있지만, 길이 합은 모두 같습니다. 비슷해 보이는 다익스트라 알고리즘(에츠허르 데이크스트라)의 최단 경로⁠(shortest path)⁠ 트리는 출발점에서 각 점까지의 거리를 줄이는 것이라 결과가 다릅니다. 최소 신장 트리에서 두 점 사이의 길은 꽤 멀리 돌아갈 수 있습니다.

이어지는 곳. 이 문제는 1926년 체코의 수학자 오타카르 보루프카가 모라비아 지방의 전력망을 설계하며 처음 풀었다고 알려져 있고, 크러스컬(1956)과 프림(1957)의 방법이 뒤를 이었습니다. 평면 위의 점들에서는 보로노이 다이어그램⁠(Voronoi diagram)⁠이 변 후보를 크게 줄여 줍니다. 보로노이 칸이 서로 맞닿은 두 점끼리만 이으면 삼각형 그물이 생기는데, 이것을 들로네 삼각분할(러시아의 수학자 보리스 들로네의 이름)이라 하고, 최소 신장 트리의 변은 모두 이 안에 들어 있습니다. 최소 신장 트리에서 가장 긴 변 k−1개를 끊으면 점들이 k개 무리로 나뉩니다. 이것을 단일 연결 군집⁠(single-linkage clustering)⁠이라 하며, 가까운 이웃을 사슬처럼 따라 묶기 때문에 둥근 무리를 가정하는 k-평균 군집⁠(k-means clustering)⁠과 달리 길쭉한 무리도 잘 찾습니다. 두 점 사이를 '잇는 길 가운데 가장 긴 변이 가장 짧은 길의, 그 가장 긴 변의 길이'로 다시 재면, 그 값은 최소 신장 트리 위의 길에서 가장 긴 변의 길이와 같고 강한 삼각부등식⁠(triangle inequality)⁠ $d(a, c) \le \max(d(a, b), d(b, c))$를 만족하는 초거리⁠(ultrametric)⁠가 되어 단일 연결 군집의 나무 그림을 그대로 줍니다. 길을 이을 때 길이를 더하는 대신 최댓값을 취하는 풍부화된 범주⁠(enriched category)⁠가 바로 이 거리입니다.

모든 점을 한 번씩 들르고 돌아오는 가장 짧은 순회를 찾는 외판원 문제⁠(traveling salesman problem)⁠는 NP-난해⁠(NP-hard)⁠합니다. NP-완전⁠(NP-complete)⁠ 문제만큼 또는 그보다 어려워서, 빠른 풀이법이 알려져 있지 않다는 뜻입니다. 그래도 거리가 삼각 부등식 $d(a, c) \le d(a, b) + d(b, c)$, 곧 '둘러 가는 길이 곧장 가는 길보다 짧을 수는 없다'를 지키는 거리 함수⁠(metric)⁠라면 좋은 근사가 쉽습니다. 최소 신장 트리를 따라 한 바퀴 돌되 이미 들른 점은 건너뛰면 됩니다. 가장 짧은 순회에서 변 하나를 빼면 신장 트리가 되므로 최소 신장 트리는 그 순회보다 길지 않고, 트리를 한 바퀴 도는 길이는 트리 길이의 두 배이며, 삼각 부등식 때문에 건너뛰기는 길을 늘리지 않습니다. 그래서 이렇게 얻은 순회는 최적의 두 배를 넘지 않습니다. 이 그림에서는 유클리드 거리⁠(Euclidean distance)⁠를 썼습니다.