Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
130
Cer tains arcs u sont tels que w1 u 2 5 c 1 u2 : on dit qu’ils sont « satu rés » ; plus
bas (fig 4.22 à 4.24) ils sont tra cés en trait gras épais. Les autres sont une « capa cité
rési duelle » : c 1 u2 2 w1 u 2 , non nulle.
Don nons la défi
ni tion sui vante : une chaîne amé lio rante est une chaîne élé men -
taire m 5 1 x 1 , c , x p 2 d’ori gine O 5 x 1 et d’extré mité P 5 x p , telle que aucun arc
direct (un arc direct
1
est un arc (x i , x i 1 1 ) de la chaîne tel que l’arc (x i , x i 1 1 ) est un
arc du graphe, alors que pour un arc indi rect de la chaîne, c’est l’arc de sens opposé
(x i 1 1 , x i ) qui est un arc du graphe) de cette chaîne ne soit saturé (la quan
tité de flux
asso ciée est stric te ment infé rieure à la capa cité de l’arc) et que les flux des arcs indi
rects soient stric te ment posi tifs. L’algo rithme de Ford- Fulkerson est alors :
1. tant qu’il existe m, une chaîne amé lio rante, faire
2. aug men ter le flux sur m
En fait, Ford et Fulkerson ont donné une pro cé dure de mar quage permetttant de
trou ver une chaîne amé lio rante m (si elle existe) : nous la détaillons plus bas.
On mon trera aussi plus loin que, lors qu’il n’existe plus de chaîne amé lio rante, le
flot est opti mal (de valeur maximale).
L’opé ra
tion consis tant à aug
men ter le flux sur une chaîne améliorante C s’énonce
de la manière sui vante :
1. cal cu ler d
1 5 min 5c u 2 w u 6, où u est un arc direct de C ; nécessairement :
d
1 . 0 car aucun arc direct n’est saturé.
2. cal cu ler d
2 5 min 5w u 6, où u est un arc indi rect de C ; nécessairement : d
2 . 0
car aucun arc indirect n’a son flux nul.
3. poser d 5 min 5d
1
, d
2
6 ; nécessairement : d . 0 car d
1
et d
2
sont positifs.
4. pour tout arc direct u faire : w u d w u 1 d
5. pour tout arc indi rect u faire : w u d w u 2 d
La pro cé dure de mar quage sui vante, due à Ford et Fulkerson, per met de déter mi -
ner une chaîne amé
lio rante si le flot courant n’est pas optimal :
1. ini tia le ment la source Ο est « mar quée » du signe 1 et les autres som mets sont
« non mar qués »
2. tant que cela est pos sible, choi sir un som met x non mar qué véri fiant l’une des
deux défi
ni tions 3 ou 4 sui vantes :
3. si y est extrémité initiale d’un arc (x, y) tel que x est déjà marqué et y non marqué,
avec φ (x,y) < c (x,y) , c’est-à-dire que (x, y) est non saturé, marquer +x le sommet y
4. si x est extrémité initiale d’un arc (x, y) tel que y est déjà marqué et x non
marqué, avec φ (x,y) > 0, c’est-à-dire de flux non nul, marquer −y le sommet x
5. En fin de marquage : si le puits p est marqué, alors le flot courant est améliorable.
Si le puits p n’est pas mar qué, il n’existe pas de chaîne amé lio rante et le flot
courant est opti mal.
1. Autre ment dit, si l’on par court la chaîne de Ο vers P, les arcs directs sont par cou rus dans le sens
de leur orien ta tion, tan dis que les arcs indi rects (ou « rétro grades ») sont par cou rus en sens inverse
de leur orien ta tion.
130
Cer tains arcs u sont tels que w1 u 2 5 c 1 u2 : on dit qu’ils sont « satu rés » ; plus
bas (fig 4.22 à 4.24) ils sont tra cés en trait gras épais. Les autres sont une « capa cité
rési duelle » : c 1 u2 2 w1 u 2 , non nulle.
Don nons la défi
ni tion sui vante : une chaîne amé lio rante est une chaîne élé men -
taire m 5 1 x 1 , c , x p 2 d’ori gine O 5 x 1 et d’extré mité P 5 x p , telle que aucun arc
direct (un arc direct
1
est un arc (x i , x i 1 1 ) de la chaîne tel que l’arc (x i , x i 1 1 ) est un
arc du graphe, alors que pour un arc indi rect de la chaîne, c’est l’arc de sens opposé
(x i 1 1 , x i ) qui est un arc du graphe) de cette chaîne ne soit saturé (la quan
tité de flux
asso ciée est stric te ment infé rieure à la capa cité de l’arc) et que les flux des arcs indi
rects soient stric te ment posi tifs. L’algo rithme de Ford- Fulkerson est alors :
1. tant qu’il existe m, une chaîne amé lio rante, faire
2. aug men ter le flux sur m
En fait, Ford et Fulkerson ont donné une pro cé dure de mar quage permetttant de
trou ver une chaîne amé lio rante m (si elle existe) : nous la détaillons plus bas.
On mon trera aussi plus loin que, lors qu’il n’existe plus de chaîne amé lio rante, le
flot est opti mal (de valeur maximale).
L’opé ra
tion consis tant à aug
men ter le flux sur une chaîne améliorante C s’énonce
de la manière sui vante :
1. cal cu ler d
1 5 min 5c u 2 w u 6, où u est un arc direct de C ; nécessairement :
d
1 . 0 car aucun arc direct n’est saturé.
2. cal cu ler d
2 5 min 5w u 6, où u est un arc indi rect de C ; nécessairement : d
2 . 0
car aucun arc indirect n’a son flux nul.
3. poser d 5 min 5d
1
, d
2
6 ; nécessairement : d . 0 car d
1
et d
2
sont positifs.
4. pour tout arc direct u faire : w u d w u 1 d
5. pour tout arc indi rect u faire : w u d w u 2 d
La pro cé dure de mar quage sui vante, due à Ford et Fulkerson, per met de déter mi -
ner une chaîne amé
lio rante si le flot courant n’est pas optimal :
1. ini tia le ment la source Ο est « mar quée » du signe 1 et les autres som mets sont
« non mar qués »
2. tant que cela est pos sible, choi sir un som met x non mar qué véri fiant l’une des
deux défi
ni tions 3 ou 4 sui vantes :
3. si y est extrémité initiale d’un arc (x, y) tel que x est déjà marqué et y non marqué,
avec φ (x,y) < c (x,y) , c’est-à-dire que (x, y) est non saturé, marquer +x le sommet y
4. si x est extrémité initiale d’un arc (x, y) tel que y est déjà marqué et x non
marqué, avec φ (x,y) > 0, c’est-à-dire de flux non nul, marquer −y le sommet x
5. En fin de marquage : si le puits p est marqué, alors le flot courant est améliorable.
Si le puits p n’est pas mar qué, il n’existe pas de chaîne amé lio rante et le flot
courant est opti mal.
1. Autre ment dit, si l’on par court la chaîne de Ο vers P, les arcs directs sont par cou rus dans le sens
de leur orien ta tion, tan dis que les arcs indi rects (ou « rétro grades ») sont par cou rus en sens inverse
de leur orien ta tion.