平成22年度秋期 ネットワークスペシャリスト 午前Ⅱ 問2

辺容量と流量の対応を確認する視点

ネットワーク図では、各辺に示された制約と、始点から終点へ進む流れの関係を同じ基準で見比べ、局所的な数字だけで判断せず、全体のつながりを一つの視点から整理します。

この問題で問われていること

確認する観点は、図中の各辺が受け持つ役割と、流れが複数の経路を通るときに生じる関係です。辺ごとに独立して見るのではなく、接続点の前後で整合しているかを丁寧に追います。

視点

辺ごとの制約と流れを切り分けて捉え、分岐や合流を含む経路全体の関係を順番に確認します。

確認ポイント

• 各辺の制約と流れを同じ単位・向きで読み取れているか
• 分岐・合流の接続点で、前後の関係を一貫して追えているか
• 一つの経路だけでなく、図全体の接続と制約の影響を見ているか

正解

ウ

解説

この問題は、XからYへ流せる論理回線数を最大流として求める。容量10のカットによる上限と、実際に10回線を流せる具体的な辺別割当てを併せて確認する。

上限の根拠

X側の集合をX・A・B・Cとすると、外へ出る辺はA-Dの1、B-Dの2、B-Eの3、C-Fの4であり、合計は1＋2＋3＋4＝10論理回線です。このカットを越えられる流量は10を超えない。

達成可能性の確認

実際に、X-Aを3、X-Bを4、X-Cを3、A-Bを2、B-Cを1、A-Dを1、B-Dを2、B-Eを3、C-Fを4とする。右側ではD-Yを3、F-Eを2、F-Gを2、E-Yを3、E-Gを2、G-Yを4とすれば、各地点で流量が保存され、各辺の容量以内で合計10論理回線をYへ送れる。

選択肢ア

これは不正解だよ。8論理回線は、ネットワーク上で実現できる流量の一例としては小さすぎる。例えば、辺別に容量内の流量を割り当てて合計10論理回線をYへ送れるため、8は最大値ではない。8になる特別な計算過程は、図の容量条件からは導けない。

選択肢イ

これは不正解だよ。9論理回線も、実現可能な流量より1論理回線少ない値である。図の辺容量を守りながら合計10論理回線を流せる具体的な割当てがあるため、9は最大値ではない。9を導く条件変更は設問に示されていない。

選択肢ウ（正解）

これは正解だよ。A-D、B-D、B-E、C-Fを境界とすると容量は1＋2＋3＋4＝10論理回線で、これが上限になる。一方、各辺の容量以内でX-Aを3、X-Bを4、X-Cを3などと割り当て、10論理回線をYまで実際に流せるため、最大値は10である。

選択肢エ

これは不正解だよ。11論理回線は、X側のX・A・B・Cと右側を分ける境界の容量1＋2＋3＋4＝10論理回線を超えている。この境界を通過せずにYへ進むことはできないため、11は図の容量条件では実現できない。

学習のポイント

最大流では、上限の証明と、その上限を実現する流量割当ての両方が必要です。