Problème de flot maximum

Problème de flot maximum: Un exemple de graphe de flot avec un flot maximum. la source est $s$ , et le puits $t$ . Les nombres indiquent le flot et la capacité.

Le problème de flot maximum consiste à trouver un flot réalisable depuis une source unique et vers un puits unique graphe de flot qui soit maximum^[1]. Quelquefois le problème répond 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 multi-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.

Solutions

Étant donné 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 le puits $t$ , sous contraintes de capacité. Il y a plusieurs façons de résoudre le problème:

Méthode Complexité Description

Programmation linéaire Les contraintes sont données par flot admissible, où on considère comme admissible un flot qui n'excède pas la capacité d'un arc. On maximise $\sum_{v \in V} f(s,v)$ .

Algorithme de Ford-Fulkerson $\scriptstyle O(E \cdot \mathit{flotmax})$ 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 (V E 2)$ Une spécialisation de Ford-Fulkerson, trouver un chemin augmentant avec une recherche en largeur d'abord.

Algorithme de flot bloquant de Dinitz $O (V 2 E)$ 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 être calcule en temps $O (V E)$ , et le nombre maximum de phase est de $V - 1$ .

Algorithme de flot maximum par poussage/re-étiquetage $O (V 2 E)$ 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'étiquetage. Les définitions de ces opérations garantissent que le flot resultant est un flot maximum.

Poussage/re-étiquetage avec règle de sélection des sommets par FIFO $O (V 3)$ 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 (V E log(V))$ La structure d'arbre dynamique accelère le calcul de flot maximum dans le graphe en couche pour obtenir $O (E log(V))$ par phase.

Poussage/re-étiquetage avec usage des arbres dynamiques^[3] $O (V E log(V 2 / 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] $\scriptscriptstyle O(E\min(V^{2/3},\sqrt{E})\log(V^2/E)\log{U})$ La valeur U correspond à la capacité maximum du réseau.

Pour une liste plus complète, voir^[1].

Références bibliographiques

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Maximum flow problem » (voir la liste des auteurs)

↑ ^{a et b} (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, Cambridge, MIT Press and McGraw-Hill, 2001, second edition^e éd., relié (ISBN 978-0-262-53196-2) (LCCN 2001031277), « 26 », p. 643–700

↑ Daniel D. Sleator and Robert E. Tarjan, « A data structure for dynamic trees », dans Journal of Computer and System Sciences, vol. 26, 1983, p. 362–391 (ISSN 0022-0000) [texte intégral, lien DOI]

↑ Andrew V. Goldberg and Robert E. Tarjan, « A new approach to the maximum-flow problem », dans Journal of the ACM, ACM Press, vol. 35, 1988, p. 921–940 (ISSN 0004-5411) [lien DOI]

↑ Andrew V. Goldberg and S. Rao, « Beyond the flow decomposition barrier », dans J. assoc. Comput. Mach., vol. 45, 1998, p. 753–782 [lien DOI]

Lien externe

Bibliothèque C++ Lemon avec plusieurs implémentations du flot maximum

Portail des mathématiques

Catégorie :
Algorithme de la théorie des graphes

Méthode	Complexité	Description
Programmation linéaire		Les contraintes sont données par flot admissible, où on considère comme admissible un flot qui n'excède pas la capacité d'un arc. On maximise $\sum_{v \in V} f(s,v)$ .
Algorithme de Ford-Fulkerson	$\scriptstyle O(E \cdot \mathit{flotmax})$	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 (V E 2)$	Une spécialisation de Ford-Fulkerson, trouver un chemin augmentant avec une recherche en largeur d'abord.
Algorithme de flot bloquant de Dinitz	$O (V 2 E)$	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 être calcule en temps $O (V E)$ , et le nombre maximum de phase est de $V - 1$ .
Algorithme de flot maximum par poussage/re-étiquetage	$O (V 2 E)$	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'étiquetage. Les définitions de ces opérations garantissent que le flot resultant est un flot maximum.
Poussage/re-étiquetage avec règle de sélection des sommets par FIFO	$O (V 3)$	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 (V E log(V))$	La structure d'arbre dynamique accelère le calcul de flot maximum dans le graphe en couche pour obtenir $O (E log(V))$ par phase.
Poussage/re-étiquetage avec usage des arbres dynamiques^[3]	$O (V E log(V 2 / 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]	$\scriptscriptstyle O(E\min(V^{2/3},\sqrt{E})\log(V^2/E)\log{U})$	La valeur U correspond à la capacité maximum du réseau.

Contenu soumis à la licence CC-BY-SA. Source : Article Problème de flot maximum de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

Probleme de flot maximum — Problème de flot maximum Un exemple de graphe de flot avec un flot maximum. la source est s, et le puits t. Les nombres indiquent le flot et la capacite. Le problème de flot maximum consiste a trouver un flot réalisable depuis une source unique… … Wikipédia en Français
Flot admissible — Problème de flot maximum Un exemple de graphe de flot avec un flot maximum. la source est s, et le puits t. Les nombres indiquent le flot et la capacite. Le problème de flot maximum consiste a trouver un flot réalisable depuis une source unique… … Wikipédia en Français
Probleme de bin packing — Problème de bin packing Le problème de bin packing relève de la recherche opérationnelle et de l optimisation combinatoire. Il s agit de trouver le rangement le plus économique possible pour un ensemble d articles dans des boîtes. Le problème… … Wikipédia en Français
Problème de bin packing — Le problème de bin packing relève de la recherche opérationnelle et de l optimisation combinatoire. Il s agit de trouver le rangement le plus économique possible pour un ensemble d articles dans des boîtes. Le problème classique se définit en une … Wikipédia en Français
Theoreme flot-max/coupe-min — Théorème flot max/coupe min Le théorème flot max/coupe min est un théorème de la théorie des graphes. Il généralise le théorème de König et le théorème de Hall (dans les graphes bipartis) et le théorème de Menger (dans les graphes quelconques).… … Wikipédia en Français
Théorème flot-max/coupe-min — Le théorème flot max/coupe min est un théorème de la théorie des graphes. Il généralise le théorème de König et le théorème de Hall (dans les graphes bipartis) et le théorème de Menger (dans les graphes quelconques). Il révèle que le calcul d une … Wikipédia en Français
Bin packing problem — Problème de bin packing Le problème de bin packing relève de la recherche opérationnelle et de l optimisation combinatoire. Il s agit de trouver le rangement le plus économique possible pour un ensemble d articles dans des boîtes. Le problème… … Wikipédia en Français
Graphe (mathématiques) — Théorie des graphes Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… … Wikipédia en Français
Graphe (théorie des graphes) — Théorie des graphes Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… … Wikipédia en Français
Theorie des graphes — Théorie des graphes Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Problème de flot maximum

Solutions

Références bibliographiques

Lien externe

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Problème de flot maximum

Solutions

Références bibliographiques

Lien externe

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link