ネットワークスペシャリスト 2012年 午前2 問04

ネットワークの最大同時論理回線数【午前2 解説】

要点まとめ

• 結論：X地点からY地点まで同時に使用可能な論理回線の最大数は10本です。
• 根拠：ネットワークの最大フロー問題として考え、各辺の容量（重み）を用いて最大流量を求めることで導出します。
• 差がつくポイント：複数経路の容量を正確に把握し、フローの増加経路を見逃さずに計算できるかが鍵です。

正解の理由

よくある誤解

• 単純にXからYへの辺の容量を足すだけで最大値を判断しがちですが、途中のノード間の容量制約を無視すると誤答になります。
• 経路の重複や容量の分配を考慮せずに計算すると、実際の最大フローを超える値を選んでしまいます。

解法ステップ

1. 問題を最大フロー問題として認識する。
2. 各辺の容量（重み）をフロー容量として設定する。
3. XからYへの複数経路を洗い出す。
4. フォード・ファルカーソン法などで増加経路を見つけ、フローを増やす。
5. 途中のノード間の容量制約を考慮しながら、フローの合計を計算する。
6. 最大フロー値が10であることを確認し、選択肢から正解を選ぶ。

選択肢別の誤答解説

• ア: 8
  Xからの容量合計は11あるため、8は過小評価。途中経路の容量制約を考慮しても10までは可能。
• イ: 9
  9も途中経路の容量制約を考慮すると達成可能だが、最大値ではない。
• ウ: 10
  正解。最大フロー計算の結果、10が最大値となる。
• エ: 11
  Xからの容量合計は11だが、途中の経路制約により11は不可能。過大評価。

補足コラム

FAQ