206
Recherche opérationnelle
Le flot au jugé (les traits doubles représentent les arcs satures)
Appliquons maintenant le marquage de Ford-Fulkerson en précisant ce marquage de la
façon suivante (pour savoir à partir de quel sommet un sommet donné a été marqué).
Si est marqué à partir de parceque
alors sera marqué par
Si est marqué à partir de parceque :
, alors sera marqué par
On obtient alors le marquage suivant :
(on omet ici les marquages inutiles, c'est-à-dire ceux consistant à marquer parce que
est marqué avec
puis à remarquer parce que
.
On voit que l'on marque , donc que le flot n'est pas optimal; on marque à partir de
plusieurs chaînes possibles. Prenons-en une :
A
B
C
D
E
F
G
H
J
I
K
2
1
0
1
3
5
3
2
0
5
2
3
1
2
4
1
0
3
5
A
B
C
D
E
F
G
H
J
I
K
2
1
0
1
3
5
3
2
0
3
5
5
2
3
1
2
4
1
0
+A
+A
-G
+C
+B
+G
+B
+E
+F
+I
+D
+I
+J
+C
A
C
D
G
I
K
[9]
[4]
[3]
[5]
[6]
3
3
2
3
5