Max flow problem

Motivation and basics can be found in the following lecture: click on this link

Flow problem allow to model a wide class of problems. They correspond to physical flows in a traffic/electric/gas grid. The problem is to forward the largest quantity of material from a source s to a destination t.

Definition

A network is an oriented graph N=(V,A) with a positive value on its arcs. Tje value c(x,y) on (x,y) is called the capacity. N have two specific nodes: a source s and a destination/sink t. Other vertices are called intermediate.

A flow is the quantity of material passing from a vertex to another. This quantity must be inferior or equal to the capacity of the arc. Furthermore, it is not possible to stock or to produce materials in intermediate vertices. A flow is similar to the laws of Kirchhoff.

A flow F in a network N have the two following properties:

  1. For all arc a ∈ A, 0F(a)c(a)
  2. For all intermediate vertex xV \ { s,t }, ∑y F(y,x) = ∑y F(x,y)

The sum F(x) =yF(y,x) is the incoming flow of vertex x
La somme F+(x) =yF(x,y) is the outcoming flow of vertex x
The value | F | for a flow F is defined as | F | = F+(s)F(s). In a basic flow problem, it’s equal to zero.

A flow problem

A basic flow problem is a linear problem. We suppose that between any couple of vertices it exists an arc. If an arc have no capacity, it is equal to zero. The objective function is the outcoming flow at the source or the incoming flow at the sink.

Constraints of a flow problem are as following:

  • Capacity: f(u,v) ≤ c(u,v)
  • Symmetry: f(u,v) = – f(v,u)
  • Flow conservation: | F |=0
  • etc.

Various industrial problems are similar to a flow problem or can be reduced to.

Problem’s reduction

Multi-source multi-sinks: a parent source is linked to every sources and the capacity of each new arc verifies the flow conservation rule. Same with a parent sink.

Problème de flot avec capacité aux sommets: vertices are duplicated, the capacity of the new arc substitute the vertex’ capacity.

Problème du plus court chemin: the source is the start and the sink is the end with d(s)=1 et d(t)=-1. There is no capacity’s constraints and the cost of each flow is equal. The problem become a min cost flow.

Cut and residual graph

A cut (E,T) of a graph N=(V,A) is a partition of V between E and T=V-E such as s ∈E and t∈T. We defined the capacity of the cut c(E,T) as the sum of the capacity of all arcs (u,v) with u in the set E and v in the set T. For any cut (E,T) and a flow f, |f| cannot exceeded c(E,T).
Taking N=(V,A) a graph and a flow f, we named residual capacity cf (u,v) = c(u,v) – f(u,v). If the capacity of (v,u) is zero, then cf (v,u) = f(u,v). A residual capacity is superior or equal to zero.

The residual graph N’=(V,A) is based on all residual capacity and the capacity minus the residual one. An augmenting path is a path in the residual graph.

residuel

Publicités