Problèmes de flots
203
Précisons ce point en démontrant le résultat suivant qui va nous conduire en même
temps à l'algorithme permettant de trouver le flot optimal :
Théorème : La valeur maximale d'un flot de à
dans
, muni de capacités
est égale à la capacité d'une coupe de capacité minimale.
Supposons en effet, un flot tel que
soit maximal. Colorions les arcs de de la
façon suivante :
- l'arc de retour
est colorié en noir,
- un arc tel que
est colorié en noir,
- un arc tel que
est colorié en rouge,
- un arc tel que
est colorié en vert.
Appliquons le lemme de Minty. Montrons que nous ne sommes pas dans le cas a) de ce
lemme. En effet, supposons que l'on soit dans le cas a) : il existe alors un cycle partant
de avec tous les arcs noirs dans le sens
tous les arcs verts dans le sens contraire et
les arcs rouges dans un sens quelconque. Par exemple :
Mais d'après le coloriage choisi sur ce cycle, on peut (en conservant la loi des nœuds)
augmenter les flux sur les arcs noirs d'une unité, diminuer d'une unité les flux sur les arcs
verts, augmenter ou diminuer d'une unité les flux sur les arcs rouges suivant le sens de
ces derniers. On vérifie aisément que les lois des nœuds restent effectivement vérifiées et
les contraintes de capacité également (remarquons ici le caractère nécessaire d'intégrité
des capacités).
x0
noir
vert
rouge
rouge
vert
noir
noir
203
Précisons ce point en démontrant le résultat suivant qui va nous conduire en même
temps à l'algorithme permettant de trouver le flot optimal :
Théorème : La valeur maximale d'un flot de à
dans
, muni de capacités
est égale à la capacité d'une coupe de capacité minimale.
Supposons en effet, un flot tel que
soit maximal. Colorions les arcs de de la
façon suivante :
- l'arc de retour
est colorié en noir,
- un arc tel que
est colorié en noir,
- un arc tel que
est colorié en rouge,
- un arc tel que
est colorié en vert.
Appliquons le lemme de Minty. Montrons que nous ne sommes pas dans le cas a) de ce
lemme. En effet, supposons que l'on soit dans le cas a) : il existe alors un cycle partant
de avec tous les arcs noirs dans le sens
tous les arcs verts dans le sens contraire et
les arcs rouges dans un sens quelconque. Par exemple :
Mais d'après le coloriage choisi sur ce cycle, on peut (en conservant la loi des nœuds)
augmenter les flux sur les arcs noirs d'une unité, diminuer d'une unité les flux sur les arcs
verts, augmenter ou diminuer d'une unité les flux sur les arcs rouges suivant le sens de
ces derniers. On vérifie aisément que les lois des nœuds restent effectivement vérifiées et
les contraintes de capacité également (remarquons ici le caractère nécessaire d'intégrité
des capacités).
x0
noir
vert
rouge
rouge
vert
noir
noir