Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
138
Figure 4.28 Réseau de transport et flot f
(0) de valeur 30
Figure 4.29 Graphe d’écart G
e
1f
102 2.
G
e
1 f
102
2 com porte un (seul) che min m de s vers p : m 5 1 s, A, C, B, D, p2 ; on a :
e 5 min1 10, 5, 10, 102 5 5. La valeur du flot va donc être aug    men    tée de 5 uni    tés.
Voici le nou veau graphe d’écart G
e
1 f
112
2 , il ne com porte pas de che min de s à p :
le flot asso    cié f
(1)
est donc opti mal, il est valeur v
* 5 35.
On nomme désor mais S l’ensemble des som mets qu’on peut atteindre depuis s
par des che mins ; ici S 5 5s, A, C6 ; S  est  aussi  l'ensemble  des  sommets  marqués 
quand on applique la procédure de marquage de Ford­Fulkerson au flot f
(1)
.
Figure 4.30 Graphe d’écart G
e
1f
112 2.
avec le cocircuit (S, S) en pointillé