Optimisation de flot
Nous renvoyons au cours de théorie des graphes pour le rappel sur ces notions ainsi que l'ensemble des notations
Réseau
Définition
Un réseau est la donnée d'un graphe connexe valué \( (\G,\lambda)\) possédant une unique source et un unique puits.
\[
\xymatrix@C=2.5cm@R=0.19cm{
&A\ar@/_1pc/[dd]_{10}\ar[r]^{12}&C\ar[rd]^{20}\ar[ldd]_9&\\
s\ar[ru]^{16}\ar[rd]_{13}&&&p\\
&B\ar[r]_{14}\ar@/_1pc/[uu]_4&D\ar[uu]^7\ar[ru]_4&
}
\]
Remarque
Puisqu'un réseau ne possède qu'une source et qu'un puits, on peut parler de la source et de le puits.
Un réseau modélise un phénomène de transfert de flux
1. Le réseau précédent peut, par exemple, modéliser la circulation d'eau à travers des quartiers d'une ville (les quartiers \( A\) , \( B\) , \( C\) et \( D\) ), le sommet \( s\) représentant la source de ce réseau (au sens définie ici et au sens naturel d'une source) tout comme le puits. La valuation du réseau représentant la capacitée maximale des canalisations.
Définition
Un
flot sur un réseau \( (\G,\lambda)\) de source \( s\) et de puits \( p\) est la donnée d'une application \( f:\Arc(\G)\longmapsto [0; +\infty[\) satisfaisant
- \( (i)\) .
- \( \forall (x,y)\in \Arc(\G)\) , \( f(x,y) \leqslant \lambda(x,y)\) .
- \( (ii)\) .
- La loi des noeuds :
\[\forall x \in \Som(\G)-\{s,p\},\qquad \sum_{y\in \Gamma^{+1}(x,\G)} f(x,y)=\sum_{z\in \Gamma^{-1}(x,\G)}f(z,x)\]
Dans la pratique un flot, représente le parcours d'un flux dans le réseau. En reprennant la modélisation des canalisations, un flot représente le parcours du l'eau dans les canalisation.
Remarque
Une manière alternative d'énoncer la loi des noeuds est : tout ce qui rentre sort.
Considérons le réseau suivant
\[
\xymatrix@C=2.19cm@R=1.519cm{
&A\ar@/_1pc/[dd]_7&\\
s\ar[ru]^6\ar[rd]_5&&p\\
&B\ar@/_1pc/[uu]_5\ar[ru]_{10}&
}
\]
\begin{eqnarray*}
f:\Arc(\G)&\longmapsto&[0;+\infty[\\
(s,A)&\longrightarrow&5\\
(s,B)&\longrightarrow&5\\
(A,B)&\longrightarrow&7\\
(B,A)&\longrightarrow&2\\
(B,p)&\longrightarrow&10
\end{eqnarray*}
On peut représenter un flot dans un réseau en indiquant sur chaque arc \( valeur\,du\,flot/valuation\) .
\[
\xymatrix@C=2.19cm@R=1.519cm{
&A\ar@/_1pc/[dd]_{{\color{red}7}/7}&\\
s\ar[ru]^{{\color{red}5}/6}\ar[rd]_{{\color{red}5}/5}&&p\\
&B\ar@/_1pc/[uu]_{{\color{red}2}/5}\ar[ru]_{{\color{red}10}/10}&
}
\]
Définition
Soient \( f\) un flot sur un réseau \( (\G,\lambda)\) de source \( s\) et de puits \( p\) et \( x\in \Som(\G)-\{s,p\}\)
- \( \bullet\)
- Le flux de \( x\) est \( \dpl{\sum_{y\in \Gamma^{+1}(x,\G)} f(x,y)=\sum_{z\in \Gamma^{-1}(x,\G)}f(z,x)}\) .
- \( \bullet\)
- Le flux entrant est \( \sum_{y\in \Gamma^{+1}(s,\G)}f(s,y)\) .
- \( \bullet\)
- Le flux sortant est \( \sum_{z\in \Gamma^{-1}(s,\G)}f(z,p)\) .
Dans l'exemple précédent le flux de \( A\) est \( 7\) et le flux de \( B\) est \( 12\) . La valeur du flux entrant est \( 10\) comme la valeur du flux sortant.
Proposition
Quelque soit le flot dans un réseau, la valeur du flux entrant est égale à la valeur du flux sortant.
Démonstration
Le flux entrant se propage dans le réseau et il n'y a aucune perte car chaque sommet satisfait la loi des noeuds ; on retrouve donc la valeur du flux entrant dans le puits.
Définition
Soit \( f\) un flot sur un réseau \( (G,\lambda)\) de source \( s\) et de puits \( p\) . On appel flux du réseau le nombre
\[\flux(f)=\sum_{y\in \Gamma^{+1}(s,\G)}f(s,y) = \sum_{z\in \Gamma^{-1}(s,\G)}f(z,p)\]
Étant donné un réseau, peut-on déterminer un flot de flux maximal ?
Cette question reviens à chercher une application satisfaisant les conditions de la définition et maximisant le flux. Il s'agit donc d'un problème linéaire.
Proposition
Soit \( (\G,\lambda)\) un réseau de source \( s\) et de puits \( p\) . Considérons le problème linéaire suivant (les inconnues étants \( f(x,y)\) pour tout arc \( (x,y)\) de \( \G\) ) :
\[
\left\{
\begin{array}{lrcl}
\forall (x,y)\in \Arc(\G),& f(x,y)&\leqslant&\lambda(x,y)\\
\forall x\in \Som(\G)-\{s,p\},& \dpl{\sum_{y\in \Gamma^{+1}(x,\G)} f(x,y)-\sum_{z\in \Gamma^{-1}(x,\G)}f(z,x)}&=&0\\
&\dpl{\sum_{y\in \Gamma^{+1}(s,\G)} f(s,y)-\sum_{z\in \Gamma^{-1}(p,\G)}f(z,p)}&=&0\\
&\dpl{Max\left(\sum_{y\in \Gamma^{+1}(s,\G)}f(s,y)\right)}&&
\end{array}
\right.
\]
La solution de ce problème, si elle existe, est une fonction de flot qui maximise le flux.
Démonstration
Les inéquations du problème viennent du premier point de la définition de flot. Les équations traduisent la loi des noeuds ainsi que la conservation du flux et la fonction à maximiser est le flux du flot.
Considérons le réseau suivant
\[
\xymatrix@C=1.519cm{
&A\ar@/_1pc/[dd]_7&\\
s\ar[ru]^6\ar[rd]_5&&p\\
&B\ar@/_1pc/[uu]_5\ar[ru]_{10}&
}
\]
Pour simplifier, on note \( f(s,A)=\alpha\) , \( f(s,B)=\beta\) , \( f(A,B)=\gamma\) , \( f(B,A)=\delta\) et \( f(B,p)=\varepsilon\) .
Le système linéaire associé est
\[\left\{
\begin{array}{rcl}
\alpha &\leqslant&6\\
\beta &\leqslant&5\\
\gamma &\leqslant&7\\
\delta &\leqslant&5\\
\varepsilon &\leqslant&10\\
\alpha+\delta-\gamma &=&0\\
\beta+\gamma-\delta-\varepsilon&=&0\\
\alpha+\beta-\varepsilon&=&0\\
Max(\alpha+\beta)&&
\end{array}
\right.
\]
On peut chercher la solution via les méthodes alternatives (deux phases ou grand \( M\) ). Le premier tableau de la méthode du grand \( M\) est le suivant :
\[
\begin{array}{c|ccccccccccccc|c}
&\alpha&\beta&\gamma&\delta&\varepsilon&e_1&e_2&e_3&e_4&e_5&a_1&a_2&a_3\\\hline
e_1&1&0&0&0&0&1&0&0&0&0&0&0&0&6\\
e_2&0&1&0&0&0&0&1&0&0&0&0&0&0&5\\
e_3&0&0&1&0&0&0&0&1&0&0&0&0&0&7\\
e_4&0&0&0&1&0&0&0&0&1&0&0&0&0&5\\
e_5&0&0&0&0&1&0&0&0&0&1&0&0&0&10\\
a_1&1&0&-1&1&0&0&0&0&0&0&1&0&0&0\\
a_2&0&1&1&-1&-1&0&0&0&0&0&0&1&0&0\\
a_3&1&1&0&0&-1&0&0&0&0&0&0&0&1&0\\\hline
Max&1&1&0&0&0&0&0&0&0&0&-M&-M&-M&0
\end{array}
\]
On dénombre 13 variables pour un problème initial de 4 sommets et 5 arcs.
Remarque
On observe qu'un réseau avec \( s\) sommets et \( a\) arcs fait apparaître un problème linéaire à \( 2a+s-1\) variables (ce qui correspond aux nombres de colonne de la matrice de résolution).
Par un raisonnement combinatoire on peut démontrer que le nombre maximal de variables pour un réseau à \( s{>}2\) sommets est \( (s-1)(2s-3)\) (par exemple le plus gros réseau sur \( 8\) sommets engendrera un problème linéaire à \( 91\) variables).
Fort heureusement, il existe une autre méthode de résolution, basée sur l'étude récursif du graphe.
Algorithme de Ford-Fulkerson
Voici l'algorithme de Ford-Fulkerson permettant d'exhiber un bon candidat pour la fonction de flot de flux maximal.
§
Algorithme de Ford-Fulkerson.
- Étape 0.
- Initialisation.
- \( \bullet\)
- La fonction de flot vaut \( 0\) sur chaque arc.
- \( \bullet\)
- Le flux est nul.
- Étape 1.
- Recherche d'un chemin améliorant. Marquage \( +\) ou \( -\) .
- On marque \( +\) la source.
- On marque \( +\) un sommet qui est extrémité d'un arc dont l'origine est déjà marqué \( +\) ou \( -\) et sur lequel le flux peut augmenter.
- On marque \( -\) un sommet qui est origine d'un arc dont l'extrémité est déjà marqué \( +\) ou \( -\) et sur lequel le flux peut diminuer.
- On recommence le point précédent tant que le puits n'est pas marqué.
- \( \bullet\)
- Lorsque le puits est marqué on passe à l'étape 2.
- \( \bullet\)
- S'il n'est plus possible de marquer le puits on s'arrête.
Le processus de marquage permet de déterminer un chemin entre la source et le puits
(en ne considérant pas l'orientation des arcs). C'est ce que l'on appel le chemin
améliorant.
- Étape 2.
- Amélioration du flux.
- Flux \( +\) .
- Pour chaque arc du chemin améliorant dans le sens direct (respectant
l'orientation des arc ; ou : dont l'origine est marqué \( +\) ), on calcul la différence entre la valuation et le flot de l'arc.
- Flux \( -\) .
- Pour chaque arc du chemin améliorant dans le sens indirect (ne respectant pas l'orientation des arc ; ou : dont l'origine est marqué \( -\) ), on considère la valeur du flot de l'arc.
- Valeur améliorante du flux.
- On prend le plus petit des flux \( +\) et \( -\) .
- Étape 3.
- Pour chaque arc du chemin améliorant dont le l'origine est marqué \( +\) on incrémente le flot de la valeur améliorante du flux et pour les arcs dont l'origine est marqué \( -\) on décrémente le flot de la valeur améliorante du flux.
Détaillons un exemple.
Considérons le réseau suivant :
\[
\xymatrix@C=2.519cm@R=1.519cm{
&s\ar@/_2pc/[ldd]_{8}\ar@/^2pc/[rdd]^{6}&\\
&C\ar[d]_{4}&\\
A\ar[ru]^{8}\ar[rd]_{7}&p&B\ar[lu]^{6}\ar[ld]^{3}\\
&D\ar[u]_{9}&
}
\]
Commençons par l'initialisation.
\[
\xymatrix@C=2.519cm@R=1.519cm{
&s\ar@/_2pc/[ldd]_{{\color{red}0}/8}\ar@/^2pc/[rdd]^{{\color{red}0}/6}&\\
&C\ar[d]_{{\color{red}0}/4}&\\
A\ar[ru]^{{\color{red}0}/8}\ar[rd]_{{\color{red}0}/7}&p&
B\ar[lu]^{{\color{red}0}/6}\ar[ld]^{{\color{red}0}/3}\\
&D\ar[u]_{{\color{red}0}/9}&
}
\]
Dans ce cas \( \flux(f)=0\) .
On marque la source.
\[
\xymatrix@C=1.519cm@R=0.7519cm{
&s^{\color{red}+}\ar@/_2pc/[ldd]_{{\color{red}0}/8}\ar@/^2pc/[rdd]^{{\color{red}0}/6}&\\
&C\ar[d]_{{\color{red}0}/4}&\\
A\ar[ru]^{{\color{red}0}/8}\ar[rd]_{{\color{red}0}/7}&p&
B\ar[lu]^{{\color{red}0}/6}\ar[ld]^{{\color{red}0}/3}\\
&D\ar[u]_{{\color{red}0}/9}&
}
\]
Puisqu'on cherche à maximiser le flux, on va choisir les arcs de flot le plus grand possible. On marque \( A\) .
\[
\xymatrix@C=1.519cm@R=0.7519cm{
&s^{\color{red}+}\ar@/_2pc/[ldd]_{{\color{red}0}/8}\ar@/^2pc/[rdd]^{{\color{red}0}/6}&\\
&C\ar[d]_{{\color{red}0}/4}&\\
A^{\color{red}+}\ar[ru]^{{\color{red}0}/8}\ar[rd]_{{\color{red}0}/7}&p&
B\ar[lu]^{{\color{red}0}/6}\ar[ld]^{{\color{red}0}/3}\\
&D\ar[u]_{{\color{red}0}/9}&
}
\]
Puis on marque \( C\) .
\[
\xymatrix@C=1.519cm@R=0.7519cm{
&s^{\color{red}+}\ar@/_2pc/[ldd]_{{\color{red}0}/8}\ar@/^2pc/[rdd]^{{\color{red}0}/6}&\\
&C^{\color{red}+}\ar[d]_{{\color{red}0}/4}&\\
A^{\color{red}+}\ar[ru]^{{\color{red}0}/8}\ar[rd]_{{\color{red}0}/7}&p&
B\ar[lu]^{{\color{red}0}/6}\ar[ld]^{{\color{red}0}/3}\\
&D\ar[u]_{{\color{red}0}/9}&
}
\]
Et finalement on marque le puits.
\[
\xymatrix@C=1.519cm@R=0.7519cm{
&s^{\color{red}+}\ar@/_2pc/[ldd]_{{\color{red}0}/8}\ar@/^2pc/[rdd]^{{\color{red}0}/6}&\\
&C^{\color{red}+}\ar[d]_{{\color{red}0}/4}&\\
A^{\color{red}+}\ar[ru]^{{\color{red}0}/8}\ar[rd]_{{\color{red}0}/7}&p^{\color{red}+}&
B\ar[lu]^{{\color{red}0}/6}\ar[ld]^{{\color{red}0}/3}\\
&D\ar[u]_{{\color{red}0}/9}&
}
\]
Nous avons donc déterminer un chemin améliorant : \( sACp\) .
- Arc \( (s,A)\) .
- L'origine (\( s\) ) est marqué \( +\) . On calcul donc la différence entre la valuation et le flot : \( 8-0=8\) .
- Arc \( (A,C)\) .
- L'origine (\( A\) ) est marqué \( +\) . On calcul \( 8-0=8\) .
- Arc \( (C,p)\) .
- L'origine (\( C\) ) est marqué \( +\) . On calcul \( 4-0=4\) .
Le plus petit nombre est \( 4\) .
On modifie le flot :
- Flot de l'arc \( (s,A)\) .
- L'origine est marqué \( +\) , on incrémente le flot de \( 4\) : \( 0+4=4\) .
- Flot de l'arc \( (A,C)\) .
- L'origine est marqué \( +\) , on incrémente le flot de \( 4\) : \( 0+4=4\) .
- Flot de l'arc \( (C,p)\) .
- L'origine est marqué \( +\) , on incrémente le flot de \( 4\) : \( 0+4=4\) .
- Flux.
- On augmente la valeur du flux de \( 4\) .
\[
\xymatrix@C=2.519cm@R=1.519cm{
&s\ar@/_2pc/[ldd]_{{\color{red}4}/8}\ar@/^2pc/[rdd]^{{\color{red}0}/6}&\\
&C\ar[d]_{{\color{red}4}/4}&\\
A\ar[ru]^{{\color{red}4}/8}\ar[rd]_{{\color{red}0}/7}&p&
B\ar[lu]^{{\color{red}0}/6}\ar[ld]^{{\color{red}0}/3}\\
&D\ar[u]_{{\color{red}0}/9}&
}
\]
A la fin de cette itération, nous avons augmenter la valeur du flux : \( \flux(f)=4\) .
On marque \( s\) .
\[
\xymatrix@C=1.519cm@R=0.7519cm{
&s^{\color{red}+}\ar@/_2pc/[ldd]_{{\color{red}4}/8}\ar@/^2pc/[rdd]^{{\color{red}0}/6}&\\
&C\ar[d]_{{\color{red}4}/4}&\\
A\ar[ru]^{{\color{red}4}/8}\ar[rd]_{{\color{red}0}/7}&p&
B\ar[lu]^{{\color{red}0}/6}\ar[ld]^{{\color{red}0}/3}\\
&D\ar[u]_{{\color{red}0}/9}&
}
\]
On marque \( B\) .
\[
\xymatrix@C=1.519cm@R=0.7519cm{
&s^{\color{red}+}\ar@/_2pc/[ldd]_{{\color{red}4}/8}\ar@/^2pc/[rdd]^{{\color{red}0}/6}&\\
&C\ar[d]_{{\color{red}4}/4}&\\
A\ar[ru]^{{\color{red}4}/8}\ar[rd]_{{\color{red}0}/7}&p&
B^{\color{red}+}\ar[lu]^{{\color{red}0}/6}\ar[ld]^{{\color{red}0}/3}\\
&D\ar[u]_{{\color{red}0}/9}&
}
\]
On marque \( C\) .
\[
\xymatrix@C=1.519cm@R=0.7519cm{
&s^{\color{red}+}\ar@/_2pc/[ldd]_{{\color{red}4}/8}\ar@/^2pc/[rdd]^{{\color{red}0}/6}&\\
&C^{\color{red}+}\ar[d]_{{\color{red}4}/4}&\\
A\ar[ru]^{{\color{red}4}/8}\ar[rd]_{{\color{red}0}/7}&p&
B^{\color{red}+}\ar[lu]^{{\color{red}0}/6}\ar[ld]^{{\color{red}0}/3}\\
&D\ar[u]_{{\color{red}0}/9}&
}
\]
On ne peut pas marquer le sommet \( p\) car l'arc \( (C,p)\) a déjà un flot maximal ; on dit que l'arc est saturé. Mais on peut marquer \( A\) d'un \( -\) car le flot de l'arc \( (C,A)\) est strictement positif (il est de \( 4\) ) et peut donc diminuer. On marque \( A\) .
\[
\xymatrix@C=1.519cm@R=0.7519cm{
&s^{\color{red}+}\ar@/_2pc/[ldd]_{{\color{red}4}/8}\ar@/^2pc/[rdd]^{{\color{red}0}/6}&\\
&C^{\color{red}+}\ar[d]_{{\color{red}4}/4}&\\
A^{\color{red}-}\ar[ru]^{{\color{red}4}/8}\ar[rd]_{{\color{red}0}/7}&p&
B^{\color{red}+}\ar[lu]^{{\color{red}0}/6}\ar[ld]^{{\color{red}0}/3}\\
&D\ar[u]_{{\color{red}0}/9}&
}
\]
On marque \( D\) .
\[
\xymatrix@C=1.519cm@R=0.7519cm{
&s^{\color{red}+}\ar@/_2pc/[ldd]_{{\color{red}4}/8}\ar@/^2pc/[rdd]^{{\color{red}0}/6}&\\
&C^{\color{red}+}\ar[d]_{{\color{red}4}/4}&\\
A^{\color{red}-}\ar[ru]^{{\color{red}4}/8}\ar[rd]_{{\color{red}0}/7}&p&
B^{\color{red}+}\ar[lu]^{{\color{red}0}/6}\ar[ld]^{{\color{red}0}/3}\\
&D^{\color{red}+}\ar[u]_{{\color{red}0}/9}&
}
\]
On marque \( p\) .
\[
\xymatrix@C=1.519cm@R=0.7519cm{
&s^{\color{red}+}\ar@/_2pc/[ldd]_{{\color{red}4}/8}\ar@/^2pc/[rdd]^{{\color{red}0}/6}&\\
&C^{\color{red}+}\ar[d]_{{\color{red}4}/4}&\\
A^{\color{red}-}\ar[ru]^{{\color{red}4}/8}\ar[rd]_{{\color{red}0}/7}&p^{\color{red}+}&
B^{\color{red}+}\ar[lu]^{{\color{red}0}/6}\ar[ld]^{{\color{red}0}/3}\\
&D^{\color{red}+}\ar[u]_{{\color{red}0}/9}&
}
\]
Le chemin améliorant est : \( sBCADp\) .
- Arc \( (s,B)\) .
- L'origine est marqué \( +\) : \( 6-0=6\) .
- Arc \( (B,C)\) .
- L'origine est marqué \( +\) : \( 6-0=6\) .
- Pour \( (C,A)\)
- Il s'agit en fait de l'arc \( (A,C)\) . L'origine est marqué \( -\) : on regarde quelle quantité peut être enlever au flot : \( 4\) .
- Arc \( (A,D)\) .
- L'origine est marqué \( +\) : \( 7-0=7\) .
- Arc \( (D,p)\) .
- L'origine est marque \( +\) : \( 9-0=9\) .
Le plus petit nombre est \( 4\) .
- Flot de l'arc \( (s,B)\) .
- L'origine est marqué \( +\) , on incrémente le flot de \( 4\) : \( 0+4=4\) .
- Flot de l'arc \( (B,C)\) .
- L'origine est marqué \( +\) , on incrémente le flot de \( 4\) : \( 0+4=4\) .
- Flot de l'arc \( (C,A)\) .
- L'origine est marqué \( -\) , on décrémente le flot de \( 4\) : \( 4-4=0\) .
- Flot de l'arc \( (A,D)\) .
- L'origine est marqué \( +\) , on incrémente le flot de \( 4\) : \( 0+4=4\) .
- Flot de l'arc \( (D,p)\) .
- L'origine est marqué \( +\) , on incrémente le flot de \( 4\) : \( 0+4=4\) .
- Flux.
- Le flux augmente de \( 4\) .
\[
\xymatrix@C=2.519cm@R=1.019cm{
&s\ar@/_2pc/[ldd]_{{\color{red}4}/8}\ar@/^2pc/[rdd]^{{\color{red}4}/6}&\\
&C\ar[d]_{{\color{red}4}/4}&\\
A\ar[ru]^{{\color{red}0}/8}\ar[rd]_{{\color{red}4}/7}&p&
B\ar[lu]^{{\color{red}4}/6}\ar[ld]^{{\color{red}0}/3}\\
&D\ar[u]_{{\color{red}4}/9}&
}
\]
A la fin de cette itération, nous avons augmenter la valeur du flux : \( \flux(f)=4+4=8\) .
Continuons en éludant certaines étapes.
Marquage
\[
\xymatrix@C=1.519cm@R=0.7519cm{
&s^{\color{red}+}\ar@/_2pc/[ldd]_{{\color{red}4}/8}\ar@/^2pc/[rdd]^{{\color{red}4}/6}&\\
&C\ar[d]_{{\color{red}4}/4}&\\
A\ar[ru]^{{\color{red}0}/8}\ar[rd]_{{\color{red}4}/7}&p^{\color{red}+}&
B^{\color{red}+}\ar[lu]^{{\color{red}4}/6}\ar[ld]^{{\color{red}0}/3}\\
&D^{\color{red}+}\ar[u]_{{\color{red}4}/9}&
}
\]
Chaine améliorante : \( sBDp\) .
- Arc \( (s,B)\) .
- \( 6-4=2\)
- Arc \( (B,D)\) .
- \( 3-0=3\)
- Arc \( (D,p)\) .
- \( 9-4=5\)
Flot améliorant : \( 2\)
\[
\xymatrix@C=1.519cm@R=0.7519cm{
&s\ar@/_2pc/[ldd]_{{\color{red}4}/8}\ar@/^2pc/[rdd]^{{\color{red}6}/6}&\\
&C\ar[d]_{{\color{red}4}/4}&\\
A\ar[ru]^{{\color{red}0}/8}\ar[rd]_{{\color{red}4}/7}&p&
B\ar[lu]^{{\color{red}4}/6}\ar[ld]^{{\color{red}2}/3}\\
&D\ar[u]_{{\color{red}6}/9}&
}
\]
\( \flux(f)=8+2=10\)
Marquage
\[
\xymatrix@C=1.519cm@R=0.7519cm{
&s^{\color{red}+}\ar@/_2pc/[ldd]_{{\color{red}4}/8}\ar@/^2pc/[rdd]^{{\color{red}6}/6}&\\
&C^{\color{red}+}\ar[d]_{{\color{red}4}/4}&\\
A^{\color{red}+}\ar[ru]^{{\color{red}0}/8}\ar[rd]_{{\color{red}4}/7}&p^{\color{red}+}&
B^{\color{red}-}\ar[lu]^{{\color{red}4}/6}\ar[ld]^{{\color{red}2}/3}\\
&D^{\color{red}+}\ar[u]_{{\color{red}6}/9}&
}
\]
Chaine améliorante : \( sACBDp\) .
- Arc \( (s,A)\) .
- \( 8-4=4\)
- Arc \( (A,C)\) .
- \( 8-0=8\)
- Pour \( (C,B)\) .
- \( 4\)
- Arc \( (B,D)\) .
- \( 3-2=1\)
- Arc \( (D,p)\) .
- \( 9-6=3\)
Flot améliorant : \( 1\)
\[
\xymatrix@C=1.519cm@R=0.7519cm{
&s\ar@/_2pc/[ldd]_{{\color{red}5}/8}\ar@/^2pc/[rdd]^{{\color{red}6}/6}&\\
&C\ar[d]_{{\color{red}4}/4}&\\
A\ar[ru]^{{\color{red}1}/8}\ar[rd]_{{\color{red}4}/7}&p&
B\ar[lu]^{{\color{red}3}/6}\ar[ld]^{{\color{red}3}/3}\\
&D\ar[u]_{{\color{red}7}/9}&
}
\]
\( \flux(f)=10+1=11\)
Marquage
\[
\xymatrix@C=1.519cm@R=0.7519cm{
&s^{\color{red}+}\ar@/_2pc/[ldd]_{{\color{red}5}/8}\ar@/^2pc/[rdd]^{{\color{red}6}/6}&\\
&C\ar[d]_{{\color{red}4}/4}&\\
A^{\color{red}+}\ar[ru]^{{\color{red}1}/8}\ar[rd]_{{\color{red}4}/7}&p^{\color{red}+}&
B\ar[lu]^{{\color{red}3}/6}\ar[ld]^{{\color{red}3}/3}\\
&D^{\color{red}+}\ar[u]_{{\color{red}7}/9}&
}
\]
Chaine améliorante : \( sADp\) .
- Arc \( (s,A)\) .
- \( 8-5=3\)
- Arc \( (A,D)\) .
- \( 7-4=3\)
- Pour \( (D,p)\) .
- \( 9-7=2\)
Flot améliorant : \( 2\)
\[
\xymatrix@C=1.519cm@R=0.7519cm{
&s\ar@/_2pc/[ldd]_{{\color{red}7}/8}\ar@/^2pc/[rdd]^{{\color{red}6}/6}&\\
&C\ar[d]_{{\color{red}4}/4}&\\
A\ar[ru]^{{\color{red}1}/8}\ar[rd]_{{\color{red}6}/7}&p&
B\ar[lu]^{{\color{red}3}/6}\ar[ld]^{{\color{red}3}/3}\\
&D\ar[u]_{{\color{red}9}/9}&
}
\]
\( \flux(f)=11+2=13\)
L'algorithme s'achève ici. On observe en effet que tous les arcs aboutissants au puits sont saturés il sera donc impossible de déterminer une chaine améliorante.
Comment s'assurer que le flot trouvé est maximal ?
Définition
Soit \( (G,\lambda)\) un réseau de source \( s\) et de puits \( p\) . Une
coupe de \( \G\) est la donné de deux sous-ensembles \( X\) , \( \overline{X}\) de \( \Som(\G)\) satisfaisant :
- \( (i)\)
- \( s\in X\) , \( p\in \overline{X}\) .
- \( (ii)\)
- \( X\cup\overline{X}=\Som(\G)\) , \( X\cap\overline{X}=\varnothing\) .
Pour toute coupe \( (X,\overline{X})\) , on définit la
valeur de la coupe comme le nombre \[\lambda(X,\overline{X})=\sum_{x\in X, y\in \overline{X}}\lambda(x,y)\]
\(
\xymatrix@C=2.5cm{
& \ar@{--}@/^1pc/[ddddr]&&\\
&A \ar@/_1pc/[dd]_{10} \ar@*{[red]}[r]^{12}&C \ar[rd]^{20} \ar[ldd]_9&\\
s \ar[ru]^{16} \ar[rd]_{13}&&&p\\
&B \ar@*{[red]}[r]_{14} \ar@/_1pc/[uu]_4 & D \ar[uu]^{7} \ar[ru]_4&\\
\ar@{-}[rr]_X && \ar@{-}[r]_{\overline{X}}&
}
\)
La valeur de cette coupe est \( \lambda(X,\overline{X})=12+14=26\)
Théorème [Ford-Fulkerson]
Pour tout flot \( f\) et toute coupe \( (X,\overline{X})\) d'un réseau
\[\flux(f)\leqslant\lambda(X,\overline{X})\]
Corollaire
S'il existe un flot \( f\) et une coupe \( (X,\overline{X})\) tel que \( \flux(f)=\lambda(X,\overline{X})\) alors le flot est de flux maximal.
Dans la pratique, lorsqu'on dispose d'un candidat au flot de flux maximal, obtenu par l'algorithme de Ford-Fulkerson par exemple, il suffit de trouver une coupe de la valeur du flux pour conclure qu'il est maximal.
Dans notre exemple, si on considère \( X=\{s,A,B,C,D\}\) et \( \overline{X}=\{p\}\) alors \( (X,\overline{X})\) est une coupe de valeur \( 13\) . Puisque le flot trouvé est de flux \( 13\) , il de flux maximal.
1Le mot flux aura pour nous un sens différent, on l'utilise ici dans le sens courant du terme.
