Théorème flot-max/coupe-min

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).

Définitions et notations

Soit $G=(V,A)$ un graphe orienté.

Graphe de flot

Un graphe de flots vérifie les deux conditions suivantes :

• il possède deux sommets particuliers distincts, une source $s$ et un puits $t$ ;
• chaque arc $(u,v)$ de $G$ possède une capacité, $c(u,v)$ qui représente le flot maximum pouvant passer par cet arc. Cette capacité est positive.

Un flot dans un graphe de flot est une fonction $f$ qui, à chaque arc $(u,v)$, associe une quantité $f(u,v)$. Un flot doit vérifier les conditions suivantes :

• la contrainte de capacité : $f(u,v)\leq c(u,v)$ pour tout arc $(u,v)\in A$ ;
• la loi de conservation du flot :

$\sum _{u:(u,v)\in A}f(u,v)=\sum _{u:(v,u)\in A}f(v,u)$ pour tout sommet $v\in V\setminus \{s,t\}$.

Cette contrainte s'appelle aussi la loi des nœuds des lois de Kirchhoff.

La valeur du flot, notée $|f|$, est la quantité de flot allant de la source au puits. Elle est égale à la quantité de flot sortant de la source : $|f|=\sum _{v:(s,v)\in A}f(s,v)$.

Problème de flot maximum

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 $|f|$.

Problème de coupe minimum

On appelle coupe s-t de $G$ un couple de sous-ensembles de sommets $(S,T)$ disjoints d’union $G$ tels que $s\in S$ et $t\in T$.

La capacité de la coupe $(S,T)$, notée $c(S,T)$, est la somme des capacités respectives des arcs de $S$ à $T$, soit

$c(S,T)=\sum _{u\in S,v\in T}c(u,v)$.

Le problème de coupe minimum est la minimisation de la capacité $c(S,T)$, c'est-à-dire la recherche d'une coupe $(S,T)$ qui minimise la capacité de la coupe s-t.

Énoncé

Le théorème flot-max/coupe-min est le suivant :

Théorème flot-max/coupe-min — Pour tout graphe orienté $G$ , tout couple $(s,t)$ de sommets, et pour tout vecteur de capacités positives, la valeur maximale du flot de $s$ à $t$ est égale à la capacité d'une coupe minimale séparant $s$ de $t$.

Le théorème a été prouvé par Lester Randolph Ford junior et Delbert Ray Fulkerson en 1954, l'article est paru en 1956. 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. Une description des premiers travaux de Ford et Fulkerson a été donnée par Alexander Schrijver.

Le théorème s'étend également aux graphes non orientés.

Formulation en termes de programmation linéaire

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 $c$ le vecteur dans $\mathbb {R} _{+}^{|A|}$ contenant les valeurs de toutes les capacités. Alors on a :

Flot maximum (Primale)	Coupe minimum (Duale)
maximiser $|f|=\nabla _{s}$ sous les contraintes ${\begin{array}{rcll}f(i,j)&\leq &c(i,j)\quad &(i,j)\in A\\\sum _{j:(j,i)\in A}f(i,j)-\sum _{j:(i,j)\in A}f(i,j)&\leq &0&i\in V,i\neq s,t\\\nabla _{s}+\sum _{j:(j,s)\in A}f(j,s)-\sum _{j:(s,j)\in A}f(s,j)&\leq &0&\\\nabla _{t}+\sum _{j:(j,t)\in A}f(j,t)-\sum _{j:(t,j)\in A}f(t,j)&\leq &0&\\f(i,j)&\geq &0&(i,j)\in A\\\end{array}}$	minimiser $\sum _{(i,j)\in A}c_{ij}d_{ij}$ sous les contraintes ${\begin{array}{rcll}d_{ij}-p_{i}+p_{j}&\geq &0&(i,j)\in A\\p_{s}&=&1&\\p_{t}&=&0&\\p_{i}&\geq &0&i\in V\\d_{ij}&\geq &0&(i,j)\in A\end{array}}$

L'équivalence entre ces deux problèmes est une conséquence directe du théorème de dualité forte en optimisation linéaire.

Généralisation des théorèmes de König, Hall et Menger

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 $G=(A,B;E)$ le graphe orienté $D$ obtenu en ajoutant un sommet source $s$ et des arcs de $s$ vers les sommets de $A$ et en ajoutant un sommet puis $t$ et des arcs des sommets de $B$ vers $t$, et en orientant les arêtes de $G$ dans le sens $A$ vers $B$. Pour Kőnig, le couplage min de $G$ correspond clairement au flot max dans $D$ si tous les arcs ont une capacité 1. La coupe min $(S,T)$ séparant $s$ et $t$ de $D$ s'obtient à partir d'un transversal $T$ de $G$ en définissant $S:=\{s\}\cup (Y\cap T)$ et $T:=\{t\}\cup (X\cap T)$, et vice-versa. Pour Hall, il suffit de remarquer que pour tout $X\subseteq A$ on a que $X\cup (Y\setminus N(X))$ est un transversal de $G$. Donc la cardinalité d'un transversal min (et donc d'une coupe min) par le raisonnement précédent a pour cardinalité $|A|\,(=|B|)$ si et seulement si la condition de Hall est vérifiée.

Bibliographie

De nombreux ouvrages et livres d'enseignement exposent le théorème du flot maximum - coupe minimum, le plus souvent avec l'algorithme de construction de Ford et Fulkerson.

• (en) Eugene Lawler, Combinatorial Optimization : Networks and Matroids, Mineola (N.Y.), Dover, 2001, 374 p. (ISBN 0-486-41453-1, lire en ligne) : Sections 4.5. « Combinatorial Implications of Max-Flow Min-Cut Theorem » et 4.6. « Linear Programming Interpretation of Max-Flow Min-Cut Theorem », p. 117–120.
• (en) Christos H. Papadimitriou et Kenneth Steiglitz, Combinatorial Optimization : Algorithms and Complexity, Mineola (N.Y.), Dover, 1998, 496 p. (ISBN 0-486-40258-4, lire en ligne) : Section 6.1 : « The Max-Flow, Min-Cut Theorem », p. 120–128.
• (en) Vijay V. Vazirani, Approximation Algorithms, Springer, 2004, 380 p. (ISBN 3-540-65367-8, lire en ligne) : Chapitre 12 « Introduction to LP-Duality », p. 93–100.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, 2002 [détail de l’édition] : Chapitre 27 : « Flot maximum », p. 638.
• (en) Kevin Wayne, « Chapter 7. Network Flow I », Lecture Slides for Algorithm Design, Home page of Kevin Wayne - Teaching (consulté le 27 juillet 2015) : « Chapter 7. Network Flow I ».
• (en) Jon Kleinberg et Éva Tardos, Algorithm Design, Pearson, 2005, 1^re éd., 864 p. (ISBN 978-0-321-29535-4, présentation en ligne). Chapitre 7 : « Network Flows » Une deuxième édition est annoncée pour octobre 2015.
• Gilles Schaeffer, « Cours 2:Flots et couplages », INF550 - Algorithmique avancée, École polytechnique (consulté le 27 juillet 2015).
• Robert Cori, Guillaume Hanrot, Claire Kenyon, Jean-Marc Steyaert, « INF550 - Conception et analyse d’algorithmes », École polytechnique.