In a network flow graph, what is the MAX-FLOW MIN-CUT Theorem state?
The Max-Flow Min-Cut Theorem proves that the maximum amount of flow passing from source s to sink t equals the minimum total capacity of edges in an s-t cut.
What is the worst-case time complexity of the Edmonds-Karp implementation of the Ford-Fulkerson algorithm using BFS to find augmenting paths?
Edmonds-Karp uses BFS to select the shortest augmenting path (number of edges). Each augmenting path step takes O(E) time and at most O(V * E) augmentations occur, yielding O(V * $E^2)$ time.
In a residual graph $G_f$, an AUGMENTING PATH is:
An augmenting path is a directed path from s to t in the residual network where every edge has $c_f$(u, v) > 0, allowing additional flow to be pushed.
If capacities in a flow network are ALL INTEGERS, the Ford-Fulkerson algorithm guarantees that:
Integrality Theorem: If all capacity values are integers, Ford-Fulkerson terminates with an optimal max flow where all edge flow values f(u, v) are integers.
The capacity of an s-t cut (S, T) in a flow network is defined as:
The capacity c(S, T) of a cut (S, T) is strictly the sum of capacities of directed edges going from set S to set T. Edges from T to S are NOT added.