next up previous
suivant: Démonstration du théorème Flot monter: L'algorithme de Ford & précédent: L'algorithme de Ford &

Capacité résiduelle dans le cas général

Dans le cas simple où l'on exclue le fait que les arcs $ (i,\,j)$ et $ (j,\,i)$ soient présents simultanément, la capacité résiduelle de l'arc $ (i,\,j)$ s'écrit :

$\displaystyle r_{ij}=u_{ij}-x{ij}
$

Dans le cas général, on peut étendre cette définition en prenant en compte la valeur du flot passant sur l'arc opposé, soit :

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

En effet, il est toujours possible de ``gagner'' du flot dans le sens $ i\rightarrow j$ en retirant le flot présent sur l'arc $ (j,\,i)$.

Bruno Garcia 2000-12-17