204
Recherche opérationnelle
Ainsi
augmenterait d'une unité et le flot ne serait pas optimal.
On se trouve donc forcément dans le cas b) du lemme de Minty :
appartient à un
cocycle séparant deux ensembles de sommets
.
Les arcs noirs sont tous dans le même sens (
) et les arcs verts dans le sens contraire
( ); il n'y a pas d'arc rouge appartenant au cocycle. Mais les arcs noirs (sauf
ont
un flux nul, les arcs verts un flux égal à la capacité de l'arc, et les équations de
conservation aux nœuds donnent :
)
(
)
(
=
)
(
)
(
u
u
A
u
A
u
z
)
(
=
)
(
=
)
(
=
)
(
)
(
A
C
u
c
u
A
u
A
u
z
Le théorème est donc démontré. Il fournit en même temps l'algorithme de détermination
du flot maximal, algorithme de Ford Fulkerson.
Ce dernier consiste en effet à faire d'abord passer dans le graphe un flot quelconque. Puis
on effectue le coloriage du théorème précédent. Si on arrive à trouver un cycle partant de
x0
+1
-1
+1
+1
-1
+1
+1
= 0
= c
= 0
= c
0< < c
0< < c
A
A
Vert = c
noir = c
= Z