Loading AI tools
De Wikipédia, l'encyclopédie libre
Le théorème flot-max/coupe-min (ou max flow/min cut en anglais) est un théorème important en optimisation et en théorie des graphes. Il stipule qu'étant donné un graphe de flots, le flot maximum pouvant aller de la source au puits est égal à la capacité minimale devant être retirée du graphe afin d'empêcher qu'aucun flot ne puisse passer de la source au puits.
Ce théorème est un cas particulier du théorème de dualité en optimisation linéaire et généralise le théorème de Kőnig, le théorème de Hall (dans les graphes bipartis) et le théorème de Menger (dans les graphes quelconques).
Soit un graphe orienté.
Un graphe de flots vérifie les deux conditions suivantes :
Un flot dans un graphe de flot est une fonction qui, à chaque arc , associe une quantité . Un flot doit vérifier les conditions suivantes :
La valeur du flot, notée , est la quantité de flot allant de la source au puits. Elle est égale à la quantité de flot sortant de la source : .
Le problème de flot maximum est le problème de maximiser la quantité de flots allant de la source au puits. Cela se traduit par la maximisation de la valeur du flot .
On appelle coupe s-t de un couple de sous-ensembles de sommets disjoints d’union tels que et .
La capacité de la coupe , notée , est la somme des capacités respectives des arcs de à , soit
Le problème de coupe minimum est la minimisation de la capacité , c'est-à-dire la recherche d'une coupe Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « http://localhost:6011/fr.wikipedia.org/v1/ » :): {\displaystyle (S,T)} qui minimise la capacité de la coupe s-t.
Le théorème flot-max/coupe-min est le suivant[1],[2],[3] :
Théorème flot-max/coupe-min — Pour tout graphe orienté , tout couple de sommets, et pour tout vecteur de capacités positives, la valeur maximale du flot de à est égale à la capacité d'une coupe minimale séparant de .
Le théorème a été prouvé par Lester Randolph Ford junior et Delbert Ray Fulkerson en 1954, l'article est paru en 1956[4]. L'algorithme a été donné l'année suivante, aussi par Ford et Fulkerson, et indépendamment par d'autres auteurs, notamment déjà dans une courte note par Peter Elias, A. Feinstein et Claude Shannon[5]. Une description des premiers travaux de Ford et Fulkerson a été donnée par Alexander Schrijver[6].
Le théorème s'étend également aux graphes non orientés.
Les problèmes de flot maximal et coupe minimale peuvent être formulés comme étant les versions primale et duale d'un même programme linéaire. Pour cela, on note le vecteur dans contenant les valeurs de toutes les capacités. Alors on a :
Flot maximum (Primale) | Coupe minimum (Duale) |
---|---|
maximiser sous les contraintes |
minimiser sous les contraintes |
L'équivalence entre ces deux problèmes est une conséquence directe du théorème de dualité forte en optimisation linéaire.
Il est clair que Menger est un cas particulier du théorème flot-max/coupe-min. Pour voir que ce théorème permet d'obtenir les deux théorèmes sur les graphes bipartis, il faut associer à un graphe biparti le graphe orienté obtenu en ajoutant un sommet source et des arcs de vers les sommets de et en ajoutant un sommet puis et des arcs des sommets de vers , et en orientant les arêtes de dans le sens vers . Pour Kőnig, le couplage min de correspond clairement au flot max dans si tous les arcs ont une capacité 1. La coupe min séparant et de s'obtient à partir d'un transversal de en définissant et , et vice-versa. Pour Hall, il suffit de remarquer que pour tout on a que est un transversal de . Donc la cardinalité d'un transversal min (et donc d'une coupe min) par le raisonnement précédent a pour cardinalité si et seulement si la condition de Hall est vérifiée.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.