Describe and analyze an algorithm for finding all of the upper-binding edges in a flow network G when given a maximum flow f? in G. Your algorithm should run in time O(n + m), where n is the number of nodes and m is the number of edges.

2. (Worth: 3 points. Page limit: 1 sheet; 2 sides) (a) For the network G below determine the max s-t flow, f, the residual network Gf, and a minimum s-t cut 5 1 (b) An edge in a flow network is called upper-binding if increasing its capacity by one unit increases the maximum flow in the network. Similarly, an edge in a flow network is called lower-binding if reducing its capacity by one unit decreases the maximum flow in the network. Identify all of the upper-binding and all of the lower-binding edges in the above flow network. (c) Describe and analyze an algorithm for finding all of the upper-binding edges in a flow network G when given a maximum flow f in G. Your algorithm should run in time O(n+m), where n is the number of nodes and m is the number of edges 2. (Worth: 3 points. Page limit: 1 sheet; 2 sides) (a) For the network G below determine the max s-t flow, f, the residual network Gf, and a minimum s-t cut 5 1 (b) An edge in a flow network is called upper-binding if increasing its capacity by one unit increases the maximum flow in the network. Similarly, an edge in a flow network is called lower-binding if reducing its capacity by one unit decreases the maximum flow in the network. Identify all of the upper-binding and all of the lower-binding edges in the above flow network. (c) Describe and analyze an algorithm for finding all of the upper-binding edges in a flow network G when given a maximum flow f in G. Your algorithm should run in time O(n+m), where n is the number of nodes and m is the number of edges