~/ learn/ comp-372/ cards/ Maximum flow (concept + Ford-Fulkerson)
1 of 5

Type the residual-capacity definitions for max flow

Type the residual-capacity definitions for max flow

Answer

forward residual: c_f(u, v) = c(u, v) - f(u, v) backward residual: c_f(v, u) = f(u, v) edge in G_f iff: c_f(u, v) > 0 augment by: c_f(p) = min over edges on p

Forward residual is the unused capacity; backward residual lets you cancel existing flow. Pushing the bottleneck c_f(p) along an augmenting path raises |f| by that amount.

space flip · ← → navigate · esc to exit
NORMAL ~/memra/library/9db2ef0c-e921-41e5-94b2-887290bdba0d/flashcard utf-8 LF