Problèmes de flots
215
9.5.4. Flots et potentiels
Introduisons deux vecteurs
Appelons l'ensemble
sera appelé fonction potentielle. Soit la quantité
On a le lemme suivant :
Lemme 1
On a toujours :
pour tout flot saturant et toute fonction potentielle.
En effet
ij
j
i
ij
ij
ij
ij
c
)
(
(puisque
)
ij
i
j
j
ij
j
i
i
ij
ij
ij
c
mais
i
ij
j
a
=
et
j
ij
i
b
=
puisque est saturant, soit
j
j
j
i
i
i
ij
ij
ij
b
a
c
d'où l'inégalité
Si donc on trouve un flot saturant et une fonction potentielle , tels que
on a trouvé le flot de coût minimal.
Démontrons alors un autre résultat.
Lemme 2
Soit une fonction potentielle .
Si on supprime les arcs
tels que
(on garde donc ceux tels que
), on obtient un graphe partiel .