Méthode de recherche d'un flot maximum
Dans une première phase, on marque les sommets successivement en partant de la
source s. Cette phase se termine lorsque le terminal t reçoit une marque ou bien
lorsqu’aucun sommet ne peut plus recevoir de marque.
Si t a été marqué, on a trouvé un chemin γ non saturé de s à t :
® on augmente alors le flot de la quantité p(γ), minimum des marques p v , où v
parcourt les sommets de γ : on a donc simplement p(γ) = p t .
® On supprime ensuite toutes les marques sauf celle de s, puis on recommence le
marquage.
® S’il n’y a plus de sommet à marquer et si t n’a pas été marqué, le flot est maximum, du moins dans le cas où les capacités ont des valeurs entières : dans ce cas
en effet, le flot augmente, à partir du flot nul, par valeurs entières, donc la valeur
des flots successifs finit par être stationnaire.
Algorithme du flot maximum. On suppose que les capacités sont des entiers
positifs ou nuls.
I) Trouver un flot dans le graphe G (on peut prendre f (α) = 0 pour tout arc α) et
donner à s la marque (−, ∞).
II) Marquer les sommets successivement jusqu’à ce que t soit marqué ou bien qu’il
n’y ait plus de sommet marquable. Si t est marqué, aller en (III) ; sinon aller en (V).
III) Poser v = t et p = p t . Tant que v = s faire :
i) si la marque de v contient u
+ , alors f (u, v) ← f (u, v) + p ;
ii) si la marque de v contient u
− , alors f (v, u) ← f (v, u) − p ;
iii) v ← u.
IV) Supprimer toutes les marques sauf celle de s et aller en (II).
V) Fin de l’algorithme : le flot est maximum.
Exemple. Appliquons l’algorithme à l’exemple précédent. Le graphe est celui de
la figure 1 reproduite ci-dessous
a
b
c
d
t
s
(1, 0)
(1, 0)
(2, 0)
(3, 0)
(3, 0)
(4, 0)
(4, 0)
(4, 0)
(5, 0)
On marque la source s par (−, ∞) et l’on part du flot nul.
a) On peut marquer successivement les sommets c, a, b et t (phase II) :
90 – GRAPHES
Dans une première phase, on marque les sommets successivement en partant de la
source s. Cette phase se termine lorsque le terminal t reçoit une marque ou bien
lorsqu’aucun sommet ne peut plus recevoir de marque.
Si t a été marqué, on a trouvé un chemin γ non saturé de s à t :
® on augmente alors le flot de la quantité p(γ), minimum des marques p v , où v
parcourt les sommets de γ : on a donc simplement p(γ) = p t .
® On supprime ensuite toutes les marques sauf celle de s, puis on recommence le
marquage.
® S’il n’y a plus de sommet à marquer et si t n’a pas été marqué, le flot est maximum, du moins dans le cas où les capacités ont des valeurs entières : dans ce cas
en effet, le flot augmente, à partir du flot nul, par valeurs entières, donc la valeur
des flots successifs finit par être stationnaire.
Algorithme du flot maximum. On suppose que les capacités sont des entiers
positifs ou nuls.
I) Trouver un flot dans le graphe G (on peut prendre f (α) = 0 pour tout arc α) et
donner à s la marque (−, ∞).
II) Marquer les sommets successivement jusqu’à ce que t soit marqué ou bien qu’il
n’y ait plus de sommet marquable. Si t est marqué, aller en (III) ; sinon aller en (V).
III) Poser v = t et p = p t . Tant que v = s faire :
i) si la marque de v contient u
+ , alors f (u, v) ← f (u, v) + p ;
ii) si la marque de v contient u
− , alors f (v, u) ← f (v, u) − p ;
iii) v ← u.
IV) Supprimer toutes les marques sauf celle de s et aller en (II).
V) Fin de l’algorithme : le flot est maximum.
Exemple. Appliquons l’algorithme à l’exemple précédent. Le graphe est celui de
la figure 1 reproduite ci-dessous
a
b
c
d
t
s
(1, 0)
(1, 0)
(2, 0)
(3, 0)
(3, 0)
(4, 0)
(4, 0)
(4, 0)
(5, 0)
On marque la source s par (−, ∞) et l’on part du flot nul.
a) On peut marquer successivement les sommets c, a, b et t (phase II) :
90 – GRAPHES