Max Flow quiz



Given a flow network, let f be any flow and let (A,B) be any cut. Then, the net flow across (A,B) is __________ the value of f.

less than
greater than
equal to
not related to

When running Ford-Fulkerson as per our Java implementation, how does the algorithm know when to terminate?

When the flow for some cut is equal to the inflow at t.
By analyzing each cut and determining that the minimum-capacity cut is equal to the current value of the flow.
When BFS cannot find a path from s to t on the residual graph.
When all of the incoming edges to t are full OR all of the outgoing edges from s are full.

Suppose that you run the Ford-Fulkerson algorithm (using the shortest augmenting path heuristic) to solve a bipartite matching problem with N students and N companies. How many augmenting paths are needed in the worst case?

N
N2
0.5 N3
N3