notes an edge (vuwith capacity in the residual graph figure shows the residual graph after finding our first pathfigure the dashed edges are the edges we added in the residual graph / / / / / the capacity of the dashed edge is the same as the amount of water carried by the solid edge in the opposite direction so here is an algorithm to find the maximum flowfirst construct the residual graph (in the beginningthe residual graph is the same as the network graphwhile there exists path from to in the residual graphwe flow water through one of the path ( path in the residual graph is called an augmenting pathwe then adjust the residual graph accordingly once we can no longer find any more path in the residual graphwe have found the maximum flow comparison networks suppose we have directed network (vedefined by set of nodes (or vertexesand set of arcs (or edgeseach arc ( ,jin has an associated nonnegative capacity uij also we distinguish two special nodes in ga source node and sink node for each in we denote by (iall the arcs emanating from node let max uij by ( ,jin let us also denote the number of vertexes by and the number of edges by we wish to find the maximum flow from the source node to the sink node that satisfies the arc capacities and mass balance constraints at all nodes representing the flow on arc ( ,jin by xij we can obtain the optimization model for the maximum flow problemmaximize (xx ij es subject to \{stij : ij : <xij <uij (ij(ije vector (xijwhich satisfies all constraints is called feasible solution ora flow (it is not necessary maximalgiven flow we are able to construct the residual network with respect to this flow according to the following intuitive idea suppose that an edge ( ,jin carries xij units of flow we define the residual capacity of the edge ( ,jas rij uij xij this means that we can send an additional rij units of flow from vertex to vertex we can also cancel the existing flow xij on the arc if we send up xij units of flow from to over the arc ( ,jsogiven feasible flow we define the residual network with respect to the flow as follows suppose we have network (vea feasible solution engenders new (residualnetwork lovely professional university