DEPARTEMENT D'INFORMATIQUE
Cours No 5 : FLOTS
Sommaire
1- Réseau de transport
2- Flot
3- Flot maximal
4- Coupe
5- Graphe d’écart
Rédigé par :
[Link]
Année Universitaire : 2021-2022
COURS No 6 : FLOTS
1. Réseau de transport
Soit G = (X, U) un graphe orienté connexe et antisymétrique ayant deux sommets
particuliers E (appelé source) et S (appelé puits) tels que -{E}= et +{S} = . A tout arc
de U, on associe une valeur entière positive C(u) 0 (éventuellement infinie), appelée
capacité de l’arc u. (G, C) est appelé réseau de transport.
Exemple
a
3 7
7
b
S
E 4
2
4 2
2. Flot
Un flot représente l’acheminement d’un flux de matière depuis une source E vers une
destination S.
Exemple
Dans le réseau de transport suivant 0 = 10.
2.1. Flot réalisable
Un flot est dit réalisable si et seulement si :
1. u U 0 (u) C(u)
2. x X – {S,T} (u) (u)
u ( x ) uw ( x )
3. E, S X (u) (u)
u ( E ) uw ( S )
COURS No 6 : FLOTS
3. Flot maximal
Application
Trouver un flot maximal
1ère étape : Le flot est –il réalisable ?
Le flot est réalisable o est réalisable.
COURS No 6 : FLOTS
2ème étape : Le flot o est-il maximal ?
La sortie T est marquée donc o n’est pas maximal
3ème étape : Trouver la chaîne améliorante
0 = Min (5, 6, 5, 10, 5) = 5
1 = o + 0 = 15 + 5 = 20
COURS No 6 : FLOTS
4ème étape : 1 est il maximal ?
La sortie T n’est pas marquée : 1 = 20 est maximal.
4. Coupe
Une coupe C d’un réseau de transport G est un ensemble d’arcs déconnectant l’entrés S de la
sortie T.
Soit Xm les sommets marqués, W+(Xm) est une coupe de G
Xm = {S, b, e, c}
W+(Xm) = {(S,a) (b,d) (e,d) (e,f) (c,g) }.
On remarque que tous les arcs de la coupe Xm sont saturés.
COURS No 6 : FLOTS
La capacite de Xm = 5 + 2 + 2 + 4 + 7 = 20 = 1
5. Graphe d’écart
Soit un réseau de transport G et un flot :
Le graphe d’écart de (G, ) est un graphe ayant les mêmes sommets de G mais des arcs
déterminés sur la base des valeurs du flot .
Soit 1 = 20, on détermine Ge (1) Graphe d’écart associé à 1