# Network Flows

This is a problem about Network Flows.

A. The Edmonds Karp max-flow algorithm uses Breadth First Search to find the augmenting path. What is the running time of the Edmonds-Karp algorithm to find the maximum flow?

B. Here is a flow network. Trace the execution of the Edmonds-Karp algorithm to find the maximum flow. Draw a separate picture for each augmenting step - clearly showing the residual graph and the flow network. What is the value of the maximum flow?

C. What is the value of the maximum flow? (Your answer should be a number.)

D. Give a minimum cut for this flow network. (Your answer should be two sets of vertices, S and T.)

https://brainmass.com/computer-science/searching/network-flow-functions-20210

#### Solution Preview

This is a problem about Network Flows.

A. The Edmonds Karp max-flow algorithm uses Breadth First Search to find the augmenting path. What is the running time of the Edmonds-Karp algorithm to find the maximum flow?

O(VE2)

B. Here ...

#### Solution Summary

Network Flows are highlighted.