algorithme d'obtention d'un flot

Imaginez un réseau de conduites orientées entre une source et un point d’arrivée. Chaque conduite possède une capacité, et l’algorithme cherche comment faire circuler une quantité compatible avec toutes ces limites. Il augmente progressivement le flot sur des chemins encore disponibles, puis s’arrête lorsqu’aucun chemin de la source vers l’arrivée ne peut plus être utilisé. Le résultat indique à la fois la circulation obtenue et, selon l’objectif choisi, un flot maximal.

Un réseau de flot est un graphe orienté muni d’une capacité non négative sur chaque arc. On distingue une source s, sans arc entrant, où le flot entre dans le réseau, et un puits t, où il en sort. Un flot attribue une quantité à chaque arc : cette quantité est non négative, ne dépasse pas la capacité de l’arc et vérifie la conservation aux autres sommets. Autrement dit, à chaque sommet intermédiaire, le débit entrant est égal au débit sortant.

L’algorithme d’obtention d’un flot construit cette attribution par augmentations successives. Il choisit un chemin de s à t dans lequel chaque arc conserve une capacité disponible, puis ajoute sur ce chemin la plus petite capacité restante. Cette valeur est le goulot d’étranglement du chemin. Les méthodes classiques, comme celle des chemins augmentants, s’arrêtent quand aucun tel chemin ne subsiste. La valeur du flot est alors la quantité totale sortie par s, et la version complète de la méthode fournit un flot maximal lorsque les capacités et les règles de recherche respectent ses hypothèses.

Pour obtenir un flot par chemins augmentants, on part d’un flot nul. À chaque étape, on choisit un chemin orienté de la source s au puits t dont chaque arc a une capacité résiduelle positive. On ajoute au flot la plus petite de ces capacités résiduelles, puis on actualise toutes les capacités restantes. La procédure s’arrête lorsqu’aucun chemin augmentant n’existe. Avec des capacités entières et une recherche qui termine, elle atteint un flot maximal.

La méthode s’applique à un réseau orienté, avec une source, un puits et une capacité connue pour chaque arc. Les capacités doivent être non négatives ; une capacité nulle ne permet aucune augmentation. Le flot doit respecter la conservation aux sommets qui ne sont ni source ni puits. La quantité obtenue est mesurée dans la même unité que les capacités.

Un chemin augmentant de la source au puits dans le graphe résiduel est nécessaire pour augmenter le flot. La recherche doit prendre en compte les arcs directs encore disponibles et les arcs inverses, qui permettent d’annuler ou de réacheminer une partie du flot déjà posé. Si aucun chemin augmentant ne subsiste dans ce graphe résiduel, la méthode ne peut plus augmenter la valeur courante. Dans ce cas, il faut conserver le flot obtenu et, si le réseau ne représente pas correctement le problème, revoir les arcs ou employer un modèle avec plusieurs sources et plusieurs puits.

Considérons un réseau orienté de source s vers puits t. Les capacités sont s→a : 4, s→b : 3, a→b : 1, a→t : 2 et b→t : 4. On cherche un flot construit par chemins augmentants.

Premier chemin : s→a→t. Ses capacités restantes valent 4 et 2 ; le goulot vaut donc 2. Après l’augmentation, le flot sur ces deux arcs vaut 2 et la valeur courante vaut 2.
Deuxième chemin : s→b→t. Les capacités restantes valent 3 et 4 ; le goulot vaut 3. La valeur courante devient 5.
Troisième chemin : s→a→b→t. Les capacités restantes valent 2, 1 et 1 ; le goulot vaut 1. La valeur courante devient 6.

Le flot final vaut 6 unités. Les arcs s→a et b→t portent respectivement 3 et 4 unités, tandis que a→t porte 2 et a→b porte 1. Le contrôle est immédiat : la source envoie 3 + 3 = 6 unités, le puits reçoit 2 + 4 = 6, et chaque sommet intermédiaire conserve le débit.

Dans un réseau de transport, les sommets représentent des lieux et les arcs des liaisons orientées. Les capacités peuvent représenter des véhicules par heure. L’algorithme répartit alors le trafic sans dépasser une liaison ; une méthode de flot maximal convient si l’objectif est le volume total entre un départ et une arrivée.

En traitement du signal, un réseau peut modéliser des dépendances ou des canaux de transmission. Le calcul sert à déterminer une circulation admissible lorsque chaque liaison impose une limite. Si le coût de chaque liaison compte aussi, un algorithme de flot de coût minimal est une alternative plus adaptée.

Un flot admissible n’est pas nécessairement un flot maximal. Le premier respecte les capacités et la conservation ; le second est admissible et sa valeur ne peut plus être augmentée dans le réseau. Dans l’exemple conducteur, un flot de 5 unités après les deux premiers chemins est admissible, mais le troisième chemin permet encore d’atteindre 6.

Un chemin augmentant n’est pas un chemin quelconque du graphe initial. Il doit utiliser une capacité résiduelle positive, éventuellement créée par la possibilité de diminuer un flot déjà posé. Cette distinction est testable en examinant le réseau résiduel après chaque augmentation.

Un réseau sans chemin de s à t donne un flot maximal de 0, même si certains arcs ont de grandes capacités. Le symptôme est une source séparée du puits ; il faut vérifier la connexité orientée avant d’interpréter le résultat.

Une recherche qui s’arrête après un chemin ne prouve pas la maximalité. Dans l’exemple, la valeur 2 obtenue par s→a→t n’est qu’une valeur intermédiaire. Il faut explorer le réseau résiduel jusqu’à l’absence complète de chemin augmentant.

Avec des capacités réelles, certaines variantes de choix des chemins peuvent demander une analyse de terminaison plus fine. Pour une implémentation générale, il faut choisir une méthode connue, gérer les capacités résiduelles et vérifier la conservation plutôt que supposer que tout parcours produit automatiquement un résultat maximal.

Le problème du flot maximal relie la construction algorithmique à une question de séparation : une coupe du réseau partage les sommets entre la source et le puits, et sa capacité additionne les capacités des arcs qui sortent de la partie contenant s. Le théorème flot maximal–coupe minimale explique pourquoi une valeur ne peut dépasser la capacité d’une telle coupe et caractérise l’optimalité lorsque les deux valeurs coïncident.