Networks, Flows: capacity constraint, conservation of flow, value of a flow. Maximum flows in networks, auxiliary graphs, flow augmenting paths. Edmonds-Karp algorithm (without proof of correctness).

Network (!!!)

A network is a digraph (directed graph) G(V, E) with a non-negative capacity function c : E(G) → [0, ∞) on every edge, and two distinguished vertices: s called the source and t called the sink. It is denoted by the tuple (G, s, t, c). Vertices that are neither the source nor the sink are called nodes.

Flow (!!!)

A flow on a network is a function f : E(G) → [0, ∞) satisfying two conditions: Capacity constraint: 0 ≤ f(e) ≤ c(e) for every edge e. Flow cannot be negative and cannot exceed the capacity of the edge. Conservation of flow: f⁺(v) = f⁻(v) for all nodes v ≠ s, t, where f⁺(v) denotes the out-flow and f⁻(v) denotes the in-flow of v. The incoming flow must equal the outgoing flow at every node.

Value of a Flow (!!!)

The value of a flow is defined as: val(f) = f⁺(s) − f⁻(s) = f⁻(t) − f⁺(t). It represents the net flow leaving the source (equivalently, the net flow arriving at the sink). ( val(f) = f⁺(s) − f⁻(s) )

Maximum Flow

A maximum flow is a feasible flow with the largest possible value. It is found using the Edmonds-Karp algorithm.

Auxiliary Graph

Given a network (G, s, t, c) and a flow f, the auxiliary graph Hf is a directed graph on V(G). For each edge e = u→v: If f(e) < c(e), the auxiliary graph contains a forward edge u→v with label c(e) − f(e), representing how much additional flow can be sent along e. If f(e) > 0, the auxiliary graph contains a backward edge v→u with label f(e), representing how much flow on e can be reduced.

Flow Augmenting Path

Given a network (G, s, t, c), a flow f, and the corresponding auxiliary graph Hf, a flow augmenting path is a directed path from s to t in Hf. If such a path exists, the flow can be increased by δ, the minimum label along the path (the bottleneck).

Edmonds-Karp Algorithm (!!!)

Input: Network (G, s, t, c). Set f(e) = 0 for every edge e. Construct the auxiliary graph Hf. Run BFS on Hf to find the shortest flow augmenting path from s to t. If an augmenting path exists: Let δ be the minimum label along the path. For each forward edge on the path, set f(e) ← f(e) + δ. For each backward edge on the path, set f(e) ← f(e) − δ. Repeat from step 2. If no augmenting path exists, let S be the set of vertices reachable from s in Hf and stop. Output: A maximum flow f and the set S of vertices reachable from s in the final auxiliary graph. Running time: O(|V| · |E|²). ( O(|V| · |E|²)