57.다음 네트워크에서 7지점의 물류 창고를 모두 연결하는 도로를 개설하려 한다. 최소로 필요한 도로 연장은?

① 120 km

정답: X

일곱 지점을 이으려면 여섯 구간이 필요하고 가장 짧게 골라도 130km라 120km는 나오지 않는다.

② 130 km

정답: O

짧은 구간부터 고리 없이 고른다: 3-5 10 → 1-3 20, 4-7 20, 6-7 20 → 1-2 30, 두 덩어리를 잇는 30km 구간 하나(3-6) → 10 + 20 + 20 + 20 + 30 + 30 = 130km.

③ 140 km

정답: X

2를 1-2 30 대신 2-4 40으로 이으면 140km가 된다 — 더 짧은 1-2를 써야 한다.

④ 150 km

정답: X

150km는 최소 연결 130km보다 20km 길어 가장 짧은 도로망이 아니다.

⑤ 160 km

정답: X

160km는 짧은 구간부터 고르는 규칙을 따르지 않은 연결이다 — 최소는 130km다.