ネットワークスペシャリスト 2021年 午前2 問04

最大流問題の計算【午前2解説】

正解の理由

解法ステップ

1. ネットワークを流量ネットワークと見なし、XからYへ流す。各辺の容量は最大流量の上限。
2. 増加パス（X→…→Y）の一つひとつにフローを割り当て、各辺で容量を超えないようにする。代表的な増加パスと送る流量は次の通り。
   • X → A → D → Y : 1
   • X → A → B → E → Y : 2
   • X → B → E → Y : 1
   • X → B → D → Y : 2
   • X → C → F → G → Y : 3
   • X → B → C → F → E → G → Y : 1 合計 $1+2+1+2+3+1=10$。
3. 各辺の使用状況が容量を超えていないことを確認（例えば X–B は 1+2+1 = 4 で容量4に一致、C–F は 3+1 = 4 で容量4に一致など）。
4. 最小カットを示して上限を示す。S = {X, A, B, C} とすると S→T に出る辺は A–D(1)、B–D(2)、B–E(3)、C–F(4) で合計 $1+2+3+4=10$。したがって最大流は10で確定。

選択肢別の誤答解説

• ア（8）
  多くの場合、上流側の直接的な経路だけを数えたり、C側の容量3を見落としたりして総和を過小評価した結果です。実際は複数経路を分散して使えるため8より多く流せます。
• イ（9）
  1本分の増加パスを見落としているケースです。上で示した最後の経路（X→B→C→F→E→G→Y）を見つけられず、合計を9で止めてしまう典型的ミスがあります。残っている辺（例：C–F の残容量や E–G の未使用容量）をチェックすると増やせることが分かります。
• エ（11）
  一部の受験者は同じノード間の複数の経路を重複して足したり、逆向きの残余辺を誤って正方向の余剰容量として加えたりして過大評価します。最小カットの和で上限を取れば $=10$ であり、11は不可能です。

よくある誤解

• 増加パスを見つけたらその順序でしか流せないと考えること。順序によって中間の残余が異なるが、最終的に最大値は同じ（最大流＝最小カット）になる可能性があるため、複数通りの配分を試すとよい。
• 「各段の最大値を単純合算すればよい」と思う誤り。ノード間で共有する辺（ボトルネック）を無視すると誤答になる。
• 無向図的に見えても、フロー割当ては辺ごとに容量制約と流量保存を満たす必要がある。逆向き残余を間違えると過大評価につながる。

補足コラム

• 最大流／最小カット定理は、実務での帯域幅配分や回線冗長化の評価に直結します。図のように複数経路が絡むときは、単一路ごとの最大値ではなく「カット」に着目すると上限がわかりやすくなります。
• 実際の解法は Ford–Fulkerson 法や Edmonds–Karp（幅優先で経路を選ぶ）を使うと、増加パスの見逃しを防げます。手計算では主要な増加パスを順に潰し、最後にS–Tのカットを確認するのが定番です。

FAQ