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, vV, 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