Que dit réellement le théorème de flot maximal/coupe minimale ?

Il stipule que la plus grande quantité de flot que l'on peut acheminer d'une source à un puits est égale à la plus petite capacité totale de tout ensemble d'arêtes dont la suppression déconnecte la source du puits. La coupe minimale agit comme le goulot d'étranglement qui limite le flot maximal.

Pourquoi la méthode de Ford-Fulkerson simple n'a-t-elle pas un temps d'exécution polynomial ?

Si les chemins augmentants sont mal choisis et que les capacités sont grandes (ou irrationnelles), le nombre d'augmentations peut être très élevé, voire ne pas se terminer. Le choix des chemins augmentants les plus courts (Edmonds-Karp) ou l'utilisation de flots bloquants (Dinic) borne le nombre d'augmentations et garantit un temps polynomial.

Algorithmes de flot maximal

Les algorithmes de flot maximal calculent la quantité maximale de flot pouvant être acheminée d'une source à un puits à travers un réseau capacitaire, un problème dont l'optimum est lié par dualité à la coupe minimale du réseau.

Trouver un sujet avec PaperMindBientôtFind papers & topics

Tools & resources

Télécharger les diapositives

Learn & explore

VidéoBientôt

Definition

Un réseau de flot est un graphe orienté avec des capacités d'arêtes, une source et un puits ; un algorithme de flot maximal trouve une affectation de flot aux arêtes, respectant les capacités et la conservation aux sommets intermédiaires, qui maximise le flot total de la source au puits.

Scope

Ce sujet aborde le problème de flot maximal et ses algorithmes : la méthode de Ford-Fulkerson avec les chemins augmentants, les améliorations d'Edmonds-Karp et de Dinic qui bornent le temps d'exécution, et le théorème de flot maximal/coupe minimale qui caractérise l'optimum. Il couvre également les réductions d'autres problèmes — l'appariement biparti, les chemins disjoints en sommets, la sélection de projets — au flot de réseau. Il exclut la programmation linéaire générale, dont le flot est un cas particulier.

Core questions

Comment un flot est-il défini et quelles contraintes doit-il satisfaire ?
Comment les chemins augmentants dans le graphe résiduel augmentent-ils le flot vers le maximum ?
Pourquoi le flot maximal est-il égal à la capacité de la coupe minimale ?
Comment les algorithmes d'Edmonds-Karp et de Dinic garantissent-ils un temps d'exécution polynomial ?
Comment l'appariement et d'autres problèmes sont-ils réduits au flot maximal ?

Key concepts

réseau de flot
capacité et conservation
chemin augmentant
graphe résiduel
théorème de flot maximal/coupe minimale
algorithme d'Edmonds-Karp
algorithme de Dinic
réduction à l'appariement biparti

Key theories

Max-flow min-cut theorem: La valeur d'un flot maximal d'une source à un puits est égale à la capacité minimale d'une coupe les séparant ; cette dualité, due à Ford et Fulkerson, certifie l'optimalité et relie le flot aux problèmes de connectivité et de partitionnement.
Augmenting paths and residual graphs: La méthode de Ford-Fulkerson augmente le flot en trouvant des chemins avec une capacité résiduelle dans le graphe résiduel ; le choix des chemins augmentants les plus courts (Edmonds-Karp) ou l'utilisation de graphes de niveaux et de flots bloquants (Dinic) garantit des temps polynomiaux.

Clinical relevance

Le flot de réseau est un outil de modélisation polyvalent : il résout les problèmes d'affectation bipartite et d'ordonnancement, calcule la connectivité et la fiabilité des réseaux, effectue la segmentation d'images via des coupes de graphes en vision par ordinateur, et sous-tend la logistique, la planification des transports et l'optimisation de la sélection de projets où les capacités et les goulots d'étranglement sont importants.

History

Ford et Fulkerson ont introduit le problème de flot maximal et le théorème de flot maximal/coupe minimale en 1956 lors de l'étude des réseaux de transport. Edmonds et Karp (1972) et, indépendamment, Dinic (1970) ont proposé les premiers algorithmes à temps polynomial, et les travaux ultérieurs ont constamment amélioré le temps d'exécution asymptotique du flot maximal.

Key figures

Lester Ford
Delbert Fulkerson
Jack Edmonds
Yefim Dinic

Seminal works

fordfulkerson1956
cormen2009

Frequently asked questions

Que dit réellement le théorème de flot maximal/coupe minimale ?: Il stipule que la plus grande quantité de flot que l'on peut acheminer d'une source à un puits est égale à la plus petite capacité totale de tout ensemble d'arêtes dont la suppression déconnecte la source du puits. La coupe minimale agit comme le goulot d'étranglement qui limite le flot maximal.
Pourquoi la méthode de Ford-Fulkerson simple n'a-t-elle pas un temps d'exécution polynomial ?: Si les chemins augmentants sont mal choisis et que les capacités sont grandes (ou irrationnelles), le nombre d'augmentations peut être très élevé, voire ne pas se terminer. Le choix des chemins augmentants les plus courts (Edmonds-Karp) ou l'utilisation de flots bloquants (Dinic) borne le nombre d'augmentations et garantit un temps polynomial.