다음 그림과 같이 A, B, C, D, E의 5개 도시에 석유제품을 공… | [물류관리사] 12년 1회차 기출문제 상세 페이지

모든 도시를 잇는 최소신장나무(MST)를 구하면 필요한 파이프라인 길이는 21km다.
그림의 구간과 거리는 A-B 10, A-C 5, B-C 7, B-D 4, B-E 6, C-E 9, D-E 5(단위 km)다. 파이프라인은 5개 도시를 모두 연결하기만 하면 되므로 순환을 만들지 않는 4개 구간만 골라 합을 최소화한다.
짧은 구간부터 채택하면 B-D 4 → A-C 5 → D-E 5가 들어가고, 그다음 B-E 6은 B-D-E와 순환이 되어 버려진다.
아직 떨어져 있는 A·C 묶음을 잇는 가장 짧은 구간 B-C 7을 더하면 5개 도시가 모두 연결된다.
$4+5+5+7=21\,\mathrm{km}$
노드가 5개이므로 필요한 구간 수는 반드시 4개이며, 이보다 짧은 조합은 존재하지 않으므로 최소 소요 길이는 21km다.