4.4 Pro blème du flot de valeur maximale
131
© Dunod – Toute reproduction non autorisée est un délit.
Inver se ment, il est aisé de démon trer, en se repor tant à la défi ni tion d’une chaîne
amé lio rante, qu’une chaîne amé lio rante existe si et seule ment si le som met Ρ est mar -
qué. Une telle chaîne est obte nue, à l’issue de l’application de la procédure de mar -
quage, en remont aut le marguage récur si ve ment depuis P jus qu’au som met O.
Appli quons l’algo rithme à notre exemple ; il est facile d’obte nir un flot ini tial ; nous
repre nons celui de la figure pré
cé dente, en indi
quant les arcs satu
rés par un trait gras.
Figure 4.22 Mar quage des som mets
On peut remar quer que l’on ne peut pas amé lio rer trivialement la valeur du flot
courant : tout che min de O vers P com por tant au moins un arc saturé (on dit alors
que le flot est « com plet »).
Appli quons la pro cé dure de mar quage des som mets : l’ini tia li sation consiste à mar -
quer O d’un 1 ; puis A, extré mité ter mi nale de l’arc (Ο, A), non saturé, est mar qué du
signe 1O ; E, extré mité ter mi nale de l’arc (A, E), non saturé, est mar qué 1A ; B, extré -
mité ini tiale de l’arc (B, E), tran spor tant un flot non nul, est mar qué 2E ; D, extré mité
ter mi nale de l’arc (B, D), non saturé, est mar qué 1B ; enfin, P, extré mité ter mi nale de
l’arc non saturé (D, P), est mar qué 1D : le flot cou rant n’est donc pas un flot de valeur
maximale.
Consi dé rons alors la chaîne amé lio rante [O, A, E, B, D, P] : on l’obtient à par tir
du puits Ρ en remon tant le chaî nage arrière contenue dans les marques. En effet p(P)
5 D, puis p(D) 5 B, puis p(B) 5 E, puis p(E) 5A et enfin p(A) 5 O, où p(Y ) est le
prédécesseur de Y sur la chaîne améliorante.
Figure 4.23 Chaîne amé lio rante
131
© Dunod – Toute reproduction non autorisée est un délit.
Inver se ment, il est aisé de démon trer, en se repor tant à la défi ni tion d’une chaîne
amé lio rante, qu’une chaîne amé lio rante existe si et seule ment si le som met Ρ est mar -
qué. Une telle chaîne est obte nue, à l’issue de l’application de la procédure de mar -
quage, en remont aut le marguage récur si ve ment depuis P jus qu’au som met O.
Appli quons l’algo rithme à notre exemple ; il est facile d’obte nir un flot ini tial ; nous
repre nons celui de la figure pré
cé dente, en indi
quant les arcs satu
rés par un trait gras.
Figure 4.22 Mar quage des som mets
On peut remar quer que l’on ne peut pas amé lio rer trivialement la valeur du flot
courant : tout che min de O vers P com por tant au moins un arc saturé (on dit alors
que le flot est « com plet »).
Appli quons la pro cé dure de mar quage des som mets : l’ini tia li sation consiste à mar -
quer O d’un 1 ; puis A, extré mité ter mi nale de l’arc (Ο, A), non saturé, est mar qué du
signe 1O ; E, extré mité ter mi nale de l’arc (A, E), non saturé, est mar qué 1A ; B, extré -
mité ini tiale de l’arc (B, E), tran spor tant un flot non nul, est mar qué 2E ; D, extré mité
ter mi nale de l’arc (B, D), non saturé, est mar qué 1B ; enfin, P, extré mité ter mi nale de
l’arc non saturé (D, P), est mar qué 1D : le flot cou rant n’est donc pas un flot de valeur
maximale.
Consi dé rons alors la chaîne amé lio rante [O, A, E, B, D, P] : on l’obtient à par tir
du puits Ρ en remon tant le chaî nage arrière contenue dans les marques. En effet p(P)
5 D, puis p(D) 5 B, puis p(B) 5 E, puis p(E) 5A et enfin p(A) 5 O, où p(Y ) est le
prédécesseur de Y sur la chaîne améliorante.
Figure 4.23 Chaîne amé lio rante