62.다음과 같은 네트워크에서 노드 S로부터 G까지 모든 노드들에 원유를 공급할 수 있는 가장 짧은 길이의 송유관 네트워크를 구축하고자 할 때, 송유관의 총 길이는 얼마인가? (단, 숫자는 두 노드 상의 거리이며, 단위는 km임)

① 18 km

정답: X

여덟 마디를 이으려면 일곱 구간이 필요하고 가장 짧게 골라도 20km라 18km는 나올 수 없다.

② 19 km

정답: X

가장 짧은 연결의 합이 20km라 19km로 모든 노드를 잇는 방법은 없다.

③ 20 km

정답: O

짧은 구간부터 고리가 생기지 않게 고른다: a-b 2, c-f 2, e-f 2 → S-a 3, a-d 3 → b-c 4(두 덩어리 연결), d-G 4(S-b 4는 고리라 뺀다) → 2 + 2 + 2 + 3 + 3 + 4 + 4 = 20km.

④ 21 km

정답: X

G를 d-G 4 대신 e-G 5로 이으면 21km가 된다 — 더 짧은 d-G 4를 써야 한다.

⑤ 22 km

정답: X

22km는 가장 짧은 연결 20km보다 길다 — 짧은 구간부터 고리 없이 골라야 한다.