next up previous
suivant: La notion de coupe monter: Quelques techniques utilisées sur précédent: Quelques techniques utilisées sur

Le graphe d'écart

Lorsque l'on travaille sur les flots, il est souvent intéressant d'utiliser un graphe spécial, dérivé du graphe initial, nommé graphe d'écart et noté $ G(x) = (X, E(x))$. Soit $ (\ivj)$ un arc de $ G$ de capacités minimale et maximale respectives $ l_{ij}$ et $ u_{ij}$ et portant le flot $ x_{ij}$. Il est alors possible soit : Le graphe d'écart $ G(x)$ va donc proposer deux arcs mettant en avant ces deux possibilités :

\begin{displaymath}
\begin{array}{llll}
(i,\,j) & \text{de capacit\'e r\'esidu...
... = x_{ij} & \text{arc
opposé de $(i,\,j)$}\\
\end{array}
\end{displaymath}

En outre, seuls les arcs de capacité résiduelle non nulle sont présents dans le graphe d'écart. Notez le cas intéressant où $ l_{ij} = u_{ij}$. Nécessairement, tout flot compatible est tel que $ x_{ij} = l_{ij} = u_{ij}$. Alors, le graphe d'écart ne contient ni l'arc $ (i,\,j)$, ni l'arc $ (j,\,i)$ car ils ont tous deux une capacité résiduelle nulle.

Bruno Garcia 2000-12-17