Difference between revisions of "Augmenting path"

From PEGWiki
Jump to: navigation, search
(Created page with "An augmenting path in a flow network is a path from the source to the sink in the residual network for some flow. It is so named because it is possible to ''augment'' (increa...")
 
 
Line 16: Line 16:
  
 
Intuitively, augmenting the flow corresponds to "pushing additional flow" along the augmenting path using residual capacity. The augmented flow is then the overall result of pushing both the original flow and the additional flow.
 
Intuitively, augmenting the flow corresponds to "pushing additional flow" along the augmenting path using residual capacity. The augmented flow is then the overall result of pushing both the original flow and the additional flow.
 +
 +
==Augmenting path theorem==
 +
It is now clear that a flow cannot be maximal as long as an augmenting path exists, as we can increase the flow by pushing along the augmenting path. The converse is less clear: if the flow is not maximal, then an augmenting path exists. This is the topic of this section.
 +
 +
'''Theorem (Augmenting path theorem)''': Let <math>f</math> be a flow in the flow network <math>(V, s, t, c)</math>. Then <math>f</math> is maximal if and only if there is no augmenting path in the residual network <math>(V, s, t, r)</math>.
 +
 +
'''Proof''': The "only if" direction is easy. The proof of the "if" direction is based on the [[max-flow min-cut theorem]]. Since there is no augmenting path, we can form the set <math>S \subset V</math> of vertices reachable from <math>s</math> in the residual network. As in the max-flow min-cut theorem, <math>\{ (u, v) \mid u \in S, v \notin S \}</math> forms an s-t cut of the weighted s-t graph corresponding to the original flow network, whose total weight equals the value of the flow <math>f</math>. Since every flow's value is less than or equal to every cut's total weight, <math>f</math> must be maximal. <math>_\blacksquare</math>
 +
 +
The augmenting path theorem forms the theoretical basis of the [[Ford–Fulkerson method]] for computing a max flow.

Latest revision as of 03:01, 9 September 2013

An augmenting path in a flow network is a path from the source to the sink in the residual network for some flow. It is so named because it is possible to augment (increase) the value of the flow by combining the existing flow with additional flow along the augmenting path.

Augmenting a flow[edit]

Let f be a flow in the flow network (V, s, t, c). Let (V, s, t, r) be the residual network corresponding to f. Now consider an augmenting path (s = v_0, v_1, \ldots, v_n = t) in the residual network. We will assume that the augmenting path is simple. Since edges must have positive capacity, the minimum residual capacity along all arcs on the augmenting path, c_m = \min_i c(v_i, v_{i+1}), is positive.

We define the augmented flow f' as follows: f'(u, v) = f(u, v) + c_m if the edge (u, v) is in the augmenting path; f'(u, v) = f(u, v) - c_m if the reverse edge (v, u) is in the augmenting path, and, otherwise, f'(u, v) = f(u, v).

Proposition: The augmented flow f' is an admissible flow. Furthermore, \sum_{v \in V} f'(s, v) = c_m + \sum_{v \in V} f(s, v); that is, the augmented flow's value is greater than the original flow's value by c_m.

Proof:

  1. Capacity. If f(u, v) \leq c(u, v), then clearly f'(u, v) \leq c(u, v) whenever f'(u, v) = f(u, v) - c_m or f'(u, v) = f(u, v). We only need to check the case f'(u, v) = f(u, v) + c_m. In this case, (u, v) is an edge in the augmenting path. By definition of c_m, we have that c_m \leq r(u, v). Therefore f'(u, v) \leq f(u, v) + r(u, v) = f(u, v) + c(u, v) - f(u, v) = c(u, v), as required.
  2. Skew symmetry. Let (u, v) be an edge. If (u, v) is an edge in the augmenting path, then f'(u, v) = f(u, v) + c_m = -f(v, u) + c_m = -(f(v, u) - c_m) = -f'(v, u). If on the other hand (v, u) is in the augmenting path, then f'(u, v) = f(u, v) - c_m = -f(v, u) - c_m = -(f(v, u) + c_m) = -f'(v, u). If neither is true, then f'(u, v) = f(u, v) = -f(v, u) = -f'(v, u).
  3. Flow conservation: Let v be a vertex other than the source or sink. If v is not in the augmenting path, then all flows into v are unchanged, and conservation is maintained. If v is in the augmenting path, then (since v \notin \{s, t\}) it must be preceded by a vertex v_p and followed by a vertex v_n in the augmenting path. Then f'(v_p, v) = f(v_p, v) + c_m, f'(v_n, v) = f(v_n, v) - c_m, and all other flows into v are unchanged. Since one inward flow is incremented and another decremented by the same amount, conservation is maintained.

Finally, consider the value of the augmented flow, \sum_{v \in V} f'(s, v). The source is always the first vertex in the augmenting path. Thus, \sum_{v \in V} f'(s, v) = f'(s, v_1) + \sum_{v \in V-\{v_1\}} f'(s, v) = c_m + f(s, v_1) + \sum_{v \in V-\{v_1\}} f'(s, v) = c_m + \sum_{v \in V} f(s, v). _\blacksquare

Intuitively, augmenting the flow corresponds to "pushing additional flow" along the augmenting path using residual capacity. The augmented flow is then the overall result of pushing both the original flow and the additional flow.

Augmenting path theorem[edit]

It is now clear that a flow cannot be maximal as long as an augmenting path exists, as we can increase the flow by pushing along the augmenting path. The converse is less clear: if the flow is not maximal, then an augmenting path exists. This is the topic of this section.

Theorem (Augmenting path theorem): Let f be a flow in the flow network (V, s, t, c). Then f is maximal if and only if there is no augmenting path in the residual network (V, s, t, r).

Proof: The "only if" direction is easy. The proof of the "if" direction is based on the max-flow min-cut theorem. Since there is no augmenting path, we can form the set S \subset V of vertices reachable from s in the residual network. As in the max-flow min-cut theorem, \{ (u, v) \mid u \in S, v \notin S \} forms an s-t cut of the weighted s-t graph corresponding to the original flow network, whose total weight equals the value of the flow f. Since every flow's value is less than or equal to every cut's total weight, f must be maximal. _\blacksquare

The augmenting path theorem forms the theoretical basis of the Ford–Fulkerson method for computing a max flow.

Retrieved from "http://wcipeg.com/wiki/index.php?title=Augmenting_path&oldid=1729"