Introduction à l'algorithme de Ford et Fulkerson
Nous allons présenter les idées principales de l'algorithme de Ford et Fulkerson en prenant pour exemple le graphe ci-dessous.
Remarque : Le flot nul est réalisable
Lorsque les capacités inférieures sont toutes égales à 0, faire passer un flot nul par tous les arcs est une solution réalisable pour le problème de flot maximum puisque les contraintes de capacité sur les arcs et les contraintes de conservation du flot en chaque point sont toutes respectées.
Initialisation par un flot nul dans tous les arcs.
Le schéma suivant représente le flot nul pour l'exemple considéré. Le premier chiffre sur chaque arc représente le flot et le deuxième chiffre représente la capacité de l'arc.
Remarque : Utilisation des chemins pour augmenter le flot conservatif
Quand tous les flots sont nuls, on conserve un flot conservatif réalisable en faisant passer un flot positif sur tous les arcs d'un chemin qui va de la source s (ici 0) au puit t (ici 8) à condition de ne pas dépasser la plus petite capacité d'arc de ce chemin.
Placement de flots positifs sur un ou plusieurs chemins
Par exemple ici, on peut faire passer
un flot d'au plus une unité sur le chemin (0, 1, 4, 7, 8)
ou
un flot d'au plus 4 sur le chemin (0, 3, 6, 5, 8)
ou
un flot d'au plus 8 sur le chemin (0, 2, 5, 8)
ou
un flot d'au plus une unité sur le chemin (0, 3, 6, 8)
etc.
Mais on ne peut pas utiliser tous ces chemins simultanément.
Par exemple, comme les chemins (0, 3, 6, 5, 8) et (0, 2, 5, 8) ont l'arc (5, 8) en commun, on ne peut pas dépasser un flot de 8 sur cet arc.
Par contre, les chemins (0, 1, 4, 7, 8), (0, 2, 5, 8) et (0, 3, 6, 8) n'ont aucun arc en commun et on peut donc mettre le maximum de flot simultanément sur ces trois chemins.
Sur le graphe ci-dessus, nous avons mis le maximum de flot sur les trois chemins compatibles trouvés qui partent de la source.
Nous avons colorié en rouge les arcs saturés, c'est-à-dire ceux sur lesquels on ne peut plus augmenter le flot.
Utilisation des capacités restantes pour augmenter les flots en utilisant les chemins
On voit sur le dessin ci-dessus qu'il existe encore des chemins constitués d'arcs non saturés qui vont de la source au puits, on peut donc encore augmenter le flot à condition, pour les arcs où passent déjà du flot, de ne pas ajouter plus de flot dans un arc que la capacité restante.
Par exemple, on peut ajouter un flot de une unité sur le chemin (0, 3, 6, 5, 7, 8).
On peut noter sur l'exemple ci-dessus que tous les chemins qui vont de la source au puits ont au minimum un arc saturé.
On ne peut plus donc augmenter le flot en utilisant des chemins.
Le flot obtenu est de 11 qui sort de la source et qui entre dans le puits.
Néanmoins, il n'est pas certain que ce flot soit maximal, car il se peut qu'en choisissant autrement les flots sur les chemins, nous puissions faire encore mieux.
Il faut donc éventuellement remettre en cause les quantités qui passent sur certains arcs en les diminuant, de manière à pouvoir augmenter les flots sur d'autres arcs, tout en conservant un flot conservatif, c'est ce que nous allons faire en utilisant des chaînes améliorantes.
Définition : Chaîne améliorante
Dans un problème de flot conservatif, une chaîne améliorante est
une chaîne,
qui commence par un arc qui a pour origine la source s,
qui se termine par un arc qui a pour extrémité le puits t,
et telle que pour tout (x,y) arête de la chaîne,
si l'arc correspondant va de x à y alors F(x,y)<C(x,y), c'est un arc avant non saturé,
si l'arc correspondant va de y a x alors F(y,x)>0, c'est un arc arrière à flux strictement positif.
Notations
Soit D(x,y) =
C(x,y)-F(x,y) si (x,y) est un arc avant non saturé
F(y,x) si (y,x) est un arc arrière strictement positif.
On note Δ la plus grande valeur de D(x,y) pour toute arête (x,y) d'une chaîne améliorante.
Fondamental : Utilisation d'une chaîne améliorante
Sur une chaîne améliorante,
on conserve un flot conservatif en augmentant les flots de Δ sur tout arc avant non saturé et en diminuant les flots de Δ sur tout arc arrière à flux strictement positif.
Preuve de maintien d'un flot conservatif
Considérons un point quelconque x de la chaîne améliorante différent de la source et du puits,
quatre cas peuvent se présenter,
1) x est précédé et suivi d'un arc avant non saturé et on ajoute Δ sur les deux arcs, le flot conservatif précédemment reste conservatif,
2) x est précédé et suivi d'un arc arrière à flux strictement positif et on soustrait Δ sur les deux arcs, le flot conservatif précédemment reste conservatif,
3) x est précédé d'un arc avant non saturé (qui arrive en x) et suivi d'un arc arrière à flux strictement positif (qui arrive en x), on ajoute Δ sur un arc qui arrive en x et on soustrait Δ sur un autre arc qui arrive en x, le flot précédemment conservatif reste conservatif,
4) x est précédé d'un arc arrière à flux strictement positif (qui part de x) et suivi d'un arc avant non saturé (qui part de x), on soustrait Δ sur un arc qui part de x et on ajoute Δ sur un autre arc qui part de x, le flot précédemment conservatif reste conservatif.
Le schéma ci-dessus représente schématiquement une chaîne améliorante allant de la source au puits.
Le cas 1) correspond aux points x1 et x5.
Le cas 2) correspond au point x3.
Le cas 3) correspond au point x2.
Le cas 4) correspond au point x4.
Utilisation d'une chaîne améliorante sur le graphe exemple
La chaîne (0, 3, 6, 5, *2, 1, 4, 7, 8) est une chaîne améliorante où les arcs "avant" ne sont pas saturés et les arcs "arrière" (ici un seul indiqué par une étoile dans la description de la chaîne) ont un flux strictement positif.
La plus petite valeur que l'on puisse ajouter sur les arcs "avant" et/ou soustraire sur les arcs "arrière" est de 2.
L'amélioration correspondante a été effectuée sur le graphe ci-dessous.
Fondamental : Théorème d'optimalité
Un flot est maximal s'il n'existe plus de chaîne améliorante.
Sur notre exemple, les trois arcs qui sortent de la source sont tous les trois saturés. Il n'existe donc plus de chaîne améliorante et le flot de 13 est maximal.
RECHERCHE D'UNE COUPE MINIMALE
Pour trouver une coupe minimale à partir d'un flot maximal, il faut trouver un ensemble d'arcs dont la capacité totale est minimale et qui sont responsables du fait que l'on ne peut plus augmenter le flot.
Pour trouver une coupe minimale, on va donc chercher à construire des chaînes améliorantes en partant par exemple de la source (on peut aussi partir du puits).
On met dans un ensemble X' tous les points que l'on peut atteindre par une chaîne améliorante en partant de la source (en utilisant des arcs avant non saturés ou des arcs arrière à flux non nul).
Si t entre dans X', c'est que l'on a trouvé une chaîne améliorante et le flot n'était pas maximal.
Si on n'arrive plus à trouver de nouveaux points à ajouter à X' et que le point t n'est pas dans X', c'est que le flot est maximal et dans ce cas, les arcs qui vont d'un point de X' à un point de X-X' constitue une coupe minimale.
Remarque :
Une coupe minimale constitue un goulet d'étranglement au réseau de transport.
Il est absolument NÉCESSAIRE d'augmenter la capacité d'au minimum un arc de la coupe minimale pour pouvoir augmenter le flot maximal, mais cette condition n'est pas toujours SUFFISANTE, c'est le cas en particulier lorsque le réseau de transport contient deux coupes qui n'ont aucun arc en commun.
La condition est SUFFISANTE lorsque toutes les coupes ont un arc en commun.
Remarque :
Puisqu'il n'y a pas unicité de la coupe minimale, on peut trouver des coupes différentes en partant de la source et en partant du puits.
Il est à noter que s'il y a plus de deux coupes minimales, le procédé décrit ci-dessus ne permet de n'en trouver que 2.
Coupe minimale correspondant au flot maximal sur notre exemple
Comme tous les arcs qui partent de la source sont tous saturés, nous avons ici une coupe très simple avec X'={s} et X-X'=X-{s}.
On trouverait la même coupe en partant du puits.
Dans le général, X' ou X-X' ne sont pas réduits à un seul point et le goulet d'étranglement est plus difficile à mettre en évidence.
Attention :
L'algorithme de Ford et Fulkerson ne fait qu'utiliser toutes les notions que nous avons présenté dans cette section.
La seule différence dans la section suivante est que l'algorithme de Ford de Fulkerson y est mis en œuvre techniquement en utilisant des techniques de marquage pour trouver les chaînes améliorantes, techniques analogues à celles présentées dans le module de base de théorie des graphes pour les problèmes de cheminements.
On aurait pu utiliser une technique de pile comme dans l'algorithme utilisé pour trouver les plus courts chemins à partir d'un point donné.
Pour changer et parce que l'on obtient en premier les chemins (ou les chaînes) les plus court(e)s en nombre d'arcs, nous utilisons ici une file à la place d'une pile.
