1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
# 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
|
