Pour justifier l’algorithme, il reste à montrer que si un flot à capacités entières ne
présente pas de chemin non saturé de s à t, alors ce flot est maximum.
Proposition. Un flot à capacités entières est maximum si et seulement s’il n’y a pas de
chemin non saturé de s à t.
Démonstration. S’il y a un chemin non saturé de s à t pour le flot f , le procédé d’augmentation conduit à un flot f
∗ de valeur strictement supérieure : le flot f n’est donc pas
maximum. Réciproquement, supposons que pour le flot f , il n’y a pas de chemin non saturé
de s à t. Soit S l’ensemble des sommets qu’on peut atteindre à partir de s par un chemin non
saturé. On a s ∈ S , et par hypothèse t ∈ S . En notant S
l’ensemble des sommets qui ne sont
pas dans S , on définit donc une coupure (S, S
). Soit (u, v) un arc tel que u ∈ S et v ∈ S
.
Par définition de S , il existe un chemin γ non saturé de s à u. Si l’on ajoute l’arc (u, v) à
ce chemin, on obtient un chemin saturé, car v ∈ S . On a donc f (u, v) = c(u, v). De même, si
(w, z) est un arc tel que w ∈ S
et z ∈ S , on a f (w, z) = 0. Il s’ensuit F (S, S
) = C(S, S
) et
F (S
, S) = 0. Par suite val(f ) = F (S, S
) − F (S
, S) = C(S, S
). D’après le corollaire précédent,
f est un flot maximum et (S, S
) est une coupure de capacité minimum.
Puisque l’algorithme se termine lorsqu’il n’y a plus de chemin non saturé de s à
t, on en déduit qu’il fournit un flot maximum. D’après la seconde partie de la
démonstration ci-dessus, on a le théorème suivant.
Théorème du flot maximum. Si les capacités sont entières, la valeur du flot maximum est égale à la plus petite des capacités des coupures.
Remarques
® On a supposé que les capacités sont des entiers positifs ou nuls afin d’assurer que
l’algorithme se termine. Cette restriction est sans importance dans les applications,
car en choisissant des unités convenables pour les capacités, on peut toujours se
ramener à ce cas.
® La longueur de l’algorithme est conditionnée par la taille des capacités : le temps
d’exécution peut donc être grand, même pour un graphe ayant peu d’arcs (exercice
14). Pour augmenter sensiblement l’efficacité de l’algorithme, il faut, dans la phase
de marquage, chercher systématiquement un chemin non saturé de s à t ayant le
moins d’arcs possible.
Généralisations
Voici deux généralisations au problème du flot maximum.
Graphe ayant plusieurs sources ou plusieurs terminaux
On conserve les hypothèses générales faites sur G page 87, mais on ne suppose plus
l’unicité de la source et du terminal. Au contraire, il peut y avoir des sommets s 1 ,. . .,s p
où n’arrive aucun arc (ce sont les sources) et des sommets t 1 ,. . .,t q d’où ne part aucun
arc (ce sont les terminaux). On définit un flot de la même façon, la loi de conservation
devant être vérifiée en chaque sommet différent d’une source ou d’un terminal.
94 – GRAPHES
présente pas de chemin non saturé de s à t, alors ce flot est maximum.
Proposition. Un flot à capacités entières est maximum si et seulement s’il n’y a pas de
chemin non saturé de s à t.
Démonstration. S’il y a un chemin non saturé de s à t pour le flot f , le procédé d’augmentation conduit à un flot f
∗ de valeur strictement supérieure : le flot f n’est donc pas
maximum. Réciproquement, supposons que pour le flot f , il n’y a pas de chemin non saturé
de s à t. Soit S l’ensemble des sommets qu’on peut atteindre à partir de s par un chemin non
saturé. On a s ∈ S , et par hypothèse t ∈ S . En notant S
l’ensemble des sommets qui ne sont
pas dans S , on définit donc une coupure (S, S
). Soit (u, v) un arc tel que u ∈ S et v ∈ S
.
Par définition de S , il existe un chemin γ non saturé de s à u. Si l’on ajoute l’arc (u, v) à
ce chemin, on obtient un chemin saturé, car v ∈ S . On a donc f (u, v) = c(u, v). De même, si
(w, z) est un arc tel que w ∈ S
et z ∈ S , on a f (w, z) = 0. Il s’ensuit F (S, S
) = C(S, S
) et
F (S
, S) = 0. Par suite val(f ) = F (S, S
) − F (S
, S) = C(S, S
). D’après le corollaire précédent,
f est un flot maximum et (S, S
) est une coupure de capacité minimum.
Puisque l’algorithme se termine lorsqu’il n’y a plus de chemin non saturé de s à
t, on en déduit qu’il fournit un flot maximum. D’après la seconde partie de la
démonstration ci-dessus, on a le théorème suivant.
Théorème du flot maximum. Si les capacités sont entières, la valeur du flot maximum est égale à la plus petite des capacités des coupures.
Remarques
® On a supposé que les capacités sont des entiers positifs ou nuls afin d’assurer que
l’algorithme se termine. Cette restriction est sans importance dans les applications,
car en choisissant des unités convenables pour les capacités, on peut toujours se
ramener à ce cas.
® La longueur de l’algorithme est conditionnée par la taille des capacités : le temps
d’exécution peut donc être grand, même pour un graphe ayant peu d’arcs (exercice
14). Pour augmenter sensiblement l’efficacité de l’algorithme, il faut, dans la phase
de marquage, chercher systématiquement un chemin non saturé de s à t ayant le
moins d’arcs possible.
Généralisations
Voici deux généralisations au problème du flot maximum.
Graphe ayant plusieurs sources ou plusieurs terminaux
On conserve les hypothèses générales faites sur G page 87, mais on ne suppose plus
l’unicité de la source et du terminal. Au contraire, il peut y avoir des sommets s 1 ,. . .,s p
où n’arrive aucun arc (ce sont les sources) et des sommets t 1 ,. . .,t q d’où ne part aucun
arc (ce sont les terminaux). On définit un flot de la même façon, la loi de conservation
devant être vérifiée en chaque sommet différent d’une source ou d’un terminal.
94 – GRAPHES