令和3年度 春期 ネットワークスペシャリスト試験 午前Ⅱ 問4

解説

この問題は，図のネットワークにおける X-Y 間の最大フロー（最大多重度）を最小カットによって求める問題です。X が出せる回線容量の合計は X-A(4)＋X-B(4)＋X-C(3)＝11 ですが，ネットワークを｛X，A，B｝と残り｛C，D，E，F，G，Y｝に分けるカットを考えると，その間をまたぐ回線は X-C(3)，A-D(1)，B-D(2)，B-E(3)，B-C(1) の 5 本で，合計 3＋1＋2＋3＋1＝10 となり，これが全体のボトルネック（最小カット）になります。したがって，X-Y 間で同時に使用できる論理回線の最大値は 10 です。

選択肢ごとの解説

• ア誤り。実際にはこれより 2 多い 10 まで多重化でき，8 は最大値ではありません。
• イ誤り。実際にはこれより 1 多い 10 まで多重化でき，9 は最大値ではありません。
• ウ正しい。｛X，A，B｝と残りのノードを分けるカットの容量が 10 であり，これが最小カット（＝最大フロー）です。
• エ誤り。X から出る回線容量の単純合計は 4＋4＋3＝11 ですが，｛X，A，B｝と残りを分けるカットの容量が 10 しかないため，11 の多重化を同時に実現することはできません。