210
Recherche opérationnelle
quantités
sur ces arcs, sans changer ces distances sur les autres arcs. On diminue
donc la distance totale d(
Supposons maintenant qu'on se trouve dans le cas b)
appartient alors à un cocycle où
tous les arcs noirs sont dans le même sens, où les arcs verts sont dans le sens contraire et
où il n'y a pas d'arc rouge.
Mais si on applique les équations de conservation aux nœuds, on a nécessairement
Mais comme
pour
avec l'inégalité stricte au moins pour , on a alors :
C'est à dire que la condition nécessaire d'existence dans un flot compatible n'est pas
vérifiée. Si donc on se trouve dans ce cas b), c'est qu'il n'y a pas de flot compatible.
S'il y a des flots compatibles, on se trouve systématiquement dans le cas a) et
l'algorithme consiste, grâce à des marquages de Ford-Fulkerson, à diminuer la quantité
jusqu'à ce que
.
On voit alors que la condition nécessaire d'existence du flot compatible est en même
temps suffisante. En effet, si elle est vérifiée pour tout
, on ne peut jamais être dans
le cas b) du lemme de Minty, et on se trouve dans le cas a) où l'on peut diminuer
à
chaque fois qu'on trouve cette quantité positive. On aboutira donc nécessairement à
et sera alors compatible.
Retenons donc également, au delà de l'algorithme, ci-dessus le théorème suivant, dû à
Hoffmann :
A
A
(u) c(u)
(u) b(u)