本文共 4025 字，大约阅读时间需要 13 分钟。

1.1 Flow Networks

A flow network G = (V, E) is a directed graph where each edge (u, v) has a nonnegative capacity c(u, v) ≥ 0. If an edge (u, v) exists in E, its reverse (v, u) cannot exist in E. If (u, v) is not in E, its capacity is defined as 0. The network must contain a source s and a sink t, and there must be a path from s to t through other vertices.

A flow in G is a function f: V × V → R that satisfies two properties:

1. **Capacity Constraint**: For all u, v ∈ V, 0 ≤ f(u, v) ≤ c(u, v).

2. **Flow Conservation**: For all u ∈ V \ {s, t}, the sum of flow entering u equals the sum of flow leaving u. If (u, v) is not in E, f(u, v) = 0.

The flow value |f| is defined as the total flow out of the source minus the flow into the source, calculated as:

|f| = ∑_{v ∈ V} f(s, v) - ∑_{v ∈ V} f(v, s)

Modeling Problems with Antiparallel Edges

When an edge (u, v) exists in E, its reverse (v, u) is not allowed. To handle this, we can add a virtual vertex to create antiparallel edges, ensuring the flow constraints are maintained. This approach helps in modeling problems where bidirectional flow is required.

Networks with Multiple Sources and Sinks

Complex flow networks may have multiple sources and sinks, requiring a more flexible approach. The flow network must still satisfy the basic properties of flow conservation and capacity constraints while accommodating multiple input and output points.

1.2 The Ford-Fulkerson Method

The Ford-Fulkerson algorithm is used to find the maximum flow in a flow network. It starts with an initial flow of 0 and iteratively increases the flow by finding and augmenting along an augmenting path in the residual network. Each iteration increases the flow by at least 1 unit, ensuring progress.

Residual Networks

Given a flow network G and a flow f, the residual network G_f is constructed by subtracting the flow f from the original capacities. This residual network includes both the original edges and reverse edges to represent the possible flow decreases. The residual capacity c_f(u, v) is defined as:

c_f(u, v) = { c(u, v) - f(u, v) if (u, v) ∈ E, f(v, u) if (v, u) ∈ E, 0 otherwise }

Augmenting Paths

In the Ford-Fulkerson algorithm, an augmenting path is a simple path from s to t in the residual network G_f. The maximum flow that can be increased along this path is determined by the minimum residual capacity of the edges along the path. Augmenting along this path updates the flow and residual capacities accordingly.

Cuts of Flow Networks

A cut (S, T) of a flow network G = (V, E) is a partition of V into S and T where s ∈ S and t ∈ T. The net flow across a cut is the difference between the total flow from S to T and the total flow from T to S. The minimum cut in a flow network provides an upper bound on the maximum flow.

The minimum cut capacity is the sum of the capacities of the edges from S to T. The value of the maximum flow is bounded above by the capacity of the minimum cut. Finding the minimum cut is crucial for determining the maximum flow in a network.

The Basic Ford-Fulkerson Algorithm

The Ford-Fulkerson algorithm repeatedly finds an augmenting path in the residual network and increases the flow along this path. It uses BFS to find the shortest augmenting path in terms of residual capacity, ensuring that the algorithm terminates when no more augmenting paths exist.

The algorithm's time complexity is O(|f| * E), where |f| is the maximum flow and E is the number of edges in the graph. This ensures that the algorithm is efficient for finding the maximum flow in most practical networks.

The Edmonds-Karp Algorithm

The Edmonds-Karp algorithm optimizes the Ford-Fulkerson method by using BFS to find the shortest path in terms of residual capacity from s to t in the residual network. This approach reduces the number of iterations required, resulting in a time complexity of O(V * E²), where V is the number of vertices and E is the number of edges. This makes the algorithm more efficient for networks with larger capacities and more complex structures.