Un réseau de conduites doit transporter le plus de marchandises possible entre un dépôt et un terminal. Chaque liaison limite la quantité qu'elle peut recevoir. Choisir un trajet bon marché ne répond pas à cette question : plusieurs trajets peuvent fonctionner simultanément et partager des passages limités. Les flots permettent de répartir ce transport, puis de prouver qu'aucune répartition meilleure n'existe.
La conservation interdit de créer de la marchandise au milieu du réseau. Elle autorise en revanche à partager une arrivée entre plusieurs sorties ou à réunir plusieurs arrivées. La valeur du flot est la quantité nette qui quitte S, égale à celle qui arrive à T. Dans notre exemple, aucun arc n'entre dans S et aucun ne sort de T, ce qui simplifie sa lecture.
La capacité est une borne, pas un poids à additionner le long d'un trajet. Si un parcours utilise plusieurs conduites en série, le passage le plus limité détermine la quantité supplémentaire qu'il peut transporter. Nous utilisons des unités de débit abstraites et identiques sur toutes les liaisons. Mélanger des unités de temps différentes rendrait le résultat dépourvu de sens.
L'arc inverse ne représente pas forcément une conduite physique permettant de faire circuler des colis en arrière. C'est un outil de calcul : il permet de retirer une décision ancienne pour réaffecter la marchandise autrement. Sans ce mécanisme, un premier choix maladroit pourrait bloquer définitivement le programme alors qu'une meilleure répartition existe.
Sur une sortie résiduelle directe, on augmente le flot d'origine. Sur une sortie inverse, on le diminue. À chaque sommet intermédiaire, les modifications conservent l'équilibre. Le goulot empêche de dépasser une capacité ou d'annuler davantage de flot qu'il n'en existe. Il faut mettre à jour les deux sens résiduels après chaque augmentation.
Initialiser tous les flots à zéro
Construire les capacités résiduelles
Tant qu'un chemin résiduel de S à T existe :
delta ← minimum des capacités résiduelles du chemin
Pour chaque arc résiduel u → v du chemin :
diminuer sa capacité résiduelle de delta
augmenter celle de son inverse de delta
ajouter delta à la valeur du flot
Conserver les sommets encore accessibles depuis SFord-Fulkerson désigne ce mécanisme général ; il ne fixe pas une unique manière de chercher le chemin. Lorsque l'on utilise BFS pour choisir un chemin ayant le moins d'arcs résiduels, on obtient la variante d'Edmonds-Karp. Cette précision importe pour les garanties de temps et de terminaison.
Si les capacités sont entières, chaque augmentation ajoute au moins une unité, et la valeur reste bornée par les capacités sortant de S. La méthode termine donc. Avec des capacités réelles arbitraires et de mauvais choix de chemins, la méthode générale ne garantit pas cette terminaison. Edmonds-Karp dispose d'une borne polynomiale indépendante de la valeur numérique du flot optimal.
Les capacités sont SA : 10, SB : 5, AB : 4, AT : 6 et BT : 10. Nous choisissons les chemins par BFS avec un ordre alphabétique pour rendre la trace reproductible. Le premier chemin S–A–T accepte 6 unités. Le deuxième S–B–T en accepte 5. Il reste ensuite le chemin S–A–B–T, qui accepte 4 unités.
| Chemin | Goulot | Valeur totale |
|---|---|---|
| S → A → T | 6 | 6 |
| S → B → T | 5 | 11 |
| S → A → B → T | 4 | 15 |
La valeur totale atteint 15. Les quantités finales sont SA : 10, SB : 5, AB : 4, AT : 6 et BT : 9. Au sommet A, les 10 unités reçues se répartissent en 4 vers B et 6 vers T. Au sommet B, les arrivées de 5 et de 4 donnent les 9 unités envoyées vers T.
BT garde une unité de capacité inutilisée. Cela ne prouve pas qu'on peut encore augmenter le flot : il faut pouvoir acheminer une unité supplémentaire jusqu'à B depuis S, en respectant toutes les contraintes. Or les deux sorties de S sont déjà saturées. Une marge locale n'est pas une possibilité globale de transport.
Considérons un autre réseau où SA, SB, AB, AT et BT possèdent chacun la capacité 1. Supposons que le premier chemin choisi soit S–A–B–T. Il transporte une unité, mais occupe AB et BT. Un algorithme qui n'examine que les marges directes pourrait croire la situation bloquée.
Le réseau résiduel contient pourtant le chemin S–B–A–T. Son passage B → A est l'inverse de AB. L'augmentation annule donc le flot sur AB et ajoute du flot sur SB et AT. On obtient finalement une unité sur S–A–T et une sur S–B–T, soit une valeur totale de 2.
Le calcul ne transporte pas réellement une marchandise à rebours pour gagner une unité. Il remplace une répartition provisoire par une autre. Lorsqu'un graphe possède déjà des arcs physiques dans les deux sens, l'implantation doit distinguer chaque arc d'origine de son inverse résiduel associé. Des enregistrements d'arcs appariés évitent les confusions entre annulation et transport opposé.
La borne vient de la conservation : toute quantité nette quittant le groupe de S doit franchir sa frontière. Les arcs sortants limitent cette quantité. Les retours éventuels vers le groupe ne permettent pas de dépasser la borne ; ils diminuent le passage net. Une coupe fournit donc un certificat supérieur indépendant de la manière dont le flot a été calculé.
Quand aucun chemin augmentant n'existe, prenons les sommets encore accessibles depuis S dans le résiduel. Les arcs sortant de cet ensemble sont saturés ; les arcs y entrant ne transportent aucun flot positif qui permettrait un retour résiduel. La valeur du flot égale alors la capacité de cette coupe. La borne est atteinte : le flot est maximal et la coupe minimale.
Dans notre exemple principal, seul S reste accessible. La coupe porte SA et SB, de capacité totale 10 + 5 = 15. Le flot de valeur 15 atteint cette limite. Même si les deux arcs arrivant à T offrent ensemble une capacité 16, l'entrée du réseau limite le transport à 15.
Pour des capacités entières, une borne simple de Ford-Fulkerson est O(mF), où F est la valeur optimale, avec une recherche linéaire dans le résiduel par augmentation. Cette borne dépend de la valeur des capacités. Edmonds-Karp coûte O(nm²) avec des listes résiduelles efficaces. Le stockage résiduel demande O(n + m) de mémoire.
Pour vérifier un résultat, contrôlez les bornes sur chaque arc, la conservation à chaque sommet intermédiaire et l'égalité entre la valeur obtenue et une coupe de même capacité. Sur notre petit réseau, toutes les coupes ont aussi été énumérées indépendamment. Sur un grand réseau, le certificat flot–coupe évite cette énumération exhaustive.
Pourquoi la dernière augmentation principale S–A–B–T vaut-elle 4 ?
Après les deux premières augmentations, SA garde 4 unités, AB en offre 4 et BT en garde 5. Le minimum est donc 4. Envoyer davantage dépasserait au moins une des capacités du chemin.
Vérifiez l'équilibre final au sommet B.
B reçoit 5 unités depuis S et 4 depuis A, soit 9. Il envoie 9 unités vers T. L'arrivée et la sortie sont égales, et BT respecte sa capacité 10. Une vérification locale complète la valeur globale du flot.
Dans le réseau de capacités unitaires, que signifie le passage résiduel B → A ?
Il retire l'unité provisoirement envoyée sur AB. Cette annulation permet de rediriger les flux vers AT et BT sans violer la conservation. Elle ne suppose pas l'existence d'une conduite physique de B vers A.
Donnez un certificat du maximum 15 dans le réseau principal.
La coupe isolant S possède les arcs SA et SB, de capacités 10 et 5. Tout flot est donc au plus 15. Le flot construit atteint 15 en respectant les contraintes : cette égalité prouve sa maximalité.
Questions / Réponses
Ajouter un commentaire