平成22年度 秋期 ネットワークスペシャリスト試験 午前Ⅱ 問2
テクノロジ／ネットワーク図のネットワークで，数字は二つの地点間で同時に使用できる論理回線の多重度を示している。X 地点から Y 地点までには同時に最大幾つの論理回線を使用することができるか。
出典：平成22年度 秋期 ネットワークスペシャリスト試験 午前Ⅱ 問2
- ア8
- イ9
- ウ10
- エ11
正解：ウ
解説
図の各リンクの多重度をボトルネックとして，X から Y への最大フロー（最大多重度）を求める問題です。X から出る経路の合計容量は 4＋4＋3＝11 ですが，Y へ流入できる容量は D→Y が 3，E→Y が 3，G→Y が 6 の合計 12 まで許容されます。実際に各枝の容量制約を満たすように経路を割り当てると，最大で 10 の論理回線を同時に流すことができます。
選択肢ごとの解説
- ア誤り。経路の割当てを最適化しないまま一部の枝だけで計算すると，本来流せる量より少なく見積もってしまいます。
- イ誤り。B を経由する経路の一部を数え漏らすと，最大値より 1 少ない値になります。
- ウ正しい。各枝の容量制約の下で経路を適切に割り当てると，X-Y 間で同時に最大 10 の論理回線を使用できます。
- エ誤り。実際には存在しない余剰の容量まで加算すると，最大値を超えた値になってしまいます。