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

同時使用可能な回線数は最小カットの容量で決まる

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

地点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-C:1, B-E:3(B-Eを通る線), D-E:2, D-Y:3, C-F:4, F-G:3, F-E:2(FからEへの斜め線), E-G:4, E-Y:3, G-Y:6。X地点から複数経路を通りY地点まで到達できる構成で、最大フロー問題として最大論理回線数を求める。

選択肢

ア8
イ9
ウ10
エ11

正解と解説

正解：ウ 10

この種の問題は最大フロー問題であり、最大フロー最小カット定理を使って解く。X側とY側にノードを分ける切り口（カット）をいろいろ試し、その切り口をまたぐ辺の容量の合計が最小になる値が、同時に使用できる論理回線の最大数と一致する。X直結の3本の合計は11だが、途中の中継区間の容量がボトルネックとなり、最小カットは10になる。

選択肢ごとの解説

ア8では流しきれず、これより多くの回線を同時に確保できる経路の組合せが存在する。
イ9でも同様に上限に達しておらず、最小カットの値には届かない。
ウ正しい。最小カットの容量が10であり、同時に使える論理回線は最大10本である。
エ11はX直結の辺の合計値だが、その先の区間で容量が不足するため実際には流せない。

出典：令和3年度春期ネットワークスペシャリスト試験午前II 問4（IPA）

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

2016年度秋期午前II 問3この問題の代表ページ
2021年度春期午前II 問4（このページ）

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