Network flow — max-flow min-cut theorem, Ford-Fulkerson, Edmonds-Karp

3.5.16 · Coding › Graphs

HUM KYA model kar rahe hain

KYU max-flow = min-cut (derivation scratch se)

Step 1 — Kisi bhi cut pe flow $∣ f ∣$ ke barabar hota hai.

Koi bhi cut $(S, T)$ lo. $S$ ke saare nodes par conservation equation ka sum karo. Internal edges (dono endpoints $S$ mein) ek baar $+ f$ aur ek baar $- f$ ke roop mein aate hain aur cancel ho jaate hain. Jo bachta hai woh sirf cut cross karne wala flow hai: $∣ f ∣ = \sum_{u \in S, v \in T} f (u, v) - \sum_{u \in S, v \in T} f (v, u)$ Yeh step kyun? Conservation $S$ ke andar sab kuch balance karti hai, isliye $S$ se net baahri flow, $s$ se net baahri flow ke barabar hona chahiye, jo hai $∣ f ∣$ .

Step 2 — Weak duality: har flow ≤ har cut. $∣ f ∣ = \leq c \sum f (forward) - \geq 0 \sum f (backward) \leq \sum c (forward) = c (S, T)$ Kyun? Forward flows capacity se cap hote hain; backward flows subtract hote hain aur $\geq 0$ hote hain. Isliye koi bhi flow value kisi bhi cut capacity se bounded hai. Hence $max ∣ f ∣ \leq min c (S, T)$ .

Step 3 — Equality achievable hai (max-flow min-cut theorem).

Jab flow maximum hota hai, residual graph mein koi augmenting path NAHI hota (aage define hoga). Maano $S =$ residual graph mein $s$ se reachable saare nodes, $T$ = baaki. Tab $t \in / S$ . Is cut ke liye:

har forward edge $u \to v$ ( $u \in S, v \in T$ ) saturated hai ( $f = c$ ), warna $v$ reachable hota;
har backward edge $f = 0$ carry karta hai, warna woh $T$ mein ek residual edge deta.

Step 1 mein plug karo: $∣ f ∣ = \sum c (forward) - 0 = c (S, T)$ . Toh yeh flow ek cut capacity ke barabar hai, aur Step 2 se dono optimal hain. $■$

Residual graph (saare algorithms ka engine)

Ek augmenting path residual graph mein koi bhi $s \to t$ path hai. Iski bottleneck uspe minimum $c_{f}$ hai; utna push karna $∣ f ∣$ ko strictly increase karta hai.

Ford–Fulkerson (the method)

Formula Ford–Fulkerson

f = 0
while there exists an augmenting path P in residual G_f:
    b = min residual capacity along P
    push b along P:  forward edges f += b, backward edges f -= b
return f

YEH kaise terminate/correct hota hai: jab koi augmenting path nahi hota, theorem se $f$ maximum hai.

Complexity: integer capacities ke saath, har iteration $\geq 1$ add karta hai, toh $O (E \cdot ∣ f^{*} ∣)$ . Bure path choice se yeh slow ho sakta hai (value-dependent). Irrational capacities ke saath toh yeh terminate bhi nahi kar sakta!

Edmonds–Karp (ek smart path rule)

Figure — Network flow — max-flow min-cut theorem, Ford-Fulkerson, Edmonds-Karp

Worked Example 1 — haath se push & augment karo

Network: $s \to a$ (cap 3), $s \to b$ (2), $a \to b$ (1), $a \to t$ (2), $b \to t$ (3).

Path 1: $s \to a \to t$ , bottleneck $= min (3, 2) = 2$ . Push 2. Kyun? $a \to t$ limiter hai. Path 2: $s \to b \to t$ , bottleneck $= min (2, 3) = 2$ . Push 2. Path 3: $s \to a \to b \to t$ , residual: $s \to a$ mein $3 - 2 = 1$ hai, $a \to b = 1$ , $b \to t = 3 - 2 = 1$ . Bottleneck $= 1$ . Push 1. Ab $∣ f ∣ = 2 + 2 + 1 = 5$ . Aur kyun nahi? $s$ ki out-capacity $3 + 2 = 5$ hai, sab saturated — yahi min cut hai $S = {s}$ , $c = 5$ . Max flow = 5. ✔

Worked Example 2 — backward edge bacha leta hai

