Network F ow ● For any vertex uand any subset AcV,let fu,A) denote fu,A),and 4 u)denote A,u).For a capacity function c du,A)and dA,u)are defined similar. The value of a flow f denoted by f,is defined to be If=f(s,)=∑f(s,v) Lemma:For any cut {S,D and a flow,7). Max-Flow Problems:Design a function f for the network(G,s,t,c),so that f is the maximum
◼ For any vertex u and any subset AV, let f(u, A) denote f({u}, A), and f(A, u) denote f(A, {u}). For a capacity function c, c(u, A) and c(A, u) are defined similar. ◼ The value of a flow f, denoted by |f|, is defined to be Network Flow | | ( , ) ( , ) v V f f s V f s v = = ◼ Lemma: For any cut {S, T} and a flow f, |f|=f(S, T). ◼ Max-Flow Problems: Design a function f for the network (G, s, t, c), so that |f| is the maximum
Network Fow Given a flow fon Gwith capacity function c the residual capacity function for fon the set of pairs of vertices is defined as follows. ◆ For each pair of vertices,u,ve v,the residual capacity ru v)=du,v-fu,v).The residual graph for the flow is the directed graph R=(,E),with capacities defined by rand E={(山,小(u,>0 ◆ The residual capacity /(u,v represents the amount of additional flow that can be pushed along the edge (u,v without violating the capacity constraints. If fu,v<du,v),then both (u,v)and (v,u)are present in R.If there is no edge between wand vin G,then neither (u,v)nor (v,u)are in E Thus,2E
◼ Given a flow f on G with capacity function c, the residual capacity function for f on the set of pairs of vertices is defined as follows. ◼ For each pair of vertices, u, vV, the residual capacity r(u, v)=c(u, v)-f(u, v). The residual graph for the flow f is the directed graph R=(V, Ef ), with capacities defined by r and Ef={(u, v)|r(u, v)>0} ◼ The residual capacity r(u, v) represents the amount of additional flow that can be pushed along the edge (u, v) without violating the capacity constraints. ◼ If f(u, v)<c(u, v), then both (u, v) and (v, u) are present in R. If there is no edge between u and v in G, then neither (u, v) nor (v, u) are in Ef . Thus, |Ef |2|E|. Network Flow
Network Flow Example:what's the residual graph of the following graph? 9,7 a 6,2 2,2 5,5 9,2 s 3,3 t 5,5 8,5 6,2 b (x,y):x is the capacity,y is the flow
◼ Example: what’s the residual graph of the following graph? Network Flow s a b c d t 6, 2 5, 5 5, 5 9, 7 9, 2 6, 2 3, 3 2, 2 8, 5 (x, y): x is the capacity, y is the flow
Network Fow Let fand f'be any two flows in a network G.Define the function ff'by (A')(u,v)=u,v)+f'(u,v)for all pairs of vertices u and v.Similarly,define the function Ff'by(ff'(u,)=u,Wf'(山,). Lemma:Let fbe a flow in Gand f'the flow in the residual graph R for f.Then the function Af'is a flow in Gof value +f'. Lemma:Let fbe any flow in Gand f*a maximum flow in G.If R is the residual graph for then the value of a maximum flow in R is f*-f
◼ Let f and f ’ be any two flows in a network G. Define the function f+f ’ by (f+f ’)(u, v)=f(u, v)+f ’(u, v) for all pairs of vertices u and v. Similarly, define the function f-f ’ by (f-f ’)(u, v)=f(u, v)-f ’(u, v). ◼ Lemma: Let f be a flow in G and f ’ the flow in the residual graph R for f. Then the function f+f ’ is a flow in G of value |f|+|f ’|. ◼ Lemma: Let f be any flow in G and f * a maximum flow in G. If R is the residual graph for f, then the value of a maximum flow in R is |f * |-|f|. Network Flow
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