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

図で示されたネットワークにおいて、X地点からY地点までの最大の通信量（多重度）を求める問題です。このような問題は最大フロー最小カットの定理を用いて解くことができます。ネットワークをXを含む側とYを含む側に分断する「カット」をいくつか考え、その境界をまたぐ回線の多重度の合計が最も小さくなる箇所（ボトルネック＝最小カット）を見つけることで、通信可能な最大数（最大流量）を導出できます。

いくつかカットの候補を計算してみます。

• Xの直後で分断した場合（{X} と {A, B, C, D, E, F, G, Y} の間）:
  境界をまたぐ回線は X-A (4)、X-B (4)、X-C (3) で、合計は $4 + 4 + 3 = 11$ です。
• Yの直前で分断した場合（{X, A, B, C, D, E, F, G} と {Y} の間）:
  境界をまたぐ回線は D-Y (3)、E-Y (3)、G-Y (6) で、合計は $3 + 3 + 6 = 12$ です。
• {X, A, B, C} と {D, E, F, G, Y} の間で分断した場合:
  境界をまたぐ回線は以下の4つです。
  • A-D （多重度: 1）
  • B-D （多重度: 2）
  • B-E （多重度: 3）
  • C-F （多重度: 4）
    これらの合計は $1 + 2 + 3 + 4 = 10$ となります。

他のどの分け方をしても境界をまたぐ回線の合計は10より小さくならないため、ネットワーク全体のボトルネック（最小カット）は 10 となります。
したがって、X地点からY地点まで同時に使用できる論理回線の最大数は 10 となり、正解は ウ です。

各選択肢の解説

• ア (8): XからYへは同時に10の論理回線を使用できる経路が存在するため、最大数ではありません。
• イ (9): アと同様に、同時に10の論理回線を使用できる経路が存在するため、最大数ではありません。
• ウ (10): 正解です。
• エ (11): Xからの出力合計（$4 + 4 + 3 = 11$）に等しいですが、途中の経路（A-D, B-D, B-E, C-F を結ぶ境界）が最大でも10までしか通せないため、11の回線を同時に使用することはできません。