RSS Feed

최소 그래프

Problem 107

출제 일시 : 2013-03-03 14:58:38, ☕ 7

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

 

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

     A B C D E F G
A - 16 12 21 - - -
B 16 - - 17 20 - -
C 12 - - 28 - 31 -
D 21 17 28 - 18 19 23
E - 20 - 18 - - 11
F - - 31 19 - - 27
G - - - 23 11 27 -

 

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

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

 

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


로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.