ArithmétiqueMéthode · Glossaire
algorithme de Ford-Fulkerson
L'algorithme de Ford-Fulkerson est le premier algorithme conçu spécifiquement pour résoudre le problème du flot maximal dans un réseau. Proposé par Lester Randolph Ford Jr. et Delbert Ray Fulkerson, il consiste à rechercher itérativement des chemins augmentants dans le réseau — c'est-à-dire des chemins reliant la source au puits le long desquels il est encore possible d'augmenter le flot — et à augmenter le flot sur ces chemins jusqu'à ce qu'aucun chemin augmentant n'existe plus. Le théorème max-flot min-coupe, également dû à Ford et Fulkerson, établit que la valeur du flot maximal est égale à la capacité de la coupe minimale du réseau.
Sommaire
Ce que vous allez apprendre
- Identifier un chemin augmentant dans le réseau résiduel.
- Calculer trois augmentations sur un réseau de quatre sommets.
- Certifier la valeur 10 par une coupe de même capacité.
- Reconnaître les limites liées aux arcs inverses et au choix des chemins.
En clair
Imaginez de l'eau qui doit aller d'une source à un puits par plusieurs conduites. Chaque conduite impose un débit maximal. Ford-Fulkerson cherche un trajet encore disponible, y fait passer autant d'eau que le permet sa conduite la plus étroite, puis recommence.
Le calcul ne s'arrête pas lorsqu'un trajet particulier est plein, mais lorsqu'il n'existe plus aucun trajet utilisable de la source au puits. Les possibilités de retour gardées en mémoire permettent aussi de corriger un choix antérieur.
Définition
Ford-Fulkerson est une méthode de calcul d'un flot maximal dans un réseau orienté muni d'une source et d'un puits. Chaque arc reliant un sommet u à un sommet v possède une capacité c(u, v). Le flot f(u, v) respecte la capacité de l'arc : . En chaque sommet autre que la source et le puits, le flot total entrant est égal au flot total sortant.
À partir d'un flot nul, la méthode construit le réseau résiduel. Un arc direct y indique la capacité encore libre ; un arc inverse indique le flot qui peut être annulé pour réorienter un choix précédent. Un chemin augmentant relie la source au puits dans ce réseau. Sa capacité résiduelle, appelée goulot, est le minimum des capacités résiduelles rencontrées.
On ajoute ce goulot le long du chemin, puis on actualise les arcs directs et inverses. Quand aucun chemin augmentant ne subsiste, le flot obtenu est maximal. Le théorème max-flot min-coupe certifie alors sa valeur : elle égale la capacité d'une coupe minimale séparant la source du puits.
Le principe
Dans un réseau orienté à capacités non négatives, partez d'un flot réalisable, par exemple le flot nul.
1. Construisez le réseau résiduel.
2. Choisissez un chemin de la source au puits dont chaque arc a une capacité résiduelle strictement positive.
3. Augmentez le flot du minimum de ces capacités et actualisez les arcs inverses.
4. Répétez jusqu'à l'absence de chemin augmentant. Le flot est alors maximal.
1. Construisez le réseau résiduel.
2. Choisissez un chemin de la source au puits dont chaque arc a une capacité résiduelle strictement positive.
3. Augmentez le flot du minimum de ces capacités et actualisez les arcs inverses.
4. Répétez jusqu'à l'absence de chemin augmentant. Le flot est alors maximal.
Quand l'utiliser
La méthode demande un réseau orienté fini, une source, un puits et une capacité non négative pour chaque arc. Le flot initial doit respecter les capacités et la conservation aux sommets intermédiaires. Avec des capacités entières et un flot initial entier, notamment le flot nul, chaque augmentation non nulle vaut au moins 1 : le processus termine donc après un nombre fini d'augmentations.
Un plan de rues sans sens de circulation, sans point de départ ou sans destination ne fournit pas directement ces données. Il faut d'abord orienter les liaisons et définir source, puits et capacités. Si les capacités sont irrationnelles, la règle arbitraire de choix des chemins ne garantit plus la terminaison ; une stratégie spécifiée, comme celle d'Edmonds-Karp, évite ce blocage.
Un exemple, pas à pas
Le réseau comporte la source S, les sommets A et B, puis le puits T. Les capacités sont S→A : 7, S→B : 4, A→B : 3, A→T : 4 et B→T : 6. Le flot initial vaut 0 sur chaque arc.
1. Sur le chemin S→A→T, le goulot vaut min(7, 4) = 4. Le flot total devient 4.
2. Sur S→B→T, le goulot vaut min(4, 6) = 4. Le flot total atteint 8 et l'arc S→B est saturé.
3. Sur S→A→B→T, les capacités résiduelles sont 3, 3 et 2. Le goulot vaut donc 2, et le flot total atteint 10.
Aucun chemin augmentant ne subsiste. Pour contrôler le résultat, la coupe qui place S, A et B d'un côté et T de l'autre traverse A→T et B→T, de capacité totale 4 + 6 = 10. La figure synthétise le flot final et cette coupe qui certifie sa valeur maximale.
En pratique
Pour dimensionner un petit réseau de transport, on encode chaque liaison par une capacité et on calcule le volume total acheminable. Si les liaisons n'ont pas de sens imposé, il faut d'abord choisir un modèle orienté adapté.
Pour localiser un goulot d'étranglement, on lit la coupe minimale obtenue avec le flot maximal. Augmenter une liaison hors de cette coupe ne change pas nécessairement le débit total ; les arcs de la coupe sont les premiers à examiner.
Pour un calcul reproductible sur un grand graphe, on précise la façon de choisir les chemins. La variante d'Edmonds-Karp, qui prend un chemin comportant le moins d'arcs, est préférable à un choix arbitraire lorsque le temps de calcul doit être garanti.
À ne pas confondre
Ford-Fulkerson et théorème max-flot min-coupe. Le premier est une procédure qui construit un flot ; le second affirme l'égalité entre la meilleure valeur de flot et la plus petite capacité de coupe. Dans l'exemple, les augmentations calculent 10, tandis que la coupe de capacité 10 certifie l'optimalité.
Chemin du graphe et chemin augmentant. Un chemin dessiné de S à T n'est augmentant que si tous ses arcs ont une capacité résiduelle positive. Après saturation de S→B, le trajet S→B→T existe encore dans le graphe représenté, mais ne peut plus recevoir de flot.
Ford-Fulkerson et Edmonds-Karp. Ford-Fulkerson laisse libre le choix du chemin augmentant. Edmonds-Karp fixe ce choix en prenant un chemin avec le moins d'arcs dans le réseau résiduel. Lorsqu'elles terminent, deux exécutions arbitraires peuvent donc suivre des étapes différentes tout en atteignant le même flot maximal.
Limites et pièges
Oublier les arcs inverses. Un choix précoce peut envoyer du flot sur un arc qu'il faudra ensuite libérer. Si le réseau résiduel ne contient que les places libres vers l'avant, le calcul peut s'arrêter trop tôt. Il faut ajouter une capacité inverse égale au flot annulable.
Capacités irrationnelles. Avec un choix arbitraire des chemins, les augmentations peuvent former une suite infinie et ne jamais atteindre le maximum. Des capacités entières écartent ce cas : chaque augmentation vaut au moins 1. Pour des capacités réelles générales, on emploie une règle de choix garantissant la terminaison.
Confondre saturation locale et optimalité globale. Un arc ou un chemin saturé ne suffit pas à conclure. Dans l'exemple, S→B est plein lorsque le flot vaut 8, mais le chemin S→A→B→T ajoute encore 2. Le bon test est l'absence de tout chemin augmentant.
Choix de chemins coûteux. Avec des capacités entières et un flot maximal de valeur F, la version arbitraire peut effectuer jusqu'à F augmentations. Lorsque F est grand, il faut imposer une stratégie de parcours, par exemple celle d'Edmonds-Karp, plutôt que juger l'algorithme sur le seul nombre de sommets.
Pour aller plus loin
algorithme — Pour replacer Ford-Fulkerson dans la notion générale de procédure finie, ordonnée et exécutable.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres