st-cut, capacity of a cut, flow across a cut, equivalence to value of flow. Ford-Fulkerson theorem, Integrality lemma, and modifications of network flow problems.

st-cut (!!!)

Let S ⊂ V(G) such that s ∈ S and t ∉ S. Then S is called an st-cut. In other words, an st-cut is any partition of the vertices that puts the source and sink on opposite sides.

Capacity of a Cut (!!!)

Given an st-cut S, the capacity of the cut is the sum of capacities of all edges leaving S: cap(S) = Σ c(e) for all edges e = u→v with u ∈ S and v ∉ S. Only outgoing edges from S count — edges entering S are ignored. ( cap(S) = Σ c(u→v), u ∈ S, v ∉ S )

Flow Across a Cut (!!!)

Given a network with a flow f and an st-cut S, the flow across the cut is defined as: (sum of flow leaving S) − (sum of flow entering S) = Σ f(u→v) − Σ f(u→v) for u ∈ S, v ∉ S and u ∉ S, v ∈ S respectively.

Equivalence to Value of Flow (!!!)

Given a flow f and an st-cut S, the flow across S equals val(f), the value of the flow out of s. Therefore, for any flow f and any st-cut S: val(f) ≤ cap(S). This means the value of any feasible flow is at most the capacity of any st-cut, and in particular, the maximum flow is at most the minimum cut capacity.

Ford-Fulkerson Theorem (!!!)

In every network, the maximum value of a feasible flow equals the minimum capacity of an st-cut. This is proven by running the Edmonds-Karp algorithm until no augmenting path exists. The set S of vertices reachable from s in the final auxiliary graph forms an st-cut whose capacity equals the value of the current flow, proving both are optimal.

Integrality Lemma (!!!)

If c(e) ∈ ℤ⁺ for all e ∈ E(G), then there exists a maximum flow that takes integer values on all edges, i.e. f(e) ∈ ℤ⁺ for all e ∈ E(G). This follows from the Edmonds-Karp algorithm: if all capacities are integers and we start from zero flow, the bottleneck δ at every step is always an integer.

Modification 1: Multiple Sources and Sinks (!!!)

Given multiple sources s₁, s₂, …, sₖ and multiple sinks t₁, t₂, …, tₗ, we add a super source S and a super sink T. We add edges with ∞ capacity from S to each sᵢ, and from each tⱼ to T. Any solution to this modified network gives a solution to the original problem.

Modification 2: Vertex Capacities (!!!)

If some vertices have a capacity constraint c(v) on the maximum flow passing through them, we replace each such vertex v with two new vertices vᵢₙ and vₒᵤₜ. All incoming edges go to vᵢₙ, all outgoing edges leave from vₒᵤₜ, and we add a single directed edge from vᵢₙ to vₒᵤₜ with capacity c(v).

Modification 3: Undirected Graphs (!!!)

Given an undirected graph with edge capacities, we construct a new directed graph G' with the same vertex set. For each undirected edge uv with capacity c(e), we add two directed edges u→v and v→u, both with capacity c(e). Any solution to this modified network gives a solution to the original problem