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 nuds marqués. On pose tout naturellement : $\bar{S}\:=\:X \,\backslash\, S$. Or, par construction : $$\left\{ \begin{array}{l@{\,\in\,}l} s&S\\ t&\bar{S} \end{array} \right.$$

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 :

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

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

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

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

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

$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{array}{@{x_{ij}\,=\,}l@{\:\forall\: (i,\,j)\:\in\:}l... ...}\qquad & (S,\,\bar{S}) \\ 0 & (\bar{S},\, S) \end{array}$$

or :

$$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)$ :

$$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 :

$$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 :

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