next up previous contents index
Next: Automates finis Up: Algorithmes Previous: Ordonnancement de projet

Réseaux de transport

Certains problèmes de transport (de marchandises, de fluides, d'énergie, etc) dans un réseau (routier, de distribution, etc) sont représentables de façon naturelle par des graphes dont les sommets sont des points de passage (sans stockage) et les arcs des trajets entre ces points. Le problème consiste à maximiser l'utilisation de tels réseaux, c'est-à-dire à calculer la quantité maximale transportable compte tenu des contraintes. Ce problème a bien d'autres réalisations, par exemple pour déterminer un appariement maximum dans un graphe biparti.

On modélise un réseau  de transport à l'aide d'un graphe $\mathcal{G} = (S, A)$, muni d'une fonction de capacité $c :
S\times S \to \mathbf{N}$, telle que c(x,y)=0 si $(x,y)\notin A$. On suppose qu'un sommet source s et un sommet puits t ont été désignés (figure 2.22).


 \begin{figurette}% latex2html id marker 5731
\begin{center}
\leavevmode
\fbox{...
...ption{Un réseau de transport $(\mathcal{G}, c)$ .}
\end{center} \end{figurette}

On appelle flot une fonction $f:S\times S \to\mathbf{Z}$ telle que (contraintes de capacité et de conservation, Cf. les lois de Kirchhoff) :

1.
quels que soient x, $y\in S$, $f(x,y)\le c(x,y)$
2.
quels que soient x, $y\in S$, f(x,y) = -f(y,x)
3.
quel que soit $x\neq s, t$, $\sum_{y\in S}f(x,y) = 0$
Un flot est représenté sur la figure 2.23 par la notation f(x,y) / c(x,y) en étiquette des arcs. La valeur du flot fest le nombre $\vert f\vert = \sum_{y\in S} f(s,y)$, qui est aussi égal à $\sum_{x\in S} f(x,t)$ ; elle mesure la quantité totale transportée par le flot depuis la source vers le puits. Un arc est saturé par le flot s'il est utilisé au maximum de sa capacité, c'est-à-dire si f(x,y) = c(x,y).


 \begin{figurette}% latex2html id marker 5740
\begin{center}
\leavevmode
\fbox{...
...aturés par $f$ , mais ce flot n'est pas
maximal.}
\end{center} \end{figurette}

Le problème est de déterminer un flot de valeur maximale. Sa résolution fait appel à la notion de réseau résiduel d'un flot. Étant donné un réseau de graphe $\mathcal{G} = (S, A)$ et de capacité c et un flot f, on définit cf(x,y) = c(x,y) - f(x,y), pour $(x,y)\in S\times S$; le réseau résiduel de f est défini par le graphe $\mathcal{G}_f = (S, A_f)$ dont l'ensemble des arcs est $A_f =
\{(x,y)\in S\times S ; c_f(x,y)>0\}$, et par la capacité cf(figure 2.24) ; on notera que Af n'est pas nécessairement inclus dans A, car il peut contenir aussi l'arc réciproque d'un arc de A.


 \begin{figurette}% latex2html id marker 5749
\begin{center}
\leavevmode
\fbox{...
... arcs en italique ; ce
chemin est de capacité 6.}
\end{center} \end{figurette}

Un chemin d'augmentation de f dans un réseau est un chemin simple (c'est-à-dire sans boucle) de s vers t dans le graphe résiduel $\mathcal{G}_f$. La capacité d'un chemin p est la quantité c(p) maximale transportable le long de p, soit $c(p) = \min
\{c_f(x,y) ; (x,y) \in p \}$. Un chemin d'augmentation permet d'augmenter f en définissant le flot noté f+p(figure 2.25) :

\begin{eqnarray*}(f+p)(x,y) &= &f(x,y) + c(p) \quad\mbox{si } (x,y)\in p\\
(f+p...
...\mbox{si } (y,x)\in p\\
(f+p)(x,y) &= &f(x,y) \quad\mbox{sinon}
\end{eqnarray*}


Il s'agit bien d'un flot et c'est une augmentation de f au sens où |f+p|>|f|.


 \begin{figurette}% latex2html id marker 5760
\begin{center}
\leavevmode
\fbox{...
...e $s$\space vers $t$ . Le flot
est donc maximal.}
\end{center} \end{figurette}

On montre alors qu'un flot est maximal si et seulement si son graphe résiduel ne contient aucun chemin d'augmentation. L'algorithme de Ford-Fulkerson (1956) consiste à augmenter le flot selon un chemin d'augmentation s'il en existe :

   

Il faut choisir une structure de données adéquate ; on notera que les graphes résiduels partagent le même ensemble de sommets, mais que l'ensemble des arcs est variable. Correctement implémenté, cet algorithme a une complexité en O(|S| |A|2).


next up previous contents index
Next: Automates finis Up: Algorithmes Previous: Ordonnancement de projet
R. Lalement
2000-10-23