## Algorithms:

- Max flow
- Min cost flow
- Network simplex – see Simplex
- Cycle-canceling
- Busacker & Gowen
- Algorithme Out-of-kilter

- Problem
- To search a path in a flow

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

*to a destination*

**s***.*

**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 F in a network N have the two following properties:

- For all arc
**a ∈**,**A****0**≤≤**F(a)****c(a)** - For all intermediate vertex
∈**x****V****\ {**, ∑*s,t*}_{y}= ∑**F(y,x)**_{y}**F(x,y)**

The sum F^{–}**(x) ****=*** ∑_{y}F(y,x)* is the incoming flow of vertex

**x**La somme F

^{+}

**(x)****=**

*is the outcoming flow of vertex*

**∑**_{y}F(x,y)

**x**The value

**|**for a flow

*F*|*is defined as*

**F****|**=

*F*|*–*

**F**^{+}*(s)**In a basic flow problem, it’s equal to zero.*

**F**^{–}(s).## 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

_{f}(u,v) = c(u,v) – f(u,v). If the capacity of (v,u) is zero, then c

_{f}(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.