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

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

正解の理由

• X → A → D → Y : 1
• X → A → B → D → Y : 1
• X → B → D → Y : 1
• X → B → E → Y : 2
• X → A → B → E → Y : 1
• X → C → F → G → Y : 3
• X → B → C → F → E → G → Y : 1

• X–A: 3（1+1+1）、X–B: 4（1+2+1）、X–C: 3（3）
• A–D:1、A–B:2、B–D:2、B–E:3、B–C:1、C–F:4
• F–G:3、F–E:1、D–Y:3、E–Y:3、E–G:1、G–Y:4

解法ステップ

1. 問題を最大流（s = X, t = Y）問題として把握する。各辺は容量を示す。
2. 有効な上界を探すために適当なs−t切断（＝SとT = V\Sの分割）を選ぶ。第1コラムと第2コラムの境界（S = {X, A, B, C}）は自然で、横切る辺容量の和を計算する。
3. 切断の容量が上界となる（最小カット ≤ 最大流）。この場合は $1+2+3+4=10$。
4. その上界に到達する流の具体例を構成する（パスの組み合わせで各辺容量を超えないように配分）。
5. 構成した流が10ならばmax-flow = min-cut = 10と結論付ける。

選択肢別の誤答解説

• ア（8）: 切断容量が10であるため8は上界を超えておらず過小評価。具体的な割当で10を実現できることから不正解。
• イ（9）: 9も10を上回っていない最小カットに矛盾する。さらに、容量配分を試すと10に到達可能であるため9は最適ではない。
• ウ（10）: 上で示したように、切断による上界10に到達する実行可能な流が存在するため正しい。
• エ（11）: 切断S = {X,A,B,C} による容量和が10であり、任意の流はこの値を超えられない（最小カット ≤ 最大流）。従って11は不可能。

よくある誤解

• 切断の選び方を雑にして上界を見落とす（第1コラム→第2コラムの自然な切断を見逃す）。
• 内部の縦辺（A–B, B–C）を無視して、X→Bに過大な流を直接割り当ててしまう（X–Bの容量は4で、Bに必要な量を補うためA→BやB→Cを利用する必要がある）。
• F–Gの容量（3）やF→E（2）を超えて分配してしまう。複数経路で合計が辺容量を超えないか厳密に合計確認すること。

補足コラム

• 本問は「最大流＝最小カット定理」を使う典型問題です。実務的には、まず簡単な切断で上界を見つけ（列や段ごとに分けることが多い）、次にその上界に到達可能かを経路割当で示すのが得点につながります。
• 経路割当はユニットごとに分解（流の分解）して示すと、各辺の負荷が見えやすく検算が容易になります。

FAQ