다음 무향(undirected) 그래프는 총 7개의 꼭지점(vertex)과 총 12개의 선(egdes)으로 이루어져 있습니다. 선들의 거리(weight)의 합은 243입니다.

이 그래프는 다음처럼 표로 나타낼 수도 있습니다.

이 그래프는 선 몇 개를 제거하고도 모든 꼭지점이 연결되도록 최적화할 수 있습니다. 아래와 같이 하면 거리의 합이 93으로, 원래 그래프보다 거리가 150이나 더 작은 새로운 그래프를 만들 수 있습니다.

6K짜리 텍스트 파일  network.txt에는 40개의 꼭지점을 가진 그래프 정보가 2번째 그림과 같은 표 형식으로 정리되어 있습니다. 모든 꼭지점이 연결된 채로 거리의 합을 최적화한 그래프를 찾고, 원 그래프와의 거리 차이를 구하세요.

(역자 주 : 전산학을 전공하신 분들에게는 원어가 더 친숙하게 다가올 수 있다고 판단되어 영문을 병기하기로 결정하였습니다. 풀이에 참고바랍니다)