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

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En optimisation, le théorème flot-max/coupe-min 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 et 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[modifier | modifier le code]

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

  • On dénote par s, la source, et t le puits de G.
  • On associe à chaque arête (u,v) de G une capacité, c_{uv} qui représente le flot maximum pouvant passer par cette arête. Cette capacité est positive et on note c , le vecteur dans \R_+^{|A|} contenant les valeurs de toutes les capacités.
  • On associe aussi à chaque arête (u,v) un flot f_{uv} représentant la quantité de flot passant par l'arête (u,v). Ce flot doit vérifier deux contraintes:
  1. La contrainte de capacité: f_{uv} \le c_{uv} pour toute arête (u,v)\in A,
  2. La conservation du flot: \sum_{u\,:\,\,(u,v)\in A} f_{uv} = \sum_{u'\,:\,\,(v,u')\in A} f_{vu'} pour tout v \in V\setminus\{s,t\}. Cette contrainte s'appelle aussi la loi des nœuds des lois de Kirchhoff.
  • La valeur du flot représente la quantité de flot allant de la source au puits. Elle se définit par |f| = \sum_{\,\,v\in V} f_{sv} , où s est la source de G.

Problème de flot maximum[modifier | modifier le code]

Article détaillé : Problème de flot maximum.

Le problème de flot maximum se définit comme la maximisation de 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[modifier | modifier le code]

Article détaillé : Coupe minimum.

On appelle coupe S-T de G, un sous-ensemble de sommets D = (S,T) qui partage V en deux ensembles S et T, tel que s\in S et t\in T.

On appelle ensemble de la coupe de D, l'ensemble des arêtes séparant S de T, c'est-à-dire, A_c = \{ (u,v)\in A | u\in S, v\in T \}. On note que si cet ensemble d'arêtes est retiré de G alors la valeur du flot |f| est égale à 0.

Enfin on appelle capacité d'une coupe, c (S,T), la somme des capacités des arêtes de A_c : c (S,T) = \sum_{(u,v) \in S\times T} c_{uv}.


Le problème de coupe minimale se définit comme la minimisation de la capacité c (S,T), c'est-à-dire trouver la partition (S,T) qui minimise la capacité de la coupe S-T.

Énoncé[modifier | modifier le code]

Théorème flot-max/coupe-min (indépendamment P. Elias, A. Feinstein et C. E. Shannon, et L. R. Ford, Jr. (en) et D. R. Fulkerson, 1956) — 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.

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

Formulation en termes de programme linéaire[modifier | modifier le code]

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 :

flot max (Primale)

Coupe min (Duale)

max |f| = \nabla_s

min \sum_{(i, j) \in A} c_{ij} d_{ij}

sous contraintes de


\begin{array}{rclr} f_{ij} & \leq & c_{ij} & (i, j) \in A \\
\sum_{j: (j, i) \in A} f_{ji} - \sum_{j: (i, j) \in A} f_{ij} & \leq & 0 & i \in V, i \neq s,t \\
\nabla_s + \sum_{j: (j, s) \in A} f_{js} - \sum_{j: (s, j) \in A} f_{sj} & \leq & 0 & \\
\nabla_t + \sum_{j: (j, t) \in A} f_{jt} - \sum_{j: (t, j) \in A} f_{tj} & \leq & 0 & \\
f_{ij} & \geq & 0 & (i, j) \in A\\
\end{array}

sous contraintes de

\begin{array}{rclr}
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[modifier | modifier le code]

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[modifier | modifier le code]

Notes et références[modifier | modifier le code]