En un point donné du réseau, il y a toujours autant de pétrole qui arrive que de
pétrole qui part : cette loi de conservation se traduit par
f (s, a) + f (c, a) = f (a, b) ,
f (s, c) = f (c, a) + f (c, b) + f (c, d)
f (a, b) + f (c, b) = f (b, d) + f (b, t) ,
f(d, t) = f (c, d) + f (b, d)
et puisque tout le pétrole arrive en t, on aura aussi
f (b, t) + f (d, t) = F
Il s’agit de trouver les flux f (u, v) pour que F soit maximum, sachant que, dans
chaque conduite, le flux ne peut excéder la capacité. Voici la formulation du problème :
Trouver les f (u, v) rendant F maximum, sachant que l’on a
f (s, a) + f (s, c) = f (b, t) + f (d, t) = F
f (s, a) + f (c, a) − f (a, b) = 0
f (s, c) − f (c, a) − f (c, b) − f (c, d) = 0
f (a, b) + f (c, b) − f (b, d) − f (b, t) = 0
f (c, d) + f (b, d) − f (d, t) = 0
0 f (s, a) 3 , 0 f (a, b) 4 , 0 f (b, t) 3
0 f (s, c) 4 , 0 f (c, d) 2 , 0 f (d, t) 4
0 f (c, a) 5 , 0 f (c, b) 1 , 0 f (b, d) 1
Énoncé du problème général
Soit G un graphe orienté et connexe.
® On suppose qu’il existe un unique sommet s, appelé source, où n’arrive aucun arc
et qu’il existe un unique sommet t, appelé terminal, d’où ne part aucun arc.
® À chaque arc (u, v) est associé un nombre c(u, v) 0, appelé capacité de l’arc ; s’il
n’y a pas d’arc entre deux sommets u et v, on pose c(u, v) = 0.
® Un flot est la donnée pour chaque arc (u, v) d’un nombre f (u, v) 0 satisfaisant
les conditions :
i) f (u, v) c(u, v) pour tout arc (u, v).
ii) Si a est un sommet différent de s et de t, alors
arc (v,a) f (v, a)=
arc (a,u) f (a, u).
La condition (ii) exprime la loi de conservation : en tout sommet différent de la
source et du terminal, le flux entrant est égal au flux sortant.
® La valeur d’un flot f est la quantité val(f )=
arc (s,u) f (s, u), somme des flux issus de
la source. Il résulte de la loi de conservation que l’on a aussi val(f )=
arc (v,t) f (v, t).
La valeur d’un flot ne peut pas excéder la somme des capacités des arcs aboutissant
au terminal, ni celle des arcs issus de la source.
Problème : trouver sur G un flot dont la valeur est la plus grande possible.
Un tel flot s’appelle un flot maximum.
La recherche d’un flot maximum se rencontre dans la plupart des questions relatives
aux réseaux de distribution, notamment en télécommunication.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 87
pétrole qui part : cette loi de conservation se traduit par
f (s, a) + f (c, a) = f (a, b) ,
f (s, c) = f (c, a) + f (c, b) + f (c, d)
f (a, b) + f (c, b) = f (b, d) + f (b, t) ,
f(d, t) = f (c, d) + f (b, d)
et puisque tout le pétrole arrive en t, on aura aussi
f (b, t) + f (d, t) = F
Il s’agit de trouver les flux f (u, v) pour que F soit maximum, sachant que, dans
chaque conduite, le flux ne peut excéder la capacité. Voici la formulation du problème :
Trouver les f (u, v) rendant F maximum, sachant que l’on a
f (s, a) + f (s, c) = f (b, t) + f (d, t) = F
f (s, a) + f (c, a) − f (a, b) = 0
f (s, c) − f (c, a) − f (c, b) − f (c, d) = 0
f (a, b) + f (c, b) − f (b, d) − f (b, t) = 0
f (c, d) + f (b, d) − f (d, t) = 0
0 f (s, a) 3 , 0 f (a, b) 4 , 0 f (b, t) 3
0 f (s, c) 4 , 0 f (c, d) 2 , 0 f (d, t) 4
0 f (c, a) 5 , 0 f (c, b) 1 , 0 f (b, d) 1
Énoncé du problème général
Soit G un graphe orienté et connexe.
® On suppose qu’il existe un unique sommet s, appelé source, où n’arrive aucun arc
et qu’il existe un unique sommet t, appelé terminal, d’où ne part aucun arc.
® À chaque arc (u, v) est associé un nombre c(u, v) 0, appelé capacité de l’arc ; s’il
n’y a pas d’arc entre deux sommets u et v, on pose c(u, v) = 0.
® Un flot est la donnée pour chaque arc (u, v) d’un nombre f (u, v) 0 satisfaisant
les conditions :
i) f (u, v) c(u, v) pour tout arc (u, v).
ii) Si a est un sommet différent de s et de t, alors
arc (v,a) f (v, a)=
arc (a,u) f (a, u).
La condition (ii) exprime la loi de conservation : en tout sommet différent de la
source et du terminal, le flux entrant est égal au flux sortant.
® La valeur d’un flot f est la quantité val(f )=
arc (s,u) f (s, u), somme des flux issus de
la source. Il résulte de la loi de conservation que l’on a aussi val(f )=
arc (v,t) f (v, t).
La valeur d’un flot ne peut pas excéder la somme des capacités des arcs aboutissant
au terminal, ni celle des arcs issus de la source.
Problème : trouver sur G un flot dont la valeur est la plus grande possible.
Un tel flot s’appelle un flot maximum.
La recherche d’un flot maximum se rencontre dans la plupart des questions relatives
aux réseaux de distribution, notamment en télécommunication.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 87