Graphe d'écart et flot

[Rockleader]

Bonsoir,

j'aimerais un coup de main pour la compréhension d'un point de mon cours.

J'ai compris comment trouver à partir d'un flot compatible, le flot maximum d'un réseau de transport en utilisant l'algo de marquage de Ford Fulkersson.

--> On en arrive donc à la partie sur laquelle j'ai besoin d'aide.

Mon cours définis alors la notion de Graphe d'écart Gr(F)=(X,U_F,r_F) associant un réseau de transport et un flot.

Avec X l'ensemble des sommets communs flot et au réseau donc.
U_F l'ensemble des arc du flot
r_F La capacité résiduelle du flot. (La valeur donc on peut augmenter ou diminuer le flot) définit telle que:

Pour un arc (x,y)
Augmentation: r+(x,y) = capacité(x,y)-Flux(x,y)
Diminution : r-(x,y) = Flux(x,y)


Tout arcs du réseaux induit l'une de ses deux règles

- (x,y) appartient à U_F si Flux(x,y) <= capacité (x,y)
-(y,x) appartint à U_F si Flux(y,x) > 0

Mon cours me dit alors que l'on peut utiliser le graphe d'écart pour trouver le flot maximum à partir d'un flot compatible au lieu de la méthode Ford Fulkersson par marquage dont j'ai parlé plus haut.

En revanche je n'ai absolument pas compris ni pourquoi ni comment.

Un exemple serait apprécié.

Merci à vous !