Arbres couvrants et flots dans les
graphes
Table des matières
I - Concepts de flots et de coupes minimales dans les graphes 3
1. Définitions .................................................................................................................3
1.1. Flot.....................................................................................................................................................3
1.2. Flot réalisable ....................................................................................................................................3
2. Interprétations ............................................................................................................4
3. Valeur d’un flot..........................................................................................................4
4. Flot-max.....................................................................................................................4
5. Coupe .........................................................................................................................4
5.1. Flot et coupe ......................................................................................................................................5
5.2. Coupe minimum ................................................................................................................................6
Conclusion 7
2
Concepts de flots et de coupes
minimales dans les graphes I
1. Définitions
Réseau
Un réseau est un graphe orienté G = (S, A) contenant un sommet source s et un sommet puits t.
A chacun de ces arcs (i, j) ∈ A , on associe une capacité c positive.
ij
Un sommet source est un sommet sans prédécesseur à partir duquel tous les autres sommets sont
accessibles.
Un sommet puits est un sommet sans successeur accessible à partir de tous les autres sommets.
1.1. Flot
On appelle flot une fonction f qui associe un nombre à chaque arc.
f : A → IR+
(i, j) → fij et qui vérifie la loi des nœuds.
La Loi des Nœuds ou Loi de Kirchoff est la conservation du flot entre les arcs entrant et sortant d’un
sommet :
∑ fki = ∑ fij ∀i ∈ S ∖ {s, t}
(k,i)∈A (i,j)∈A
Un flot représente une quantité d’objets circulant sur un réseau à un instant donné.
La capacité d’un arc représente la quantité maximale d’objets qui peut passer par cet arc à un moment
donné.
1.2. Flot réalisable
Un flot est dit réalisable si f ij ≤ cij ∀(i, j) ∈ A .
Notons que le flot nul, c’est-à-dire le flot f ij = 0 ∀(i, j) ∈ A est un flot réalisable pour tous les réseaux.
3
Concepts de flots et de coupes minimales dans les graphes
2. Interprétations
Un flot peut-être :
de l’eau qui coule, dont le débit est mesuré en m3/sec, limité par la capacité des tuyaux, c’est-à-dire
le diamètre du tuyau.
de l’électricité, c’est-à-dire des électrons, conduit par un câble. Leur débit se mesure par l’intensité
du courant dans le câble et cette intensité est limitée par l’intensité maximale que peut supporter le
câble.
des données dans un réseau de télécommunications, avec un débit mesuré en bauds (ko/sec) et
limité par la “bande passante” du câble.
des voitures sur une route, avec un débit mesuré en nombre de voitures par sec, et limité par la
largeur de cette route.
et bien d’autres choses...
3. Valeur d’un flot
Valeur d’un flot
Etant donné un flot f , on note valeur d’un flot la quantité de flot entrant par la source, c’est-à-dire *
vf = ∑ fsj
(s,j)∈A
Notons que vf = ∑
(i,t)∈A
fit car la valeur de flot entrant par la source est égale à celle sortant par le
puits.
4. Flot-max
Flot-max
Le problème du flot de valeur maximale (Flot-max) consiste à déterminer un flot de valeur maximale dans
le réseau.
Ce problème permet de modéliser :
l’utilisation optimale d’un réseau électrique
la gestion des réseaux de télécommunications
la régulation routière urbaine ou autoroutière
l’acheminement des produits du fournisseur aux clients
la gestion de production d’une entreprise
...
5. Coupe
Motivation
Qu’est-ce qui contraint la valeur d’un flot ? Sur un réseau très simple, composé de “tuyaux” de capacités
différentes mis bout à bout :
On voit que le flot maximal sur ce réseau est de 2.
4
Concepts de flots et de coupes minimales dans les graphes
Flot sur un chemin
Sur un chemin de s à t, le flot circulant sur ce chemin est au plus de la valeur minimum des capacités des
arcs.
Coupe
¯
Etant donné un ensemble W ⊂ S de sommets contenant la source s, on note W = S ∖ W l’ensemble
complémentaire de W .
On appelle coupe d’un réseau l’ensemble des arcs allant de W à W .
¯
¯
¯
Noter que si l’on enlève les arcs d’une coupe (W , W ) à un réseau, alors les sommets W sont
inaccessibles depuis les sommets de W .
On peut tracer une ligne “coupant” le graphe de telle façon que tout arc allant de gauche à droite de la
ligne est dans la coupe.
Capacité d’une coupe
On appelle capacité d’une coupe la somme des capacités des ses arcs, i.e.
¯
¯c(W , W ) = ∑
ij
c
(i,j)∈(W ,W )
Flot et coupe
¯
Quelque soit un flot f réalisable et quelque soit une coupe (W , W ),
¯
vf ≤ c(W , W )
cela revient à dire que le flot entrant est limité par la somme des capacités des arcs sortant de s.
cela revient à dire que le flot sortant est limité par la somme des capacités des arcs entrant en t.
5.1. Flot et coupe
Borne supérieure
La capacité de chaque coupe est une borne supérieure pour la valeur de tout flot.
La capacité de chaque coupe est donc une borne supérieure pour la valeur maximale d’un flot.
Si l’on a un flot f réalisable de valeur et une coupe de capacité avec
¯
¯
vf (W , W ) c(W , W )
¯
vf = (W , W )
Alors f est un flot de valeur maximale et w est une coupe de capacité minimale.
5
Concepts de flots et de coupes minimales dans les graphes
5.2. Coupe minimum
Sur cet exemple :
On prouve ainsi que ce flot et cette coupe sont optimaux.
Coupe minimum
On appelle problème de la coupe minimum (min-Cut) le fait de rechercher une coupe de capacité
minimale dans un réseau.
La valeur optimale du problème de la coupe minimum est le même que celui du problème de flot maximal.
Mais ces deux problèmes fournissent des objets bien différents ! (l’un un flot, l’autre un ensemble d’arcs).
On dit qu’ils forment un couple de problèmes duaux l’un de l’autre. (Flot-max est le dual de min-Cut et
min-Cut est le dual de Flot-max).
6
Conclusion
Conclusion
