1. Max-flow to min-cost. Consider the following graph (where blue nodes are sources, yellow nodes are relays, red nodes are sinks, and the edge capacity is labeled on each edge) We wish to maximize the flow from the source to the sink nodes. Using the trick learned in lecture 5, you will formulate this problem as a min-cost problem. DO NOT use Julia to solve the problem. Simply state the answers to the questions. a) Recall the min-cost model from class max c r subject to Ax=b Remember that A (the incidence matrix) is a property of the graph, not the specific problem Find A for this graph. What is r What are p and q? b) Modify the graph using the trick to formulate a min-cost problem. What is your new r, p, and q? What are c and b? Remember from lecture 7 that the dual problem of this problem is the minimum cut problem c) What is the minimum cut of the this graph (you can just look at the graph to determine the minimum cut, and either give the solution either graphically or as a list of the edges in the cut)? What can you say about the values of the dual variables corresponding to the capacity constraints Ag and the nodal balance constraints 1. Max-flow to min-cost. Consider the following graph (where blue nodes are sources, yellow nodes are relays, red nodes are sinks, and the edge capacity is labeled on each edge) We wish to maximize the flow from the source to the sink nodes. Using the trick learned in lecture 5, you will formulate this problem as a min-cost problem. DO NOT use Julia to solve the problem. Simply state the answers to the questions. a) Recall the min-cost model from class max c r subject to Ax=b Remember that A (the incidence matrix) is a property of the graph, not the specific problem Find A for this graph. What is r What are p and q? b) Modify the graph using the trick to formulate a min-cost problem. What is your new r, p, and q? What are c and b? Remember from lecture 7 that the dual problem of this problem is the minimum cut problem c) What is the minimum cut of the this graph (you can just look at the graph to determine the minimum cut, and either give the solution either graphically or as a list of the edges in the cut)? What can you say about the values of the dual variables corresponding to the capacity constraints Ag and the nodal balance constraints