Problèmes de flots
201
Prenons alors le cocycle joignant
. Tous les arcs noirs de ce cocycle sont dans le
même sens ( ) ; sinon, s'ils allaient de dans , on aurait pu marquer les sommets
correspondants de , ce qui n'a pas été le cas. De même, tous les arcs verts du cocycle
sont également dans le même sens ( ) sinon, s'ils étaient dans le sens contraire ( ) on
pourrait marquer leur extrémité initiale dans .
Enfin, il ne peut y avoir d'arc rouge joignant
ou
, car il entraînerait de toute
façon un marquage dans . Il peut y avoir en revanche dans le cocycle des arcs
incolores.
Le lemme de Minty est ainsi démontré.
c) Flot maximal et coupe de capacité minimale
Revenons maintenant aux flots et aux réseaux de transport. Soit un réseau
,
d'entrée , de sortie , et d'arc de retour
et de capacités des arcs
Prenons un sous-ensemble de sommet tel que
A et
. Soient, suivant les
notations précédentes
l'ensemble des arcs partant de et
l'ensemble des
arcs arrivant dans .
On appellera coupe dans le réseau
l'ensemble d'arcs
. On appellera
capacité de la coupe la quantité
)
(
=
)
(
)
(
u
c
A
C
A
u
A
A
S
t
marqués
Non
marqués