La valeur d’un flot f est le nombre val(f )=
1ip val i (f ), où val i (f )=
arc (s i ,u) f (s i , u)
est la somme des flux issus de la source s i .
On a aussi val(f ) =
1jq
arc (v,t j ) f (v, t j ), d’après la loi de conservation.
Pour trouver un flot maximum sur G, nous allons nous ramener au cas d’une seule
source et d’un seul terminal. Pour cela, on définit un graphe orienté G
de la manière
suivante :
® on ajoute à G deux sommets σ et τ ,
® pour chaque source s i , on ajoute un arc (σ, s i ) et pour chaque terminal t j , on
ajoute un arc (t j , τ).
Le graphe G
a pour unique source σ et pour unique terminal τ . Définissons des
capacités très grandes sur les arcs qui ont été ajoutés et gardons les capacités sur les
arcs de G. Tout flot sur G
définit un flot sur G ; réciproquement, si f est un flot
sur G, on définit un flot f
sur G
en posant f
(α) = f (α) si α est un arc de G,
f
(σ, s i ) = val i (f ) et f
(t j , τ) =
arc (v,t j ) f (v, t j ).
Les flots f et f
ayant même valeur, il suffit d’appliquer à G
l’algorithme de
recherche d’un flot maximum : on obtiendra ainsi un flot maximum sur G.
σ
τ
s 1
s 2
s p
t 1
t 2
t q
les graphes
G et G
Flot à double contraintes
Dans les applications, on doit parfois munir chaque arc α d’une capacité minimum
m(α) 0 et d’une capacité maximum M (α). Un flot f est dit admissible si l’on
a m(α) f (α) M (α) pour tout arc α. Si tous les m(α) sont nuls, le flot nul
est admissible et l’algorithme fournit un flot admissible maximum. Mais si certains
nombres m(α) sont strictement positifs, le flot nul n’est pas admissible.
® Si l’on a trouvé un flot f admissible, alors on peut pratiquer l’algorithme du flot
maximum en partant de ce flot f . On obtient ainsi un flot admissible maximum.
®
s
b
t
a
[0, 2]
[1, 2]
[2, 4]
[3, 5]
[4, 5]
En général, la question se pose de trouver un flot admissible ; un tel flot n’existe d’ailleurs pas toujours. Dans le
graphe ci-dessous, nous avons indiqué à coté de chaque
arc, l’intervalle [m, M ] pour un flot admissible : on vérifie
facilement qu’il n’existe pas de flot admissible.
Dans l’exercice 16, on présente une méthode pour chercher
un flot admissible.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 95
1ip val i (f ), où val i (f )=
arc (s i ,u) f (s i , u)
est la somme des flux issus de la source s i .
On a aussi val(f ) =
1jq
arc (v,t j ) f (v, t j ), d’après la loi de conservation.
Pour trouver un flot maximum sur G, nous allons nous ramener au cas d’une seule
source et d’un seul terminal. Pour cela, on définit un graphe orienté G
de la manière
suivante :
® on ajoute à G deux sommets σ et τ ,
® pour chaque source s i , on ajoute un arc (σ, s i ) et pour chaque terminal t j , on
ajoute un arc (t j , τ).
Le graphe G
a pour unique source σ et pour unique terminal τ . Définissons des
capacités très grandes sur les arcs qui ont été ajoutés et gardons les capacités sur les
arcs de G. Tout flot sur G
définit un flot sur G ; réciproquement, si f est un flot
sur G, on définit un flot f
sur G
en posant f
(α) = f (α) si α est un arc de G,
f
(σ, s i ) = val i (f ) et f
(t j , τ) =
arc (v,t j ) f (v, t j ).
Les flots f et f
ayant même valeur, il suffit d’appliquer à G
l’algorithme de
recherche d’un flot maximum : on obtiendra ainsi un flot maximum sur G.
σ
τ
s 1
s 2
s p
t 1
t 2
t q
les graphes
G et G
Flot à double contraintes
Dans les applications, on doit parfois munir chaque arc α d’une capacité minimum
m(α) 0 et d’une capacité maximum M (α). Un flot f est dit admissible si l’on
a m(α) f (α) M (α) pour tout arc α. Si tous les m(α) sont nuls, le flot nul
est admissible et l’algorithme fournit un flot admissible maximum. Mais si certains
nombres m(α) sont strictement positifs, le flot nul n’est pas admissible.
® Si l’on a trouvé un flot f admissible, alors on peut pratiquer l’algorithme du flot
maximum en partant de ce flot f . On obtient ainsi un flot admissible maximum.
®
s
b
t
a
[0, 2]
[1, 2]
[2, 4]
[3, 5]
[4, 5]
En général, la question se pose de trouver un flot admissible ; un tel flot n’existe d’ailleurs pas toujours. Dans le
graphe ci-dessous, nous avons indiqué à coté de chaque
arc, l’intervalle [m, M ] pour un flot admissible : on vérifie
facilement qu’il n’existe pas de flot admissible.
Dans l’exercice 16, on présente une méthode pour chercher
un flot admissible.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 95