Problèmes de flots
209
dessus. En particulier, le flot nul n'est pas compatible. Comment trouver un flot
compatible ?
On n'est pas certain d'abord qu'un tel flot existe. Etablissons tout de suite une condition
nécessaire d'existence. Pour tout sous-ensemble de sommets
, on a d'après les
équations de conservation aux nœuds :
0
=
)
(
)
(
)
(
)
(
u
u
A
u
A
u
pour tout flot compatible. Ce qui impose :
X
A
u
b
u
c
A
u
A
u
0
)
(
)
(
)
(
)
(
Examinons maintenant l'algorithme permettant d'obtenir un flot compatible.
On part d'un flot quelconque
Appelons pour chaque arc
la distance
la
quantité suivante :
On pose :
0
>
)
,
(
=
)
(
u
d
d
u
Si est tel que
alors est un flot compatible, si est tel que
alors
n'est pas compatible et il existe au moins un arc tel que
.
Supposons qu'il s'agisse d'un arc
tel que
(la démonstration serait tout
à fait analogue si l'on prenait un arc
tel que
.
Colorions
en noir, et les autres arcs de la façon suivante :
- si
en noir,
- si
en rouge,
- si
en vert.
Appliquons alors le lemme de Minty.
Soit on se trouve dans le cas a) du lemme : il existe un cycle élémentaire, avec les arcs
noirs parcourus dans le sens de
, et les arcs verts dans le sens contraire. On peut alors
ajouter aux arcs dans le sens
un flot d'au moins une unité, retrancher ce même flot
aux arcs parcourus dans le sens contraire. On voit qu'on diminue à chaque fois les