a (1) Find a max flow in the network we looked at in class, but start...

  

Transcribed Image Text:

a (1) Find a max flow in the network we looked at in class, but start with the all-0 flow. (2) (a) Solve the problem of finding a largest matching in the graph G below by formulating the matching problem as a max flow problem in a network D. You will need to add two new vertices r and t, some new edges and some new edges, and the edges need capaticies. (b) Find a max flow and min cut in your network. (c) Use your answers to (b) to give a maximum matchings and minimum vertex cover in G. d f PO g h i j k p G a (1) Find a max flow in the network we looked at in class, but start with the all-0 flow. (2) (a) Solve the problem of finding a largest matching in the graph G below by formulating the matching problem as a max flow problem in a network D. You will need to add two new vertices r and t, some new edges and some new edges, and the edges need capaticies. (b) Find a max flow and min cut in your network. (c) Use your answers to (b) to give a maximum matchings and minimum vertex cover in G. d f PO g h i j k p G