Problème de flot maximum
Un article de Wikipédia, l'encyclopédie libre.
Le problème de flot maximum consiste a trouver un flot réalisable depuis une source unique et vers un puits unique graphe de flot qui soit maximum [1]. Quelque fois le problème renvoie simplement à la question de trouver la valeur de ce flot. Le problème du flot maximum peut être vu comme un cas particulier de plusieurs autres problèmes de flots dans les réseaux, comme le flot mutli-commodites. Le s-t flot maximum (depuis la source s vers le puits t) est égal a la s-t coupe minimale du graphe, comme l'indique le Théorème flot-max/coupe-min.
[modifier] Solutions
Etant donne un graphe orienté G(V,E), ou chaque arète u,v a une capacité c(u,v), on cherche un flot maximum f depuis la source s vers la source t, sous contraintes de capacité. Il y a plusieurs façons de résoudre le problème:
| Méthode | Complexité | Description |
|---|---|---|
| Programmation lineaire | Les contraintes sont données par flot admissible. On maximise  . |
|
| Algorithme de Ford-Fulkerson |  |
Tant qu'il existe un chemin entre la source et le puits dans le graphe résiduel, envoyer le minimum des capacités résiduelles sur ce chemin. |
| Algorithme de Edmonds-Karp | O(VE2) | Une spécialisation de Ford-Fulkerson, trouver un chemin augmentant avec une recherche en largeur d'abord. |
| Algorithme de flot bloquant de Dinitz | O(V2E) | A chaque phase l'algorithme construit un graphe en couches avec une recherche en profondeur d'abord sur le graphe résiduel. Le flot maximum dans le graphe en couche peut etre calcule en temps O(VE), et le nombre maximum de phase est de V − 1. |
| Algorithme de flot maximum par poussage/re-etiquettage | O(V2E) | Cet algorithme maintient un préflot, ie. une fonction de flot avec une possibilité d'excès dans les sommets. l'algorithme fonctionne tant qu'il existe un sommet avec un excès strictement positif, appele sommet actif du graphe. L'opération de poussage augmente le flot sur une arête résiduelle, et une fonction de hauteur contrôle sur les sommets contrôle quelles arêtes résiduelles doivent être poussées. Cette fonction est changée avec la fonction d'étiquettage. Les définitions de ces opérations garantissent que le flot resultant est un flot maximum. |
| Poussage/re-étiquettage avec règle de selection des sommets par FIFO | O(V3) | Variante qui sélectionne toujours le sommet le plus actif formellement, et fait les opérations jusqu'à ce que l'excès soit positif ou qu'il existe des arêtes résiduelles admissibles depuis ce sommet. |
| Algorithme de flot bloquant de Dinitz avec arbre dynamique[2] | O(VElog(V)) | La structure d'arbre dynamique accelère le calcul de flot maximum dans le graphe en couche pour obtenir O(Elog(V)) par phase. |
| Poussage/re-étiquettage avec usage des arbres dynamiques[3] | O(VElog(V2 / E)) | L'algorithme construit des arbres de taille limitée sur le graphe résiduel en considérant la fonction de hauteur, ces arbres fournissent des opérations de poussage multi-niveau. |
| algorithme de flot bloquant binaire[4] |  |
La valeur U correspond à la capacité maximum du réseau. |
Pour une liste plus complète, voir [1].
[modifier] Références bibliographiques
- (en) Cet article est partiellement ou en totalité issu d’une traduction de l’article de Wikipédia en anglais intitulé « Maximum flow problem ».
- ↑ a b Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001). "26", Introduction to Algorithms, second edition, MIT Press and McGraw-Hill, 643–700. ISBN 0-262-53196-8.
- ↑ Daniel D. Sleator and Robert E. Tarjan, « A data structure for dynamic trees », dans Journal of Computer and System Sciences, 26, p. 362–391 [texte intégral]
- ↑ Andrew V. Goldberg and Robert E. Tarjan, « A new approach to the maximum-flow problem », dans Journal of the ACM, 35, p. 921–940
- ↑ Andrew V. Goldberg and S. Rao, « Beyond the flow decomposition barrier », dans J. assoc. Comput. Mach., 45, p. 753–782
