Network Flows

Interactive visualizations for Chapter 11 of the Ricerca Operativa notes

Ford–Fulkerson — Step-by-step Explorer

Flow Network G

Residual Network R_x

```kawsv //| echo: false viewof stepSlider = Inputs.range([0, 7], {value: 0, step: 1, label: "Step:"})

<button class="ff-btn" id="btn-reset">↺ Reset</button>
<button class="ff-btn" id="btn-prev">← Prev</button>
<button class="ff-btn" id="btn-next">Next →</button>
<span id="step-counter"></span>

<div class="legend-item">
  <svg width="28" height="12" style="overflow:visible">
    <path d="M2,6 Q14,0 26,6" stroke="#1a6abb" stroke-width="2" fill="none" marker-end="url(#lmk-fwd)"/>
    <defs><marker id="lmk-fwd" markerWidth="6" markerHeight="5" refX="5" refY="2.5" orient="auto"><polygon points="0 0, 6 2.5, 0 5" fill="#1a6abb"/></marker></defs>
  </svg>
  Forward residual arc — solid, bows up (remaining capacity k−f)
</div>
<div class="legend-item">
  <svg width="28" height="12" style="overflow:visible">
    <path d="M2,6 Q14,12 26,6" stroke="#999" stroke-width="1.5" stroke-dasharray="4,2" fill="none" marker-end="url(#lmk-bwd)"/>
    <defs><marker id="lmk-bwd" markerWidth="6" markerHeight="5" refX="5" refY="2.5" orient="auto"><polygon points="0 0, 6 2.5, 0 5" fill="#999"/></marker></defs>
  </svg>
  Backward residual arc — dashed, bows down (used flow f, can be cancelled)
</div>
<div class="legend-item"><div class="legend-swatch ls-path"></div>Augmenting path found by BFS (green)</div>
<div class="legend-item"><div class="legend-swatch ls-sat"></div>Saturated arc in G</div>

{
  if (window.goToFlowStep) {
    window.goToFlowStep(stepSlider);
  }
}

```

The Flow Network

We work with a directed flow network of 5 nodes throughout this chapter.

Nodes: s, a, b, c, t
Arcs (with capacities): s→a(5), s→b(6), a→b(3), a→c(4), b→t(7), c→t(3)
Max flow = 10 (min cut: {s,a,b,c} | {t}, cut capacity = 7 + 3 = 10)

Use Next → and ← Prev to step through Ford–Fulkerson. Each step clearly labels whether the residual network shown is before or after the augmentation.

Ford–Fulkerson: How It Works

The algorithm runs in three phases per iteration:

Phase	What you see
🔍 Search	Current flow in G and current R_x. BFS is about to run.
➡️ Push	R_x with the found path highlighted. Bottleneck computed. Flow is about to be pushed.
✅ Update	G and R_x after pushing. Backward arcs appear, saturated arcs disappear from R_x.

The Residual Network

For each arc \((u, v)\) with capacity \(k_{uv}\) and flow \(x_{uv}\):

Residual arc	Capacity	Meaning
\(u \to v\) (forward, blue)	\(k_{uv} - x_{uv}\)	remaining capacity
\(v \to u\) (backward, grey)	\(x_{uv}\)	cancel already-pushed flow

The Three Iterations

Iteration	Augmenting path	Bottleneck	φ
1	\(s \to a \to c \to t\)	min(5, 4, 3) = 3	0 → 3
2	\(s \to a \to b \to t\)	min(2, 3, 7) = 2	3 → 5
3	\(s \to b \to t\)	min(6, 5) = 5	5 → 10

Max Flow = 10

Arc	Flow / Cap	Saturated?
s → a	5 / 5	✅
s → b	5 / 6
a → b	2 / 3
a → c	3 / 4
b → t	7 / 7	✅
c → t	3 / 3	✅

Flow conservation: a: 5 in = 5 out ✓ b: 7 in = 7 out ✓ c: 3 in = 3 out ✓

Min cut: S = {s,a,b,c}, T = {t} — cut arcs b→t(7) + c→t(3) = 10 = max flow ✓