Flows in directed graphs

From Cophy
Jump to: navigation, search

Contents


Introduction

Let G = (V,E) be a directed graph with two distinguished nodes, a source s ∈ V  and a sink t ∈ V. Let \scriptstyle c:\ E\ \rightarrow\ \mathbb{R_+} be a capacity function that assigns nonnegative weights to the edges of the graph. Further, for each node v ∈ V  let

\delta^+(v) = \{(v,w):\ w\ \in\ V,\ (v,w)\ \in\ E\}\,\! be the set of all outgoing edges of v,
\delta^-(v) = \{(w,v):\ w\ \in\ V,\ (w,v)\ \in\ E\}\,\! be the set of all ingoing edges of v.

Let f(e) indicate the 'quantity' passing an edge e ∈ E. Moreover let \scriptstyle f(A) = \sum\limits_{e\ \in\ A} f(e) denote the value of a function f  for all subsets A ⊆ E. Now we can define st flows on the directed graph G = (V,E).

Definition Flow

A function \scriptstyle f:\ E\ \rightarrow\ \mathbb{R_+} is called st flow (or simply flow) if the following conditions are satisfied:
  1. 0\ \le\ f(e)\ \le\ c(e)\,\! for all edges e ∈ E.
  2. f(\delta^+(v)) = f(\delta^-(v))\,\! for all nodes v ∈ V \{s,t}.

The first condition is called capacity constraint. The second condition is a flow conservation constraint — it is also known as Kirchhoff's law. It guarantees that the total flow into any node v ∉{s,t is equal to the total flow out of v.


Example 1

We investigate the following directed graph G = (V,E) with capacities c(e) = 1 for all edges e ∈ E.

Example1

Then the function \scriptstyle f:\ E\ \rightarrow\ \mathbb{R_+} with

f(s,2) = f(2,3) = f(1,t) = 1\,\!,
f(s,1) = f(3,1) = f(3,t) = 0.5\,\!,
f(3,s) = 0\,\!

satisfies the flow conditions (see Definition 1), i.e., f is an st flow in the graph G = (V,E).


The value | f | = f + (s)) − f(s)) is called value of the flow f. For instance, the value of the flow in Example 1 is 1.5. A maximum st flow is a st flow with maximum value.

Let δ + (S) = {(v,w) ∈ Ev ∈ Sw ∉ S} and δ(S) = {(v,w) ∈ Ev ∉ Sw ∈ S} be the set of all outgoing and ingoing edges of S ⊆ V, respectively. For instance we choose S = {s,1,2} in Example 1. That implies δ + (S) = {(2,3),(1,t)} and δ(S) = {(3,s),(3,1)}.

Lemma 1. Let f  be an st flow in G. Then for all subsets S ⊆ V with s ∈ St ∉ S it holds

|f| = f(\delta^+(S)) - f(\delta^-(S))\,\!.

A subset S ⊆ V  with s ∈ St ∉ S is called st cut with the value \scriptstyle c(\delta^+(S)) = \sum\limits_{e\ \in\ \delta^+(S)} c(e). A minimum st cut is a st cut with minimum value. The flow on the st cut S is f + (S)) − f(S)).

Because of the capacity constraint of flows the following inequality is satisfied for all st cuts S:

f(\delta^+(S)) - f(\delta^-(S)) \le\ c(\delta^+(S))\,\!.

Obviously the value of an st flow f on any st cut S with S ⊆ V  cannot exceed the capacity of this st cut.

Thus it is

\max\{|f|:\ f\ is\ an\ s-t\ flow\}\ \le\ \min\{c(\delta^+(S)):\ S\ is\ an\ s-t\ cut\}\,\!.

Herein the inequality can be replaced by equality. This is stated in the famous max-flow min-cut theorem which was proved by Ford/Fulkerson.

Theorem 2. Let G = (V,E) be a directed graph with st ∈ Vs ≠ t, and \scriptstyle c:\ E\ \rightarrow\ \mathbb{R_+}. Then the maximum value of an st flow in G is equal to the minimum value of an st cut.


Example 2

We investigate the graph of Example 1 again. Then \scriptstyle f^*:\ E\ \rightarrow\ \mathbb{R_+} with:
f * (s,1) = f * (s,2) = f * (1,t) = f * (2,3) = f * (3,t) = 1 (red edges in the above figure)
and f^*(3,s) = f^*(3,1) = 0\,\! is a maximum flow with value | f * | = 2.

Now we want to prove that f * is indeed maximum. For this we use the max-flow min-cut theorem. We consider the st cut S = {s}. It holds c + (s)) = 2. Since this is an upper bound to the values of the st flow, f * is maximum.


For more details we refer the interested reader to the standard textbook on network flows by [Ahuja et al. (1993)].

Personal tools