Networks and flows

#matematik-discmath

Definition: Network, weight function

A network is a Directed graph together with a weight or capacity function .

Definition: Source, sink

Let be a network.

A source is a vertex such that all arcs containing are directed away from .

A sink is a vertex such that all arcs containing are directed towards .

We will consider networks where a source and sink exist.

Definition: Flow

A flow from the source to the sink in a network is a function such that for every where , and where for every , where is the capacity function.

Theorem

Let be a network with a source and sink , and let be a flow in . Then Proof:
We have

Definition: Value

The value of a flow is

Definition: Cut

Let be a network and be a partition of such that and . Then is called a cut, and the capacity of the cut is

Theorem

If is a flow from to and is any cut, then Proof:

Theorem

If is a flow from to and is any cut, then .

Proof:
By Theorem, we have

Now, suppose that is a maximum flow and that is a cut with corresponding minimum capacity. From the theorem above we thus know that
We will see later that this is actually an equality.

Definition: Residual graph

Let be a network and a flow in . The residual graph of with respect to is a network with the vertices of , and where

  • For each edge , if , there is a forward edge in with capacity .
  • For each edge , if , there is a backward edge in with capacity .

The residual graph thus shows where additional flow can be added or removed. The forward edges show where additional flow can be introduced without exceeding the capacity, and the backward edges show where flow can be removed without introducing negative flow.

Definition: Augmenting path

Let be a network and a flow in with residual graph . An augmenting path is a directed path in from to .

A way to maximize flow given a network is now clear; find an augmenting path and introduce more flow along it. Specifically, it is clear that a flow of precisely the minimum capacity along the augmenting path can be introduced. We can show that by repeating this process until no augmenting path exists, always yields a maximum flow.

Theorem

Let be a network. The maximum value of a flow from to is equal to the minimum capacity of a cut separating and .

Proof:
Let be a flow in , and let be its residual graph. If there is an augmenting path in , introduce a flow of precisely the minimum capacity along the augmenting path. Repeat this process until there is no augmenting path.

We are thus left with a flow in such that there is no augmenting path. Let be the vertices reachable by directed paths from in (such paths are sometimes called incomplete augmenting paths), and be the rest of the vertices. Then, for any and where we know since if there would be an edge in making reachable from , contradicting that . Hence Furthermore, for any and where we know since if there would be an edge in making reachable from , contradicting that . Hence By Theorem, this flow is maximal.