img
Question:
Published on: 12 October, 2024

State the Max-flow min cut theorem for network flow analysis. Trace the execution of Ford-Fulkerson algorithm for finding the maximum flow in the graph.

Answer:

Max-flow min cut theorem for network flow analysis:

If f is a flow in a flow network G(V,E) with source s and sink t, then the following conditions are equivalent:

  • f is a maximum flow in G.
  • the residual network Gf contains no augmenting paths.
  • lfl=C(S,T) for some cut (S,T) of G.