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...")
(No difference)

Revision as of 02:04, 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

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.