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 :

• d'ajouter encore jusqu'à $u_{ij}-x_{ij}$ unités de flot depuis $i$ vers $j$.
• de retirer jusqu'à $x_{ij} - l_{ij}$ unités de flot depuis $i$ vers $j$, ce qui peut ête vu comme l'ajout d'autant d'unités de flot depuis $j$ vers $i$.

Le graphe d'écart $G(x)$ va donc proposer deux arcs mettant en avant ces deux possibilités :

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

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.