= Residual reachability certificate for maximum flow
In a finite <flow network>, a <maximum flow> exists because the <feasible flow> set contains the zero <flow> and is a <compact set>: the <capacity constraints> bound every coordinate, and they and <flow conservation> define a <closed set>. The <strength of a flow> is a <continuous function>, so the <extreme value theorem> gives an attained maximum. An <augmenting path> in the <residual network> would permit positive augmentation, contradicting maximality. The source-reachable <vertices> in the <residual network> therefore define a <cut of a flow network> whose outgoing original <edges> are saturated and incoming original <edges> carry zero <flow>. <Flow conservation> makes the <strength of a flow> equal to this <cut capacity>, proving the <max-flow min-cut theorem>.
Existence and <strong duality> for finite real <flow network edge capacities> do not imply finite termination for every choice of <augmenting paths> in the <Ford-Fulkerson algorithm>. With irrational capacities, some choices can continue forever. With integer capacities, <Integrality of the Ford-Fulkerson algorithm> instead forces finite termination; rational capacities reduce to that case by a common denominator. Choosing shortest <augmenting paths> as in the <Edmonds–Karp algorithm> avoids dependence on capacity magnitudes.https://courses.csail.mit.edu/6.854/21/Notes/n06-flow.html[Karger, MIT 6.854 Notes 6, section 2.1, rational and real capacities]{ref}
Back to article page
