진흙도시 프로젝트

여러분이 전기, 가스, 수도 등을 새로운 거주지에 공급하는 것을 설계한다고 가정해봅시다. 모든 집의 전선 혹은 파이프는 공공기업(한전, KT, 가스공사 등)에 연결되어야 > 합니다. 각각의 집은 어떻게든 네트워크에 연결되어야 하지만 어떤 경로를 취할 것인가는 연결만 된다면 그다지 문제가 되지 않습니다.

네트워크 경로 길이가 최소가 되도록 설계하는 작업을 “최소생성나무”(minimal spanning tree)문제라고 합니다.

“최소생성나무”는 가스나 전력 네트워크에만 유용한 것이 아닙니다. 컴퓨터 네트워크, 전화 네트워크, 송유관, 항공운항 경로 문제를 해결하는데 도움이 됩니다. 하지만, > 여행의 최적 경로를 결정할 때는 비용이 얼마나 드는지, 여행이 얼마나 편안할지도 함께 고려해야 합니다. 단지 비용이 저렴하다는 이유로, 처음으로 여행가는 나라에 > 비행기를 장시간 타면서 시간을 낭비하려는 사람은 많지 않을 것입니다. 비행경로나 화물 운송경로를 최소화하는데 사용되는 진흙도시 알고리즘은 여행경로와 같은 네트워크 > 최적화하는 데에는 그다지 도움이 되지 않습니다.

최소생성나무 알고리즘은 그래프에 관한 다른 문제(예를 들어 “외판원 문제 [Travel Salesman Problem, TSP]”)를 해결할 때 단계중의 하나로서 유용합니다. 외판원 문제는 > 네트워크의 모든 점을 방문하는 최소 경로를 찾는 것입니다.

최소생성나무 문제를 해결하는 효과적인 알고리즘과 방법이 있습니다. 최적의 해결책을 주는 간단한 방법은 아무 연결도 없는 상태에서 시작해서, 앞에서 연결되지 않은 > 점들을 비용이나 크기가 커지는 순서대로 연결을 하는 것입니다. 1956년에 J.B. Kruskal이 발표하여 Kruskal 알고리즘이라고 합니다.

“외판원 문제” 등, 그래프에 관한 많은 문제에 관해서는 지금도 컴퓨터 과학자가 가장 최선의 가능한 해결책을 찾아내는데 충분히 빠른 방법을 찾으려고 노력을 경주하고 > 있습니다.

변형과 확장

도시에 집이 n개 있다면 얼마나 많은 도로 연결이 필요할까요?
최적의 해결책은 정확하게 n-1 개 연결을 갖는 것으로 밝혀졌다.
n-1개 연결은 n 개 집을 연결하는데 충분하다.
왜냐하면, 연결을 하나 더 추가하는 것은 집 사이에 불필요한 대체가능한 연결을 하나 더 만들기 때문이다.