next up previous
suivant: Une amélioration possible monter: L'algorithme de Ford & précédent: Forme naïve de l'algorithme

Une implémentation possible de l'algorithme de Ford & Fulkerson

Nous allons ici nous intéresser à la manière dont l'on programme habituellement l'algorithme de Ford & Fulkerson. Cette méthode fait appel à un marquage des sommets et une liste de sommets candidats. Initialement, l'on marque $ s$, source du flot, et l'on cherche à progresser vers $ t$. L'algorithme se termine lorsque l'on ne peut pas marquer le sommet $ t$. Soit donc $ S$ l'ensemble des n\oeuds marqués. On pose tout naturellement : $ \bar{S}\:=\:X \,\backslash\, S$. Or, par construction : \begin{displaymath}
\left\{
\begin{array}{l@{\,\in\,}l}
s&S\\
t&\bar{S}
\end{array}
\right.
\end{displaymath}
\fbox{\begin{minipage}{\Mylen}
\centerline{Algorithme de Ford \& Fulkerson sous...
...ettre à jour $G(x)$\ \\
\hspace*{20pt}Fin Si\\
Fin Tant que
\end{minipage}}
donc, $ [S,\,\bar{S}]$ est une st-coupe. Si l'on n'a pas pu marquer $ t$ cela signifie que l'algorithme ne peut plus marquer de sommets de $ \bar{S}$ depuis $ S$. On en déduit donc que :

$\displaystyle r_{ij}=0 \quad \forall \: (i,\,j) \:$   tel que$\displaystyle \: i \: \in S \:$   et$\displaystyle \: j \: \in \: \bar{S}
$

or, par définition du graphe d'écart :

$\displaystyle r_{ij}=(u_{ij}-x_{ij})+x_{ji}
$

En outre, par définition d'un flot :

\begin{displaymath}
\left\{
\begin{array}{lll@{\geqslant 0}}
x_{ij} \leqslant...
...onc} & (u_{ij}-x_{ij}) \\
& & x_{ji}
\end{array}
\right.
\end{displaymath}

$ r_{ij}$ est donc une somme nulle de termes positifs ou nuls, ce qui signifie immédiatement que les deux termes sont nuls ! Donc :

\begin{displaymath}
\begin{array}{@{x_{ij}\,=\,}l@{\:\forall\: (i,\,j)\:\in\:}l...
...}\qquad & (S,\,\bar{S}) \\
0 & (\bar{S},\, S)
\end{array}
\end{displaymath}

or :

$\displaystyle v = \sum_{(i,\,j)\:\in\:(S,\,\bar{S})}x_{ij} - \sum_{(i,\,j)\:\in\:(\bar{S},\,
S)} x_{ij}
$

en appliquant $ x_{ij} = 0 \;\;\; \forall \: (i,\,j) \: \in \: (\bar{S},\,S)$ :

$\displaystyle v = \sum_{(i,\,j)\:\in\:(S,\,\bar{S})}x_{ij}
$

et comme $ x_{ij} = u_{ij} \;\;\; \forall \: (i,\,j) \: \in \: (S,\,\bar{S})$, on obtient finalement :

$\displaystyle v=\sum_{(i,\,j)\:\in\:(S,\,\bar{S})}u_{ij}
$

On est donc dans une situation où la valeur du flot est égale à la capacité de la coupe. Ce qui veut dire que nous sommes dans le cas flot max/coupe min. On a donc réussi ! Ce qui nous conduit au théorème suivant :
\begin{theo}[Condition d'optimalit\'e d'un flot maximal]
Le flot $x$\ est maxim...
...
r\'esiduel $G(x)$\ ne contient pas de chemin depuis $s$\ vers $t$.
\end{theo}
En effet, s'il existait un tel chemin, ce serait un chemin augmentant sur lequel on pourrait pousser du flot. Réciproquement, supposons que $ G(x)$ ne contienne pas de chemin. L'ensemble $ S$ des sommés marqués par l'algorithme de Ford & Fulkerson forme une st-coupe dont la capacité est égale au flot, d'où l'optimalité.
next up previous
suivant: Une amélioration possible monter: L'algorithme de Ford & précédent: Forme naïve de l'algorithme
Bruno Garcia 2000-12-17