Flot maximum et coupure minimum
Revenons au problème général et formulons quelques définitions.
Une coupure de G est une partition de l’ensemble des sommets en deux parties S, S
telles que s ∈ S et t ∈ S
; les parties S et S
sont donc disjointes et leur réunion
est l’ensemble de tous les sommets.
® La capacité d’une coupure (S, S
) est le nombre C(S, S
) =
arc (u,u
)
u∈S , u
∈S
c(u, u
),
® son flot est le nombre F (S, S
) =
arc (u,u
)
u∈S , u
∈S
f (u, u
).
On définit de même le nombre F (S
, S).
Exemple. Pour l’un des flots représentés figure 8, prenons comme coupure
S = {s, a, b, c} et S
= {d, t}. Les arcs orientés ayant leur origine dans S et leur extrémité dans S
sont (c, d), (b, d) et (b, t), donc la capacité est C(S, S
) = 2 + 1 + 3 = 6 ;
le flot de cette coupure est aussi F (S, S
) = 2 + 1 + 3 = 6 et l’on a F (S
, S) = 0, car
il n’y a aucun arc d’origine d ou t ayant son extrémité dans S .
Proposition. Pour tout flot f et pour toute coupure (S, S
), on a
val(f ) = F (S, S
) − F (S
, S) .
Démonstration. Pour tout sommet u ∈ S , on a
v
f (u, v) −
v
f (v, u) =
val(f ) si u = s
0
si u ∈ S \ {s}
car f est un flot. En ajoutant ces égalités pour les différents sommets de S , il vient
u∈S
v
f (u, v) −
u∈S
v
f (v, u) = val(f ) .
Si u et v sont deux sommets de S , les termes f (u, v) et −f (u, v) apparaissent exactement
une fois dans chaque somme, donc se détruisent. Après simplification, on obtient l’égalité
u∈S
v∈S
f (u, v) −
u∈S
v∈S
f (v, u) = val(f ) ,
c’est-à-dire F (S, S
) − F (S
, S) = val(f ).
Corollaire. Soient f un flot et (S, S
) une coupure de G.
i) On a val(f ) F (S, S
).
ii) Si val(f ) = C(S, S
), alors le flot f est maximum et (S, S
) est une coupure de capacité
minimum.
Démonstration. On a val(f ) = F (S, S
) − F (S
, S) F (S, S
), car F (S
, S) 0. Soit f
∗ un
flot maximum et (S
∗ , S
∗ ) une coupure de capacité minimum. D’après (i), on a
val(f
∗ ) F (S
∗ , S
∗ ) C(S
∗ , S
∗ ) , d’où
val(f ) val(f
∗ ) C(S
∗ , S
∗ ) C(S, S
) .
Supposons val(f ) = C(S, S
). Il s’ensuit val(f ) = val(f
∗ ) = C(S
∗ , S
∗ ) = C(S, S
), donc f est
un flot maximum et (S, S
) est une coupure de capacité minimum.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 93