Basic flow definitions

From Algowiki
Jump to: navigation, search

Basic definitions

  1. Basic graph definitions

Basic setting

On this page and all dependent pages, is an anti-symmetric, simple directed graph, unless stated otherwise.

  1. For , there is a nonnegative upper bound .
  2. In some flow problems, there is a lower bound as well, which need not be nonnegative.
  3. In some flow problems, each node has a required balance (or balance for short) . We also speak of the node balance.
  4. In some flow problems, there is a real-valued (not necessarily nonnegative) cost factor .

Other node and arc attributes may occur in specific flow problems. Unless stated otherwise, there are no node or arc attributes except for the upper bounds on arcs.

Neutral values of attributes: When a node or arc is added to a graph, it is sometimes appropriate to set its attributes to neutral values. The neutral values for upper and lower bounds are and , respectively. For cost factors and node balances, the neutral value is zero.

Remark: Simplicity and anti-symmetry do not reduce generality in the context of flow problems:

  1. If there are two arcs and , say, from to , add a new node to , replace by new arcs and , transfer the attribute values of to and set all attributes of and of to their neutral values.
  2. If there is a loop , add a new node to , replace by and , and set the attribute values analogously to the case of parallel arcs.
  3. If , add a new node to , replace by new arcs and , and set the attribute values analogously to the case of parallel arcs.

Integrality assumption: All numerical node and arc attributes are integral.

In the context of flow problems, this assumption usually does not reduce generality, either: Choosing a sufficiently small and replacing each attribute value by the nearest integral multiple of has a negligible impact on the output, at least in the classical types of flow problems.

Feasible flow

Let be an arc weighting, that is, a value is given for each arc .

Capacity constraints:

  1. We say that fulfills the capacity constraints if for all .
  2. If lower bounds are given, the condition is to be replaced by . In particular, may be negative if is so.

Flow conservation condition: Let .

  1. An arc weighting fulfills the flow conservation condition with respect to if for all nodes : .
  2. If there are balance values for all nodes , the right-hand side of this condition is not zero but .

Feasibility:

  1. A feasible flow (or flow for short) with respect to is an arc weighting that satisfies the capacity constraints and the flow conservation condition.
  2. For , a feasible -flow is a feasible flow with respect to .
  3. For , a feasible -flow is a feasible flow with respect to .

Preflow

  1. Preflows generalize feasible flows as follows: Instead of an equation, the following inequality is to be fulfilled for each : (resp., , if node balances are given).
  2. The excess of is the value of the left-hand side of that inequality. A node is active if its excess is strictly positive.

Flow value

Let such that , and let be a flow with respect to . The flow value of is defined by

.

Remark: A straightforward induction on shows that for all partitions of with , and , it is

.

In particular, mirror-symmetrically to the definition of , it is

.

Residual network

The residual network of with respect to an arc weighting is defined as follows: It is , and for each arc , we have:

  1. with if .
  2. with if .

The value of an arc is called the residual capacity of with respect to .

Remark: Changes of in and changes of in are equivalent in an obvious way. Since is anti-symmetric, this equivalence is one-to-one. So, the view on and is exchangeable with the view on and . We will adopt both views simultaneously in the presentation and discussion of the individual algorithms. An implementation of an algorithm may be based on or on or even on both representations simultaneously.

Flow-augmenting paths and saturated arcs

A flow-augmenting path (or augmenting path for short) from some node to some node is an ordinary path in the residual network . Equivalently, a flow-augmenting path is a generalized path in such that:

  1. if is a forward arc;
  2. if is a backward arc.

An arc is saturated

  1. in forward direction if .
  2. in backward direction if .

We say that an arc of a path is saturated if it is saturated in the direction of this path. Clearly, a path is augmenting if, and only if, it contains no saturated arc in its direction.

Augmenting along a path

Let denote some flow-augmenting path in , and let such that

  1. if is a forward arc;
  2. if is a backward arc.

In the residual network , augmenting by along the ordinary path induced by means reducing all residual capacities by . Equivalently, for each arc on in , this means:

  1. Increase the flow value by if is a forward arc on .
  2. Decrease the flow value by if is a backward arc on .

Obviously, the capacity constraints are preserved. The flow conservation conditions are preserved at every internal node of . To see that, let be such an internal node, and let and denote the immediate predecessor and successor of on , respectively. Basically, there are four cases:

  • Either is on as a forward arc or is on as a backward arc.
  • Either is on as a forward arc or is on as a backward arc.

It is easy to check preservation of the flow conservation conditions at for each of these four cases.

Augmenting up to saturation: Again, let denote some flow-augmenting path.

  1. Let denote the minimum of the values on all forward arcs of .
  2. Let denote the minimum of the values on all backward arcs of .
  3. Let denote the minimum of and .

Augmenting the flow along by yields at least one saturated arc.

Cuts and saturated cuts

  1. Let be a directed graph and . An -cut (or cut for short) is a bipartition of such that and .
  2. For , let and be real values such that ( need not be a flow here). A cut is saturated if:
    1. for every arc such that and .
    2. for every arc such that and .

Valid distance labeling

Definition:

  1. Let be a directed graph, and for each arc let and be defined such that . An assignment of a value to each node is a valid distance labeling if the following two conditions ar fulfilled:
    1. It is .
    2. For each arc in the residual network, it is .
  2. If even , is called an admissible arc.