Lab: Flow Networks 1. You are given the following graph that shows a flow network with the capacity and flow associated with each edge. It is not the graph that would necessarily result from the algorithm discussed in class 5/10 5/5 13 13 8/8 8/8 38/10 0/3 0/3 5/ 5/10 a) What is the value of this flow? b) Use the algorithm discussed in class to find the next augmenting path? What is the augmenting path? c) Find the resulting flow? Draw a picture of the resulting graph with the edges labeled with their capacities and flows. d) In trying to find the next augmenting path, the algorithm stops without reaching the sink. What is the value of maximal flow? e) What is the set of labeled vertices? f) What is the set of unlabeled vertices? g) What is the cut? h) What is the capacity of this cut? How does this compare with the value found in d) Lab: Flow Networks 1. You are given the following graph that shows a flow network with the capacity and flow associated with each edge. It is not the graph that would necessarily result from the algorithm discussed in class 5/10 5/5 13 13 8/8 8/8 38/10 0/3 0/3 5/ 5/10 a) What is the value of this flow? b) Use the algorithm discussed in class to find the next augmenting path? What is the augmenting path? c) Find the resulting flow? Draw a picture of the resulting graph with the edges labeled with their capacities and flows. d) In trying to find the next augmenting path, the algorithm stops without reaching the sink. What is the value of maximal flow? e) What is the set of labeled vertices? f) What is the set of unlabeled vertices? g) What is the cut? h) What is the capacity of this cut? How does this compare with the value found in d)