Cours TG Chapitre 5

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

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 | ;

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 =  ; sE, tF
La capacité C(E, F) d'une coupe est la somme des capacités des

arcs de E a F.

transport
C(E, F) = 26 8
Propriété :
Le flux de E à F dans un flot f est : f ( E, F )   f (u)
uExF
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

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.

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

Cours TG Chapitre 5

Transféré par

Droits d'auteur :

Formats disponibles

Cours TG Chapitre 5

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Cours TG Chapitre 5

Transféré par

Droits d'auteur :

Formats disponibles

Université de Msila

Faculté Mathématiques et Informatique

2eme année Informatique

Dr Nasser Eddine MOUHOUB

1. Les réseaux de transport

Réseau de transport avec

• 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

Exemples : circuits électriques ou hydrauliques, réseaux

Sommet A : 11+1 = 12 + 0 , sommet C: 12+7=4+15

Un flot sur le réseau de

Un flot sur le réseau de

La capacité C(E, F) d'une coupe est la somme des capacités des

Un flot sur le réseau de

et le flux orienté de la coupe (E , F) ou ( flot net traversant la coupe )

Un flot sur le réseau de

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

Un flot est saturé si sur tout chemin de s a t il existe un arc a

On cherche un chemin de s à t dans le réseau résiduel.

Il correspond à une possibilité d'amélioration du flot en modifiant

Le flot après amélioration

Dans ce réseau, il n'y a pas de chemin de s à t, donc pas de

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.

On peut dans ce cas rajouter une "super-source" et un "super-

Vous aimerez peut-être aussi