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

ネットワーク最大流【午前2解説】

正解の理由

• 最小カットの容量 = 上限 = 10
• その容量を満たす具体的な流が存在する → 最大流 = 10

解法ステップ

1. 問題を最大流問題として認識する（源点 X、吸収点 Y、各辺が容量）。
2. 有望な s−t カットを検討する。左側に X と中間列（A,B,C）を置くと、左→右に跨る辺は A−D, B−D, B−E, C−F の4本で合計容量 $1+2+3+4=10$ となる。
3. そのカット容量が上限であることを確認（任意の流はこのカットを通るためこれ以上は流せない）。
4. 上限10を達成する具体的な流を構成して可達性を示す（以下に割当てを示す）。
5. よって最大流＝最小カットの値＝10。

• X→A: $3/4$、 X→B: $4/4$、 X→C: $3/3$ （Xからの合計流 = 10）
• 左側内部
  • A→D: $1/1$（A→右へ）
  • A→B: $2/2$（AからBへ補給）
  • B→D: $2/2$
  • B→E: $3/3$
  • B→C: $1/1$（BからCへ，Cの不足分を補う）
  • C→F: $4/4$
• 右側内部・終点へ
  • D→Y: $3/3$（A→DとB→Dをまとめて流す）
  • B→E→Y 経路：B→E の 3 を E→Y へ $3/3$
  • F→G: $3/3$、F→E: $1/2$（Fの4を G に 3、E に 1 分配）
  • E→G: $1/4$（F→E で入った余剰 1 を G 側へ中継）
  • G→Y: $4/6$（F→G の 3 と E→G の 1 をまとめて送る）

• D→Y: 3、E→Y: 3、G→Y: 4 → 合計 10 を達成します。すべての辺で容量制約を超えておらず、カット容量を満たす実現可能な流です。

選択肢別の誤答解説

• ア: 8
  一部の受験者は X からの辺の総和（4+4+3=11）や右端からの Y に入る辺の和（3+3+6=12）を誤って直接比べ、余裕のある辺を単純に減算して 8 等の数字を出します。だが内部のボトルネック（例えば A−D=1 や B−D=2）が存在するため単純な和では決められません。よって 8 は過小評価です。
• イ: 9
  一部の経路割当てで 9 までしか確保できない構成のみを考えてしまうミスです。正しくは最小カットを見つけ、その容量を満たす流を組めることを示す必要があります。最小カットを見落とすと 1 単位分（今回なら A→B→... の使い方）を見逃すため 9 となる誤りが起きます。
• ウ: 10（正解）
  前述の通り、ある s−t カットの容量が $10$ かつその値を実現する流が構成できるため最大流は 10 です。
• エ: 11
  X からの出力容量合計が 11 であることに基づき「11 が上限」と早合点する誤り。だがネットワーク内部の狭い辺（A−D, B−D など）があるため 11 全てを Y へ送れないことに注意。

よくある誤解

• 「X から出る容量の合計が答え」：X からの合計は 11 だが、途中の枝に制約があり必ずしも全量を Y へ送れない。
• 「右端の Y に接する辺の和が答え」：Y に接する枝和は 12 だが左側からの到達が制限されるため上限にはならない。
• 増加路だけを見て9までしか増やせなかった構成を最終解とする（最小カットを探して上限を確認しない）。

補足コラム

• 最大流問題の解法は増加路を繰り返すフォード–ファルカーソン法や、効率的なエドモンズ–カープ法、Dinic 法などが基本です。試験では小さなネットワークでは「有望なカットを探して容量を合計する」ことで素早く上限を求め、次にその上限を達成する具体的な流の構成を示すのが実務的かつ確実です。
• 今回は左側集合 {X,A,B,C} と右側集合 {D,E,G,F,Y} の分割が自然で、カット容量計算が簡潔にできました。問題を見たらまず「どの辺を跨ぐと容量合計が小さくなるか」を探してください。

FAQ