平成24年度 秋期 ネットワークスペシャリスト試験 午前Ⅱ 問4

解説

この問題は最大流最小カット定理を用いて解きます。X 側を {X，A，B，C}，Y 側を {D，E，F，G，Y} に分けると，両者をまたぐ回線は A-D（1），B-D（2），B-E（3），C-F（4）の 4 本で，多重度の合計は 1＋2＋3＋4＝10 です。他のどの分割でもこれより小さい合計は作れないため，これが最小カットとなり，X-Y 間で同時に使用できる論理回線の最大数は 10 です。

選択肢ごとの解説

• ア誤り。代表的な経路だけをたどって数え，並行して使える別ルートの分を見落とした場合に得られる値です。
• イ誤り。カットに含める辺を 1 本分数え間違えた場合などに得られる値です。
• ウ正しい。{X，A，B，C} と {D，E，F，G，Y} の間をまたぐ回線の多重度の合計（1＋2＋3＋4）が最小カットであり，最大流に等しくなります。
• エ誤り。X 地点から直接出ている 3 本の回線の多重度をそのまま合計した値（4＋4＋3）であり，途中の枝が制約になることを考慮していません。