Input: A network with single source 1, single sink n, and positive integer capac
ID: 3843752 • Letter: I
Question
Input: A network with single source 1, single sink n, and positive integer capacities u_ij on its edges (i, j) Output: A maximum flow x assign x_ij = 0 to every edge (i, j) in the network label the source with infinity, - and add the source to the empty queue Q while not Empty (Q) do i leftarrow Front (Q); Dequeue (Q) for every edge from i to j do//forward edges if j is unlabeled r_ij leftarrow u_ij - x_ij if r_ij > 0 l_j leftarrow mint [l_i, r_ij}; label j with l_j, i^+ Enqueue (Q, j) for every edge from j to i do//backward edges if j is unlabeled if x_ji > 0 l_j leftarrow mint{l_i, x_ji}; label j with l_j, i^- Enqueue (Q, j) if the sink has been labeled //augment along the augmenting path found j leftarrow n//start at the sink and move backwards using second labels while j notequalto 1//the source hasn't been reached if the second label of vertex j is i^+ x_ij leftarrow x_ij + l_n else//the second label of vertex j is i^- x_ji leftarrow x_ji - l_n j leftarrow i erase all vertex labels except the ones of the source reinitialize Q with the source return x//the current flow is maximum (a) What is the value of the flow below? (b)Use the algorithm discussed in class to find an augmenting path? (c) Find the resulting flow? What is the value of the flow? (d) Apply the algorithm once more. What happens? (e) What is the maximum flow in the flow network? (f) What is the cut that shows that this is the maximum flow?Explanation / Answer
The value of flow can be find by this formula E(s,v) where s=flow and v=capicity
5/10 + 8/8 + 5/5 =18/23 is the flow from the source.
The agumented path is 1--> 5 --> 4 -->6
the Max flow is 18
source sink flow {1} {2,3,5,4,6} 18 {1,2} {3,5,4,6} 13 {1,2,3} {5,4,6} 18 {1,2,3,5} {4,6} 18 {1,2,3,5,4} {6} 18