78.20개의 공항을 보유하고 있는 국가가 허브 앤드 스포크(Hub and Spoke) 네트워크를 구축하려고 한다. 20개의 공항 중 4개를 허브로 선택하여 운영할 경우에 총 몇 개의 왕복노선이 필요한가?

① 16개

정답: X

허브가 아닌 공항 16곳을 허브에 하나씩 잇는 노선만 센 값이다 — 허브끼리 잇는 노선이 빠졌다.

② 18개

정답: X

스포크 16개에 허브 사이 노선 6개를 더해야 하므로 18개로는 모자란다.

③ 20개

정답: X

허브 4곳을 고리 모양으로 4개만 이으면 16 + 4 = 20개지만, 허브끼리는 모두 이어야 해서 6개가 든다.

④ 22개

정답: O

허브 4곳끼리 모두 잇는 노선 4 × 3 ÷ 2 = 6개 + 허브가 아닌 16곳을 허브 하나와 잇는 노선 16개 = 22개.

⑤ 24개

정답: X

허브 사이 6개와 스포크 16개를 더하면 22개라 24개는 노선을 더 센 값이다.