Network Flows and Maximum Flow

6.854 Advanced Algorithms Lecture 6: 9/24/2003 Lecturers: Erik Demaine, David Karger Network flows. Maximum flow. 6.1 General definitions Definition 1 Network is a directed graph G = (V, E), in which there is a source vertex s ∈ V, a sink vertex t ∈ V, and on each edge (u, v) there is defined a capacity of the edge, u(u, v) ≥ 0. (It is useful also to define the capacity for any pair of vertices (u, v), so that for any (u, v) ∈ E, u(u, v) = 0.) Figure 6.1: An example of a network with 4 vertices and 6 edges. The capacities of the edges are shown on the edges. There are two ways to define a flow: raw flow and net flow. Definition 2 Raw flow is a function   r(u, v) ≥ 0 for each edge (u, v). Function r satisfies the following properties: • Conservation: ∑(r(w, v) - r(v, w)) = 0 for all v ∈ V \{s, t}. • Capacity: r(u, v) ≤ u(u, v). Definition 3 Net flow is a function f(u, v): V² → ℝ that satisfies the following conditions: Lecture 6: 9/24/2003 Figure 6.2: An example of a raw flow for the network above. The flow has a value of 2. Skew symmetry: f(v, w) = -f(w, v). Conservation: ∑(f(w, v) - f(v, w)) = 0 for all v ∈ V \{s, t}. Capacity (feasibility condition): f(v, w) ≤ u(v, w) for all v, w ∈ V. To ease some notations later in the lecture, we will denote ∑(f(w, v)) by f(v, S) or -f(S, v). Definition 4 Value of a flow f is defined as |f| = ∑(f(s, v)). Definition 5 Maximum flow problem: given a network G, find the flow with maximum value. The maximum flow problem is the problem that we will try to solve in this lecture. Definition 6 Residual network   Gf of a network G and flow f is a network that contains the same vertices as the network G, but the capacities of the edges are u'(v,   w) = u(v, w) - f(v, w). (From feasibility conditions it results that u'(v, w) ≥ 0 and u'(v, w) ≤ u(v, w) + u(w, v)). Gf has edges wherever u'(v, w) > 0. Figure 6.3: An example of a residual network. This residual network corresponds to the network and flow depicted in the previous figures. The dashed line corresponds to a possible augmenting   path. Lecture 6: 9/24/2003 Definition 7 Augmenting path is a directed path from the node s to node t in the residual network. Note that we can push additional unit of flow along such a path in the original network G. The maximum value that we can push on a path   {s,v₁,v₂,...vk,t}; is min {u'(s,v₁),u'(v₁,v₂), u'(v₂,v₃),...u'(vk-1,vk),u'(vk,t)}. If, for a given network \[f_{c}\] there exists an augmenting path in \(G_{f},\) then the flow f is not maximum. More generally, we can add and subtract a flow in \(G_{f}\) to the flow f (in network G). Thus, if we have a flow \(f^{\prime}i   G_{II}\) then the flow \(f+f^{\prime}\) is a valid flow in G. Conversely, if we have a flow f' in G, then the flow \(f-f^{\prime}\) is a valid flow \(G_{f}.\) Definition 8 A cut is a partition of vertices into 2 groups S and \(\mathcal{S}=V\backslash\) . Definition 9 An st cut is a cut, such that \(s\in S t\in\hat{S}.\) Figure 6.4: An illustration of the s-t cut. \(s\in S t\in\overline{S}_{i}\) There might be both edges from Sto \(\overline{S}\) and from S to S. Definition 10 Net flow along cut S and S is defined as \(f(S)=\sum_{v\in S}\sum_{w\in S}f(v,w).\) Definition 11 Value (capacity) of a cut is defined as \(u(s)=\sum_{v\in S}\sum_{w\in S}u(v,w).\) Figure 6.5: An example of a cut in a network. The set cut is represented by a dashed line. The value (capacity) of the cut is equal to 3. This is one of the minimum s-t cuts. Lemma 1 All   st cuts carry the same flow, that is for any cut S, S, it holds that value of flow f. \[f(S)=|f|=\] Lecture 6: 9/24/2003 Proof: We will prove by induction on the size of the sets S that \(f(S)=|f|.\) For \(S={s}\) the claim is true. Now, we move one vertex from   S to \(\overline{S}\). Let this vertex be v. The value \(f(S)\) changes in the following way: * \(f(S)\) increases by \(f(v,\overline{S})\) * \(f(S)\) decreases by \(f(\overline{S},v)=-f(v,\overline{S})\) Concluding, as a result of moving the vertex v from S to \(\overline{S}\), the total change in the value of \(f(S)\) is equal to \(f(v,\overline{S}) + f(v,\overline{S}) = f(v,V) = 0\) by conservation of flow. A conclusion of the above lemma is that \(|f| = f(S) ≤ u(S)\), and, therefore, any flow, including the maximum flow, has a value equal or less than the capacity of the minimum cut. Theorem 1 (Max-Flow Min-Cut Theorem). The value of the max flow is equal to the value of the minimum s-t cut:   \(|f| = min_{S} u(S)\), where f is a flow and S is a s-t cut. Proof: Consider a max flow f in a network G. Since the flow f is a maximum flow, the residual network   Gf has no augmenting paths and, therefore, is disconnected. Let S = {vertices reachable from s in Gf}. Since t is not reachable, the set S describes a s-t cut. Figure 6.6: Network Gf is disconnected. The set S contains all the nodes that are reachable from s. Since all edges (u, v) straddling the cut have residual capacity 0, it means that for these edges \(f(v,w) = u(v,w)\). Therefore, \(|f| = f(S) = u(S)\). In other words, for a max flow f with a s-t cut S, \(|f| ≤ u(S)\). With the conclusion from the lemma above, we can conclude that the value of the max flow is equal to the value of the minimum s-t   cut. 6.2 Ford-Fulkerson Algorithm Ford-Fulkerson algorithm solves the problem of finding a maximum flow for a given network. The description of the   algorithm is as follows: 1. Start with \(f(v,w)   = 0\)