4.6 Pro blèmes d’affec ta tion
141
© Dunod – Toute reproduction non autorisée est un délit.
Figure 4.32
Par suite, (O, A), (O, B), (O, C) et (Ο, E), d’une part, (a, S), (b, S), (c, S) et
(e, S), d’autre part, sont aussi satu rés. La procédure de marquage permet de marquer
seulement : O (+), D (+O), a (+D) et A (–a).
S n’est pas mar qué ; nous avons donc bien un flot maximal, ce qui veut dire que,
quels que soient les choix des zéros sur le tableau 4.3, nous n’arri ve rons pas à affec -
ter plus de quatre zéros.
Pour résoudre le pro blème, nous devons main te nant avoir recours à la méthode
hon groise.
Repre nons le tableau 4.4 où on a men tionné
éga le ment les zéros que nous avons dû éli mi ner
pour les choix ulté rieurs, par suite d’une affec ta -
tion d’un autre zéro sur la même ligne ou la même
colonne : ces zéros seront dits : zéros bar rés ; les
zéros affec tés seront dits : zéros enca drés. La
trans po si tion du mar quage de Ford- Fulkerson à
ce tableau (zéro « barré » : arc de flux nul ; zéro
« enca dré » : arc saturé) four nit (cf Tab. 4.5) :
a) mar quer 1 toute une ligne n’ayant pas de zéro
enca dré (ici la ligne D) ;
b) mar quer ensuite 1 toute colonne ayant un zéro
barré sur une ligne mar quée (ici la colonne a) ;
c) mar quer alors – toute ligne ayant un zéro enca -
dré dans une colonne mar quée (ici, la ligne A)
et reve nons à b), etc., jus qu’à ce que le mar quage
ne soit plus pos sible (c’est le cas, dès à présent,
dans l’exemple).
En effet, a) cor res pond à pra ti quer le mar quage
(1) pour les som mets x tels que l’arc (O, x) n’est pas
saturé : ici, seul (O, D) est dans ce cas : on a mar -
qué D ; b) cor res pond à pra ti quer le mar quage (1)
pour les som mets y tels qu’il existe un arc (x, y) non saturé, si x est déjà mar qué. Ici, seul
(D, a) est dans ce cas : a est mar qué 1 ; c) cor res pond à pra ti quer le mar quage (2) pour
A
B
C
D
E
a b c d e
0
0
0
0
0
0
0
Tableau 4.4
Tableau 4.5
A
B
C
D
E
a b c d e
0
0
0
0
0
0
0
141
© Dunod – Toute reproduction non autorisée est un délit.
Figure 4.32
Par suite, (O, A), (O, B), (O, C) et (Ο, E), d’une part, (a, S), (b, S), (c, S) et
(e, S), d’autre part, sont aussi satu rés. La procédure de marquage permet de marquer
seulement : O (+), D (+O), a (+D) et A (–a).
S n’est pas mar qué ; nous avons donc bien un flot maximal, ce qui veut dire que,
quels que soient les choix des zéros sur le tableau 4.3, nous n’arri ve rons pas à affec -
ter plus de quatre zéros.
Pour résoudre le pro blème, nous devons main te nant avoir recours à la méthode
hon groise.
Repre nons le tableau 4.4 où on a men tionné
éga le ment les zéros que nous avons dû éli mi ner
pour les choix ulté rieurs, par suite d’une affec ta -
tion d’un autre zéro sur la même ligne ou la même
colonne : ces zéros seront dits : zéros bar rés ; les
zéros affec tés seront dits : zéros enca drés. La
trans po si tion du mar quage de Ford- Fulkerson à
ce tableau (zéro « barré » : arc de flux nul ; zéro
« enca dré » : arc saturé) four nit (cf Tab. 4.5) :
a) mar quer 1 toute une ligne n’ayant pas de zéro
enca dré (ici la ligne D) ;
b) mar quer ensuite 1 toute colonne ayant un zéro
barré sur une ligne mar quée (ici la colonne a) ;
c) mar quer alors – toute ligne ayant un zéro enca -
dré dans une colonne mar quée (ici, la ligne A)
et reve nons à b), etc., jus qu’à ce que le mar quage
ne soit plus pos sible (c’est le cas, dès à présent,
dans l’exemple).
En effet, a) cor res pond à pra ti quer le mar quage
(1) pour les som mets x tels que l’arc (O, x) n’est pas
saturé : ici, seul (O, D) est dans ce cas : on a mar -
qué D ; b) cor res pond à pra ti quer le mar quage (1)
pour les som mets y tels qu’il existe un arc (x, y) non saturé, si x est déjà mar qué. Ici, seul
(D, a) est dans ce cas : a est mar qué 1 ; c) cor res pond à pra ti quer le mar quage (2) pour
A
B
C
D
E
a b c d e
0
0
0
0
0
0
0
Tableau 4.4
Tableau 4.5
A
B
C
D
E
a b c d e
0
0
0
0
0
0
0