Network F ow Given a flow fin G,an augmenting path p is a directed path from s to tin the residual graph R.The bottleneck capacity of p is the minimum residual capacity along p.The number of edges in p will be denoted by |p. Theorem (max-flow min-cut theorem):Let (G,s t,c)be a network and fa flow in G.The following three statements are equivalent: (a)There is a cut{S,乃with(S,T刀=li. (b)fis a maximum flow in G. (c)There is no augmenting path for f.◼ Given a flow f in G, an augmenting path p is a directed path from s to t in the residual graph R. The bottleneck capacity of p is the minimum residual capacity along p. The number of edges in p will be denoted by |p|. ◼ Theorem (max-flow min-cut theorem): Let (G, s, t, c) be a network and f a flow in G. The following three statements are equivalent: (a) There is a cut {S, T} with c(S, T)=|f|. (b) f is a maximum flow in G. (c) There is no augmenting path for f. Network Flow