4.6 Pro blèmes d’affec ta tion
143
© Dunod – Toute reproduction non autorisée est un délit.
Nous n’avons pas l’inten tion de démon trer ici la vali dité de l’algo rithme, mais
le lec teur sera sûre ment inté ressé de consta ter que la colonne rayée cor res pond au
som met mar qué (1D) , soit a, et que les lignes non rayées cor res pondent éga le ment
aux som mets mar qués (2a) et (1O), soient A et D (figure 4.33), d’après le mar quage
réa lisé à par tir de la figure 4.32.
Figure 4.33
Figure 4.34
La figure 4.34 pré sente la situa tion de telle sorte qu’il est visible que, pour
résoudre le pro blème, il importe de trou ver l’arc de moindre coût (ou un arc de
moindre coût) entre l’ensemble des som mets mar qués du pre mier niveau, soit Χ M , et
l’ensemble des som mets non mar qués du second niveau, soit Y M : on vise à effec tuer
une aug men ta tion du flot en uti li sant cet arc (ou l’un de ces arcs) par une progression
du marquage.
En regrou pant le tableau des coûts sous la forme cor res pon dant à la figure 4.34,
on obtient le tableau 4.8. On voit que l’on ne change rien à la situa tion exis tant entre
les sommets mar qués si l’on sous trait le plus petit élé ment des élé ments non rayés
de la matrice et si on l’ajoute aux élé ments
rayés deux fois. En effet, dans les cases
(A, a) et (D, a), le coût demeu rera 0.
Mais on crée ainsi quatre arcs de coût
zéro entre l’ensemble des som mets mar -
qués du pre mier niveau et l’ensemble des
som mets non mar qués du second niveau ;
ce sont les arcs : (A, b) ; (A, d) ; (D, b) ;
(D, e).
Les échanges concernant le flot les plus
simples sont les sui vants (au choix) :
1) faire cir cu ler un flux satu rant de 1 sur
(A, d), satu rant (d, S) ; faire cir cu ler un flux
satu rant de 1 sur (O, D) et satu rer (D, a) ;
Tableau 4.8
A
XM
YM
X M
D
B
C
E
a b c d e
0 1 2 1 2
0 1 2 2 1
0 3 1 2 0
2 1 0 2 1
1 0 3 0 2
1
1
1
Y M
143
© Dunod – Toute reproduction non autorisée est un délit.
Nous n’avons pas l’inten tion de démon trer ici la vali dité de l’algo rithme, mais
le lec teur sera sûre ment inté ressé de consta ter que la colonne rayée cor res pond au
som met mar qué (1D) , soit a, et que les lignes non rayées cor res pondent éga le ment
aux som mets mar qués (2a) et (1O), soient A et D (figure 4.33), d’après le mar quage
réa lisé à par tir de la figure 4.32.
Figure 4.33
Figure 4.34
La figure 4.34 pré sente la situa tion de telle sorte qu’il est visible que, pour
résoudre le pro blème, il importe de trou ver l’arc de moindre coût (ou un arc de
moindre coût) entre l’ensemble des som mets mar qués du pre mier niveau, soit Χ M , et
l’ensemble des som mets non mar qués du second niveau, soit Y M : on vise à effec tuer
une aug men ta tion du flot en uti li sant cet arc (ou l’un de ces arcs) par une progression
du marquage.
En regrou pant le tableau des coûts sous la forme cor res pon dant à la figure 4.34,
on obtient le tableau 4.8. On voit que l’on ne change rien à la situa tion exis tant entre
les sommets mar qués si l’on sous trait le plus petit élé ment des élé ments non rayés
de la matrice et si on l’ajoute aux élé ments
rayés deux fois. En effet, dans les cases
(A, a) et (D, a), le coût demeu rera 0.
Mais on crée ainsi quatre arcs de coût
zéro entre l’ensemble des som mets mar -
qués du pre mier niveau et l’ensemble des
som mets non mar qués du second niveau ;
ce sont les arcs : (A, b) ; (A, d) ; (D, b) ;
(D, e).
Les échanges concernant le flot les plus
simples sont les sui vants (au choix) :
1) faire cir cu ler un flux satu rant de 1 sur
(A, d), satu rant (d, S) ; faire cir cu ler un flux
satu rant de 1 sur (O, D) et satu rer (D, a) ;
Tableau 4.8
A
XM
YM
X M
D
B
C
E
a b c d e
0 1 2 1 2
0 1 2 2 1
0 3 1 2 0
2 1 0 2 1
1 0 3 0 2
1
1
1
Y M