= Widest augmenting path
{title2=$\max_{P:s\leadsto t}\min_{e\in P}c_{\mathrm{res}}(e)$}
An <augmenting path> maximizing the possible increase in flow, namely its smallest <residual network> edge capacity. If the remaining maximum flow is $F>0$ and the original undirected network has $m$ edges, a path has bottleneck at least $F/m$. Otherwise the vertices reachable through arcs of capacity at least $F/m$ define a cut of capacity strictly less than $F$, contradicting the <max-flow min-cut theorem>. Only one directed arc per original crossing edge contributes to that cut.
Back to article page
