# Réseaux et flots
## Définitions
### Réseau
Graphe orienté, défini par ses noeuds et arcs
### Flot
- Quantité quelconque circulant sur les arcs d'un réseau
- Analogie avec un débit d'eau circulant dans des tuyaux

## Caractérisation des noeuds
### Noeud source

### Noeud puits
### Noeud de transbordement
- Noeud intermédiaire
- Tout le flot entrant doit être égal au flot sortant

## Capacité sur les arcs
- Quantité max de flots pouvant circuler sur l'arc
- Si le flot est le débit d'eau, la capacité est proportionnelle au diamètre du tuyau

## Flot maximum
-> réseau saturé

# Coupe de capacité maximale
## Définitions
### Coupe
Partition en 2 sous-ensembles $S$ et $\overline{S}$ des noeuds du réseau
### Coupe s-t
-> Soit $s$ un noeud source et $t$ un noeud puits
-> C'est une coupe telle que $s \in S$ et $t \in \overline{S}$
### Capacité d'une coupe s-t
Somme des capacités $(i,j)$ tels que $i \in S$ et $j  \in \overline{S}$
Attention au sens de l'arc

## Invariance du flot le long d'une coupe
- La valeur nette du flot le long de toute coupe est indépendant de la coupe
- Ceci signifie que la valeur du flot peut être récupérée le long d'une coupe quelconque, en comptant positivement les flots de $S$ vers $\overline{S}$ et négativement les autres

La valeur du flot dans un réseau est inférieure à la capacité de n'importe quelle coupe

## Théorème Max Flow Min Cut
- La valeur du flot maximum dans un réseau est égale à la valeur de la coupe de capacité minimale dans ce même réseau
- Ceci signifie que le flot maximum correspond à la capacité du "goulot d'étranglement" du réseau
# Algorithme de Ford-Fulkerson
## Graphe résiduel
La **capacité résiduelle** d'un arc $(i,j)$ de capacité $u_{i,j}$ sur lequel circule $x_{i,j}$ unités de flot se définit comme suit :
$$
\begin{align}
r_{i,j} = u_{i,j} - x_{i,j} \\
r_{j,i} = x_{i,j}
\end{align}
$$
Elle est égale à la capacité résiduelle minimale le long du chemin.
Un chemin **augmentant** dans un graphe résiduel est un chemin entre un noeud source et noeud puits ayant une capacité résiduelle strictement positive.

## L'algorithme
1. Trouver un chemin augmentant. S'il n'y en a pas le flot est déjà maximal
2. Sinon on calcule la capacité résiduelle $R$ du chemin et mettre ) jour les capacité résiduelles des arcs du chemin :
	1. augmenter la capacité résiduelle des arcs $(i,j)$ de $R$ unités
	2. diminuer la capacité résiduelle des arcs $(i,j)$ de $R$ unités
3. Recommencer
## Retour sur la coupe minimale
Pour trouver la coupe de capacité minimale associée, on définit $S$ en prenant les sommets atteignables depuis la source dans le graphe résiduel (+ la source)

## Validité de l'algorithme
1. Le flot est maximum entre $s$ et $t$
2. Le réseau résiduel ne contient aucun chemin augmentant
3. Il existe une coupe dont la capacité est égale à la valeur du flot