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
Submit
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.
Submit
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
N
2
0.5 N
3
N
3
Submit