Max Flow I

What are the core components of a flow network?

Directed Graph: G = (V, E). Source (s) & Sink (t): Two special vertices in the graph. Capacity (c): A value assigned to each edge representing the maximum possible flow. Flow (f): The actual amount of data/material sent through an edge.

What are the two primary constraints for a feasible flow?

Capacity Constraint: The flow on an edge cannot exceed its capacity (0

Define the (s,t)-cut and its relationship to flow value.

Definition: A partition of vertices into two sets, A (containing source s) and A-bar (containing sink t). Cut Capacity: The sum of all capacities of edges going from set A to set A-bar. The Lemma: The value of any feasible flow |f| is always less than or equal to the capacity of any (s,t)-cut. Optimality: Max flow is achieved when the flow equals the capacity of the minimum cut.

What is a Residual Network (Gf)?

A graph that represents the available capacity in the network. It includes: Forward Edges: Remaining capacity on an edge (c - f). Backward Edges: The ability to "undo" flow, equal to the current flow value (f).

Describe the Ford-Fulkerson Max Flow Algorithm in detail.

Initialization: Start by setting the flow f(u->v) to 0 for all edges in the graph. Construction: Construct the Residual Network (Gf) based on the current flow. Pathfinding: Search for any path (P) from the source (s) to the sink (t) within the Residual Network. This is called an "augmenting path". Bottleneck: Identify the "bottleneck capacity" b(P), which is the minimum residual capacity along that path. Augmentation: Update the flow along the path: add b(P) to forward edges and subtract b(P) from backward edges. Iteration: Repeat the construction and search steps until the sink (t) is no longer reachable from the source (s) in the residual network. Termination: Return the final flow f, which is now the maximum flow.

What determines if the Max Flow algorithm will terminate?

Integers: If edge capacities are integers, the algorithm is guaranteed to terminate. Irrational Numbers: If capacities are irrational and augmenting paths are not chosen carefully, the algorithm may fail to terminate.

If F is the max flow of graph G, and f is a current feasible flow, what is the max flow of the residual network Gf?

The value of the maximum flow in the residual network is the difference between the total maximum flow and the current flow: |F| - |f|.