Problèmes de flots
205
avec tous les arcs noirs dans le même sens et tous les arcs verts dans le sens contraire,
on améliore le flot en changeant les flux sur les arcs du cycle. Si l'on ne trouve pas de tel
cycle, on est arrivé au flot optimal.
Plus précisément, la recherche du cycle améliorant se fait grâce au marquage de Minty.
marqué, noir
on marque ,
marqué, vert
on marque ,
ou marqué, rouge
, on marque ou ,
Si l'on marque , c'est qu'on a obtenu un cycle améliorant.
Remarquons qu'on peut simplifier la procédure de marquage :
marqué,
on marque (arc noir ou rouge),
marqué, (Ø(ij)>0) on marque (arc vert ou rouge).
L'algorithme de Ford-Fulkerson est alors :
a) Faire passer un flot au jugé (c'est toujours possible : le flot nul est un flot réalisable)
b) Appliquer sur ce flot le marquage de Ford-Fulkerson : marqué.
Si marqué,
on marque .
Si marqué, et
on marque .
c) si on trouve un cycle de sommets marqués on peut améliorer le flot en augmentant le
flot sur les arcs parcourus dans le sens ( ) et en diminuant le flot sur les arcs parcourus
dans le sens contraire, et cela d'une même quantité. On retourne alors en b).
d) si on ne trouve pas de tel cycle, le flot est optimal.
Appliquons cet algorithme sur le graphe suivant, où on a omis l'arc de retour. La
première figure (figure 1) donne les capacités, la figure suivante (figure 2) un flot au
jugé.
Les capacités
A
B
C
D
E
F
G
H
J
I
K
[7]
[2]
[4]
[4]
[9]
[5]
[4]
[3]
[3]
[5]
[6]
[11]
[8]
[3]
[2]
[3]
[4]
[2]
[1]