## Algorithms:

- Max flow
- Min cost flow
- Problem
- To search a path in a flow
- Max flow problem with Excel

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. A naive algorithm consists to repeat the following process until you get stuck. Find a s − t path where each arc has f (e) < u(e) and augment flow along it by the minimum of u(e) − f (e). This method does not give an optimal value, we need to be able to backtrack.

## Problem’s reduction

Various problems can be reduced into max flow problem, for examples:

- network connectivity: edge-disjoint paths, network reliability.
- matching: bipartite matching, maximum matchings.
- vertex capacities: data mining.
- scheduling: airline scheduling, project selection.
- graph cuts: image processing.
- assignment: baseball elimination, distributed computing.

** 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.

* Flow with max-min capacities*: vertices are duplicated, the capacity of the new arc substitute the vertex’ capacity.

* Shortest path*: 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.

From the residual graph of a max flow, it is possible to find the solution of min-cut problem (and vice versa). In the following graph, if you seek for a set of connected vertices from vertex s you found the set {s,3,4,7} which is the set S for the min-cut problem.

## Finding a augmenting path

Find a s − t path in residual graph, it is called augmenting path. Once the path is selected, increase flow along forward edges, decrease flow along backward edges.