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

Summarize Timeline Top Qs Fact Check

Soit ${\displaystyle G=(V,A)}$ un graphe orienté.

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

• il possède deux sommets particuliers distincts, une source ${\displaystyle s}$ et un puits ${\displaystyle t}$ ;
• chaque arc ${\displaystyle (u,v)}$ de ${\displaystyle G}$ possède une capacité, ${\displaystyle 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 ${\displaystyle f}$ qui, à chaque arc ${\displaystyle (u,v)}$, associe une quantité ${\displaystyle f(u,v)}$. Un flot doit vérifier les conditions suivantes :

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

${\displaystyle \sum _{u:(u,v)\in A}f(u,v)=\sum _{u:(v,u)\in A}f(v,u)}$ pour tout sommet ${\displaystyle 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 ${\displaystyle |f|}$, est la quantité de flot allant de la source au puits. Elle est égale à la quantité de flot sortant de la source : ${\displaystyle |f|=\sum _{v:(s,v)\in A}f(s,v)}$.

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 ${\displaystyle |f|}$.

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

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

${\displaystyle 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é ${\displaystyle c(S,T)}$, c'est-à-dire la recherche d'une coupe ${\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] :

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.

Summarize Timeline Top Qs Fact Check

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

Flot maximum (Primale)

Coupe minimum (Duale)

maximiser ${\displaystyle |f|=\nabla _{s}}$ sous les contraintes ${\displaystyle {\begin{array}{rcll}f(i,j)&\leq &c(i,j)\quad &(i,j)\in A\\\sum _{j:(j,i)\in A}f(j,i)-\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 ${\displaystyle \sum _{(i,j)\in A}c(i,j)d_{ij}}$ sous les contraintes ${\displaystyle {\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.