Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
108
Figure 4.8 L'arbo res cence des plus courts che mins d’ori gine A est donnée par les arcs en
traits doubles
Figure 4.9 Un graphe com por tant un cir cuit absor bant
Mon trons que l’algo rithme de Ford, qui est évi dem ment fini en l’absence de cir
cuit absor bant, donne néces sai re ment un che min de valeur mini male. En effet, soit
un che min quel conque m 5 (X 0 , X k , , X k , 2 1 , c , X k 1 , X n 2 1 ) de X 0 à X n21 , on a avec
les l i obtenus en fin d'application de l'algorithme :
l k , 2 0 < v(X 0 , X k , )
l k , 2 1 2 l k , < v(X k , , X k , 2 1 )
. . . . . . . . . . . . . . . . . . . . . . . .
l n 2 1 2 l k 1 < v (X k 1 , X n 2 1 ),
d’où, en addi tion nant membre à membre :
l n21 < v(X 0 , X k , ) 1 v(X k , , X k , 2 1 ) 1 c 1 v1 X k 1 , X n21 2 :
la valeur du che min m est supé rieure ou égale à celle du che min m
*
déter miné par
l’algo rithme de Ford qui est l n21 ; m étant un che min quel conque de X 0 à X n21 , on en
déduit que m
*
est un che min de valeur mini male de X 0 à X n21 .
La com plexité de l’algo rithme de Ford est O1 2
n
2 . Cet algo rithme n’est donc pas poly -
no mial ; cepen dant en ordon nant la manière dont les arcs sont trai tés, des algo rithmes
poly no miaux peuvent en être direc te ment déri vés. Le lec teur pourra obte nir les preuves
108
Figure 4.8 L'arbo res cence des plus courts che mins d’ori gine A est donnée par les arcs en
traits doubles
Figure 4.9 Un graphe com por tant un cir cuit absor bant
Mon trons que l’algo rithme de Ford, qui est évi dem ment fini en l’absence de cir
cuit absor bant, donne néces sai re ment un che min de valeur mini male. En effet, soit
un che min quel conque m 5 (X 0 , X k , , X k , 2 1 , c , X k 1 , X n 2 1 ) de X 0 à X n21 , on a avec
les l i obtenus en fin d'application de l'algorithme :
l k , 2 0 < v(X 0 , X k , )
l k , 2 1 2 l k , < v(X k , , X k , 2 1 )
. . . . . . . . . . . . . . . . . . . . . . . .
l n 2 1 2 l k 1 < v (X k 1 , X n 2 1 ),
d’où, en addi tion nant membre à membre :
l n21 < v(X 0 , X k , ) 1 v(X k , , X k , 2 1 ) 1 c 1 v1 X k 1 , X n21 2 :
la valeur du che min m est supé rieure ou égale à celle du che min m
*
déter miné par
l’algo rithme de Ford qui est l n21 ; m étant un che min quel conque de X 0 à X n21 , on en
déduit que m
*
est un che min de valeur mini male de X 0 à X n21 .
La com plexité de l’algo rithme de Ford est O1 2
n
2 . Cet algo rithme n’est donc pas poly -
no mial ; cepen dant en ordon nant la manière dont les arcs sont trai tés, des algo rithmes
poly no miaux peuvent en être direc te ment déri vés. Le lec teur pourra obte nir les preuves