Université de Msila
Faculté Mathématiques et Informatique
Département d’Informatique
Cours de
Théorie des graphes
2eme année Informatique
Dr Nasser Eddine MOUHOUB
2015 / 2016
1
C hapitre V
Réseaux de flots
Problème du flot maximum
2
PROBLEME DE FLOTS
1. Les réseaux de transport
2. Le flot maximum et la coupe minimum
3. L'algorithme de Ford et Fulkerson
3
Les réseaux de transports
• Réseau de transport : graphe orienté avec pour chaque arc une
capacité.
• La capacité c(a) est un entier positif ou nul.
• Il y a aussi une source s et un puits t.
• Aucun arc n'arrive à la source
• Et aucun arc ne quitte le puits.
Réseau de transport avec
les capacités
4
• Un flot est une fonction entière positive ou nulle f définie
sur les arcs satisfaisant :
• Contrainte de capacité: f(a) c(a) ;
Pour le graphe si dessous: 11 16, 8 13, 0 10, 12 12 , … , 4 4
Un flot sur le réseau de
transport
5
Conservation du flot:
pour tout sommet autre que s et t, la somme des flots sur
les arcs entrants et la somme des flots sur les arcs sortants
sont égales.
Exemples : circuits électriques ou hydrauliques, réseaux
de communication, modélisation de transports
Sommet A : 11+1 = 12 + 0 , sommet C: 12+7=4+15
Un flot sur le réseau de
transport
6
Quand deux arcs en sens inverse relient deux sommets, on
peut toujours annuler la fonction flot sur l'un des deux.
Propriété :
la somme des flots sur les arcs sortant de source et la somme
des flots sur les arcs arrivant au puits sont égales ; cette
valeur est la valeur du flot | f | ;
Un flot sur le réseau de
transport
7
Une coupe est une partition de l'ensemble des sommets en 2
parties disjointes, l'une contenant la source et l'autre le puit:
E F =A, E F = ; sE, tF
La capacité C(E, F) d'une coupe est la somme des capacités des
arcs de E a F.
Un flot sur le réseau de
transport
C(E, F) = 26 8
Propriété :
Le flux de E à F dans un flot f est : f ( E, F ) f (u)
uExF
et le flux orienté de la coupe (E , F) ou ( flot net traversant la coupe )
est:
| f | ( E, F ) f ( E, F ) f ( F , E)
C(E, F) = 12+14 = 26
f(E, F) = 12+11 = 23
(E, F) = | f | = (12+11) - 4 = 19
Un flot sur le réseau de
transport
9
La deuxième propriété est donc que le flot net traversant une
coupe ne dépend pas de la coupe.
Tout flot a pour valeur Vf = f( {s}, X\{s} ) = ( {s}, X\{s} ).
Lemme: Plus généralement Vf = ( E, F) pour toute coupe.
| f | est inférieur à la capacité de n'importe quelle coupe.
Un flot sur le réseau de
transport
| f | = (12+7+4) – 4 = 19 10
Le flot maximum et la coupe minimum
Il existe toujours un flot possible qui est le flot nul.
Problème : comment trouver un flot qui a la valeur maximum ?
Recherche d'un chemin améliorant.
Déterminer le réseau résiduel :
Un flot est saturé si sur tout chemin de s a t il existe un arc a
tel que f(a) = c(a).
11
pour chaque arc a = uv, f(a) ≤ c(a), on peut augmenter le flot
de c(a) - f(a), et on peut le diminuer de f(a), donc faire passer
un flot f(a) sur un arc -a = vu. Si cet arc existe déjà avec une
capacité c(-a), celle-ci s'ajoute à f(a).
Le flot
Le réseau résiduel
correspondant
12
Le graphe orienté avec ces capacités est le réseau résiduel.
On cherche un chemin de s à t dans le réseau résiduel.
Il correspond à une possibilité d'amélioration du flot en modifiant
de la valeur du minimum des capacités résiduelles sur le chemin.
Le réseau résiduel
13
Un chemin améliorant
Le flot après amélioration
14
Le nouveau réseau résiduel
Dans ce réseau, il n'y a pas de chemin de s à t, donc pas de
chemin améliorant.
15
Théorème (flot maximum et coupe minimum)
Si f est un flot dans un réseau de transport, les trois conditions
suivantes sont équivalentes :
1. f est un flot maximum ;
2. Le réseau résiduel de f ne contient aucun chemin améliorant ;
3. Il existe une coupe E/F dont la capacité vaut | f |.
Remarque :
La condition 3. implique que | f | est la valeur minimum des
capacités des coupes du réseau, puisqu'on sait déjà que | f | est
inférieur à la capacité de n'importe quelle coupe.
Valeur du flot maximal = Capacité de la coupe minimale.
16
L'algorithme de Ford et Fulkerson
o On part d'un flot quelconque (éventuellement nul) ;
o On fabrique le réseau résiduel ;
o On cherche un chemin améliorant ;
o On itère jusqu'à ce qu'on ne trouve plus de tel chemin.
17
Variantes et applications :
Parfois, il y a plusieurs sources et plusieurs puits.
On peut dans ce cas rajouter une "super-source" et un "super-
puits" reliés respectivement aux sources et aux puits par des arcs
de capacité infinie.
Adjonction d'une
super-source et d'un
super-puits
18
Valeur de ce flot?
19
Flot maximum?
20
