202
Recherche opérationnelle
Soit maintenant un flot compatible avec les contraintes
Prenons un sommet quelconque de . Sur ce sommet, la loi aux noeuds s'inscrit :
0
=
)
(
)
(
u
u
x
U
u
x
U
u
Sommons ces égalités sur tous les sommets
. Les flux sur les arcs ayant leurs deux
extrémités dans vont s'éliminer; il restera, si
est le flot sur l'arc retour :
0
=
)
(
)
(
)
(
)
(
u
u
A
u
z
A
u
Soit
)
(
)
(
=
)
(
)
(
u
u
A
u
A
u
z
Comme
on peut écrire :
)
(
)
(
u
A
u
z
et encore, puisque
)
(
)
(
u
c
A
u
z
Quels que soient le flot et l'ensemble choisis, on a donc toujours cette inégalité. On est
alors certain que si l'on trouve un flot et un ensemble tel que :
)
(
= A
C
z
alors on a trouvé à la fois le flot maximal et la coupe de capacité minimale.
z
A
x0