図のネットワークで、数字は二つの地点間で同時に使用できる論理回線の多重度を示している。X地点からY地点までには同時に最大幾つの論理回線を使用することができるか。

同時使用回線数の上限は最大フロー（最小カット）で決まる

ネットワークスペシャリスト試験／2016年度 秋期 午前II 問3／ネットワーク設計 / グラフ理論

X, A, B, C, D, E, F, G, Yの各点をノードとするネットワーク図。エッジと多重度: X-A=4, X-B=4, X-C=3, A-B=2, A-D=1, B-D=2, B-E=3, B-C=1, C-F=4, D-E=2, D-Y=3, E-G=4, E-Y=3, F-G=3, F-E=2, G-Y=6。
X, A, B, C, D, E, F, G, Yの各点をノードとするネットワーク図。エッジと多重度: X-A=4, X-B=4, X-C=3, A-B=2, A-D=1, B-D=2, B-E=3, B-C=1, C-F=4, D-E=2, D-Y=3, E-G=4, E-Y=3, F-G=3, F-E=2, G-Y=6。

選択肢

正解と解説

正解：ウ 10

同時に使える論理回線の最大数は、X地点を始点、Y地点を終点とする最大フロー（最小カット）の値である。各リンクの多重度を容量とみなし、経路を重複させないように流量を積み上げていくと、Y地点へ流し込める合計は10となる。Y地点に入るリンクの容量合計（D-Y=3、E-Y=3、G-Y=6）は12あるが、途中のリンク容量が制約となって10に抑えられる。

選択肢ごとの解説

出典：平成28年度 秋期 ネットワークスペシャリスト試験 午前II 問3（IPA）

この問題は2回出題されています

最終更新：2026-08-25／解説・選択肢ごとの解説は資格暗記が独自に作成しています。問題文と選択肢の出典は上記のとおりです。