Difference between revisions of "Augmenting path"

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:

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.
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)$ .
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.

Difference between revisions of "Augmenting path"

Revision as of 02:04, 9 September 2013

Augmenting a flow

Navigation menu

Personal tools

Namespaces

Variants

Views

More

Search

Navigation

Tools