$s \to a$ (1), $s \to b$ (1), $a \to b$ (1), $a \to t$ (1), $b \to t$ (1).

Greedy $s \to a \to b \to t$ choose karta hai, bottleneck 1. Kyun panic ho sakta hai? Ab $a \to t$ aur $s \to b$ unusable lagte hain. Lekin residual mein backward $b \to a$ (cap 1) hai. Naya path: $s \to b \to a \to t$ ? — $s \to b$ (1), backward $b \to a$ (1), $a \to t$ (1). Push 1. Total $= 2$ = min cut. Yeh step kyun? Backward edge ne buri commitment $a \to b$ undo ki, $a \to t$ ko free kiya. ✔

Recall Feynman: ek 12-saal ke bacche ko explain karo

Socho ek tap se ek bucket tak water pipes hain. Har pipe sirf itna hi carry kar sakti hai. Tum chahte ho maximum paani bucket tak pahunche. Limit hai network ki sabse kamzor jagah — pipes ka woh sasta set dhundho jise cut karne se koi paani nahi jaata, aur exactly wahi hai max paani jo tum bhej sakte ho. Algorithm "abhi bhi khule raaste" dhundta rehta hai, paani push karta hai, aur ise allow bhi hai ki woh pehle try kiye ek raaste se paani wapas le aur better jagah bheje. Jab koi khula raasta nahi bachta, done — bottleneck hit ho gayi.

Flashcards

Ek flow network ke har edge par kya chahiye aur kaun se do special nodes hote hain?

Ek capacity

c (u, v) \geq 0

; ek source

s

aur ek sink

t

Ek valid flow ke do constraints batao.

Capacity (

0 \leq f \leq c

) aur conservation (in-flow = out-flow har non-

s, t

node par).

Ek s–t cut

(S, T)

ki capacity define karo.

c (S, T) = \sum_{u \in S, v \in T} c (u, v)

— sirf forward

S \to T

edges.

Max-flow min-cut theorem state karo.

max ∣ f ∣ = min c (S, T)

; max flow value minimum cut capacity ke barabar hoti hai.

Flow ke maximum hone ki teen equivalent conditions kya hain?

(a)

f

max flow hai, (b) residual graph mein koi augmenting path nahi, (c)

∣ f ∣ = c (S, T)

kisi cut ke liye.

Edge

(u, v)

ki residual capacity kya hai, aur kaun sa backward edge appear hota hai?

c_{f} (u, v) = c (u, v) - f (u, v)

; plus backward edge

v \to u

jisme capacity

f (u, v)

hai.

Backward residual edges kyun chahiye?

Pehle committed flow ko undo/re-route karne ke liye taaki greedy mistakes correct ho sakein.

Augmenting path kya hai aur woh kitna flow carry karta hai?

Residual graph mein ek

s \to t

path; apni bottleneck carry karta hai = uspe minimum residual capacity.

Integer capacities ke saath Ford-Fulkerson ki complexity kya hai?

O (E \cdot ∣ f^{*} ∣)

— max-flow value par depend karta hai (slow ho sakta hai).

Edmonds-Karp ko kaun sa rule define karta hai aur iski complexity kya hai?

Hamesha BFS-shortest path se augment karo;

O (V E^{2})

, capacities se independent.

Edmonds-Karp capacity-independent kyun hai?

BFS distances kabhi decrease nahi hote; har edge

O (V)

baar saturate hota hai →

O (V E)

augmentations ×

O (E)

BFS.

Max flow run karne ke baad min cut kaise recover karte hain?

S

= final residual graph mein

s

se reachable nodes;

T

= baaki. Cross karne wale forward edges saturated hain.

Kisi bhi cut pe flow

∣ f ∣

ke barabar kyun hota hai?

S

par conservation ka sum internal edges cancel kar deta hai, net flow out of

S

= net flow out of

s

∣ f ∣

bachta hai.

Connections

Graphs — base data structure & traversal
BFS — Edmonds-Karp ka shortest-augmenting-path engine
Bipartite Matching — unit-capacity max flow ke roop mein solve hota hai
Linear Programming Duality — max-flow/min-cut iski combinatorial special case hai
Dinic's Algorithm — level graphs + blocking flows se faster $O (V^{2} E)$
Menger's Theorem — edge/vertex disjoint paths = ek flow corollary