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

最大フロー計算【午前2解説】

正解の理由

解法ステップ

1. ネットワークをX（源）とY（湧出点）に分けて考え，s－tカットの候補を探す。単純にXと残りを分ける切断は容量 $4+4+3=11$ だが，もっと小さい切断が存在するか検討する。
2. S = {X, A, B, C} を取ると，S→Tを横断する辺はA–D(1), B–D(2), B–E(3), C–F(4) で合計10になる。これにより最大値の上限は10と分かる（最小カット ≤ 10）。
3. 上限が本当に到達可能かを示すため，具体的なフロー割当（増加パス）を示す。以下はX→Yに送る合計10を構成する経路分解の一例（各経路の流量を示す）：
   • X–A–D–Y : 1
   • X–A–B–E–Y : 2
   • X–B–D–Y : 2
   • X–B–C–F–G–Y : 1
   • X–C–F–G–Y : 2
   • X–C–F–E–G–Y : 1
   • X–B–E–Y : 1 これらを合計すると1+2+2+1+2+1+1 = 10となり，各辺の容量制約を全て満たす（下で辺ごとの合計を確認）。
4. カットの上界（10）と到達可能性（具体的フロー）が一致するので最大流は10。従って選択肢ウが正しい。

• X–A: 1+2 = 3 ≤ 4
• A–B: 2 ≤ 2
• A–D: 1 ≤ 1
• X–B: 2+1+1 = 4 ≤ 4
• B–D: 2 ≤ 2
• B–E: 2+1 = 3 ≤ 3
• B–C: 1 ≤ 1
• X–C: 2+1 = 3 ≤ 3
• C–F: 1+2+1 = 4 ≤ 4
• F–G: 1+2 = 3 ≤ 3
• F–E: 1 ≤ 2
• E–G: 1 ≤ 4
• D–Y: 1+2 = 3 ≤ 3
• E–Y: 2+1 = 3 ≤ 3
• G–Y: 1+2+1 = 4 ≤ 6

選択肢別の誤答解説

• ア（8）
  8は明らかに小さすぎます。単純に下段経路や中段・上段の一部だけ見て過小評価している場合が多いです。上で示した10の構成を考えると8では説明できない流れが存在します。
• イ（9）
  9は「ほぼ正しい」と誤認しやすい値ですが，S = {X,A,B,C} のカット容量が10であるため9は上界を破らないが、9が最大であることを示す論拠（9を超えられないカット）を示せません。さらに具体的フローで10を構成できるため9は誤りです。
• ウ（10）
  上述の通り、S = {X,A,B,C} のカット容量が10（上界），かつ合計10を実現する具体的フローが存在するので正解です。
• エ（11）
  Xから直接出る辺の容量和 $4+4+3=11$ をそのまま最大流と判断すると誤りです。内部の中央部（A–DやB–D, B–E, C–Fなど）がボトルネックになり，それらを通過できる量の合計（最小カット）が10のため11を流すことは不可能です。

よくある誤解

• 出発点（X）からの辺の和をそのまま最大流と見なす誤り。出発点の出口和は上界の一つだが，内部のボトルネックで制限されることが多い。
• 個々の経路だけ見て重複する辺の容量制約を無視してしまう。複数経路で同じ辺を共有する場合，その辺の容量以上は流せない点を必ず確認する。
• 無向辺を矢方向に誤って片方しか使えないと解釈する／逆に方向を自由に使いすぎる誤解。問題の意味（ここでは同時に使用できる論理回線の多重度＝無向容量）を明確に扱う。

補足コラム

• 理論的支柱は「最大流＝最小カット定理」です。試験では「どこで切れば小さくなるか」を観察して最小カット候補を素早く見つけるのが得点に直結します。
• 手順の実務的な流れ：まず簡単なカット（例：Xとそれ以外）で上界を得て、それより小さいカットがないか中央部やシーム（複数列のつなぎ目）を点検する。見つかった小さいカットの容量を計算し、可能なら具体的フローを構成して到達可能性を示すと確実です。
• アルゴリズム的にはFord–Fulkerson（増加パスを繰り返す）、Edmonds–Karp（BFSを用いる）などで最大流を求められますが，筆算・図で解く午前問題では最小カットの観察と容易なフロー構成で済むことが多いです。

FAQ