Arbres couvrants et flots dans les
graphes
Table des matières
I - Algorithme de Ford-Fulkerson 3
1. Algorithme de Ford-Fulkerson ..................................................................................3
1.1. Motivation .........................................................................................................................................3
1.2. Coupe minimale ................................................................................................................................3
1.3. Complexité ........................................................................................................................................3
2
Algorithme de Ford-Fulkerson I
1. Algorithme de Ford-Fulkerson
algorithme de Ford-Fulkerson
1.1. Motivation
Motivation
“Idée” d’un algorithme pour déterminer un flot maximal :
Initialisation : partir du flot nul qui est réalisable.
Tant que l’on trouve un “chemin” µ allant de s à t Augmenter la valeur du flot sur ce chemin au
maximum.
Fin Tant que
Initialisation :
Chemin µ = (s, 2, 4,t) :
L’algorithme réel est plus complexe et s’appuie sur un graphe auxiliaire appelé “graphe d’écart”.
1.2. Coupe minimale
Coupe Minimale par l’algorithme
Pour un flot f maximal, considérons l’ensemble W des sommets accessibles à partir de s dans un graphe
¯
particulier construit depuis G appelé “le graphe d’écart”. Alors (W , W )est une coupe minimale.
1.3. Complexité
Complexité
Pour un réseau de n sommets et m arcs, l’algorithme de Ford-Fulkerson consiste :
à construire le graphe d’écart : O(n + m)
à rechercher itérativement un chemin quelconque de s à t ou déterminer s’il n’en existe pas :
parcours en profondeur en O(n + m)
à effectuer la mise à jour : O(m)
3
Algorithme de Ford-Fulkerson
Donc l’algorithme est en O(nb_iter ∗ (n + m)) avec nb_iter le nombre de fois où l’on déterminer un
chemin de G .f
Dans le pire des cas, si les capacités sont entières, on augmente le flot d’une seule unité de flot : ainsi
nb_iter est borné par la valeur de la coupe minimale. Une borne sur cette valeur est n fois le maximum des
capacité des arcs.
Complexité
L’algorithme de Ford-Fulkerson est en O(Cmaxnm) où Cmax est le maximum des capacités des arcs.
