Flot & Réseaux de transport

Algorithme de Ford-Fulkerson

Pr. Cheikh Noufissa

cheikh.noufissa@gmail.com
 Définition de réseau de transport

Un réseau de transport G = (S, A):

• Graphe orienté

• Graphe valué; chaque arc (u, v) Є A a une capacité c(u, v) ≥ 0

• Si (u, v) Є A, on suppose que c(u, v) = 0

Remarque:

La capacité peut être des tonnages, des débits dans des canalisations, ...
 Source et Puits

 Dans un réseau de transport, deux sommets ont un statut particulier:

 La source s et le puits p

 On a :

 Chaque sommet se trouve sur un certain chemin reliant la source au puits.

 Pour tout sommet v Є S, il existe un chemin depuis s passant par v et allant à p

 Exemple

1 2
PUITS

SOURCE
3 4
 Flots

 Soit G = (S, A) un réseau de transport avec une fonction à capacité c

 Le sommet s est la source du réseau, le sommet p est le puits.

 Un flot de G est une fonction à valeurs réelles f: qui satisfait aux trois propriétés
suivantes:

 Contraintes de capacité

 Symétrie

 Conservation du flot
 Flots

Contraintes de capacité  Pour tout u, v Є S, on exige :

Symétrie  Pour tout u, v Є S, on exige :

Conservation de flot  Pour tout u Є on exige

 Flux

 La quantité f(u, v) qui peut être positive, nulle ou négative, est appelée flux
du sommet u au sommet v

 La valeur d’un flot f est définie par:

 Autrement dit, le flux partant de la source

 Dans un problème de flot maximum, on part d’un réseau de flot G de source s

et de puits p et on souhaite trouver un flot de valeur maximum
 Exemple
Flux Capacité
c

1 2
Puits

Source
3 4

𝒇 ( 𝒖 , 𝒗 ) ≤ 𝒄 (𝒖 , 𝒗)
 Exemple

 Un flot f de G de valeur │f│ = 19

 Seuls les flots positifs du réseau sont montrés.
 Si f(u, v) ˃ 0, l’arc (u, v) est étiqueté par f(u, v)/ c(u, v)
 La notation slash sert seulement de séparer le flux de la capacité.
Problème de flot
 Problème de flot

Les flot permettent de modéliser une très large classe de problèmes:

Calculer la quantité maximale d’un fluide pouvant transiter sur

un réseau dont les capacités sont limitées
 Problème de flot
• Distribution d’eau dans un réseau de canalisation, transport de pétrole sur un réseau
de pipelines
 Problème de flot
• Système de transport en commun dans une grande ville
 Problème de flot

• Transport d'énergie électrique sur le réseau

 Problème de flot

• La circulation dans un réseau routier

 Problème de flot

• Le débit de données sur le réseau d’un opérateur (neutralité du net)

Problème de flot

Objectif
Problème de flot
Problème de flot
Problème de flot
Problème de flot
Problème de flot
 Problème de flot

Arc saturé

On dit qu'un arc est saturé si le flot sur cet arc est égal à la capacité de l'arc

Les arcs saturés sont dessinés en bleu sur la figure

Problème de flot
 Problème de flot

Flot complet :
• On dit qu'un flot est complet si tout chemin du réseau de transport allant
de s à p contient au moins un arc saturé, c'est-à-dire un arc (i,j) tel que
Ford-Fulkerson
 Ford-Fulkerson

 L’algorithme de Ford-Fulkerson dépend de 3 concepts:

 Les réseaux résiduels

 Les chemins améliorants

 Les coupes
Ford-Fulkerson
Ford-Fulkerson
 Ford-Fulkerson – Réseau résiduels

 Intuitivement:

 Etant donné un réseau de transport et un flot,

 Le réseau résiduel est constitué des arcs qui peuvent supporter un

flot plus important
 Ford-Fulkerson – capacité résiduelle

 Soit G = (S, A) un réseau de source s et de puits t

 Soit f un flot de G, et (u, v) un couple de sommets de G

 La quantité de flux supplémentaire qu’il est possible d’ajouter entre u et v

sans dépasser la capacité de c(u, v) est la capacité résiduelle de (u, v)
donnée par
 Ford-Fulkerson – capacité résiduelle

Exemple

• Si c(u, v) = 16 et f(u, v) = 11

• on peux convoyer de flux supplémentaires sans excéder la

contrainte de capacité sur l’arc (u, v)
 Ford-Fulkerson – capacité résiduelle

• Quand le flux net f(u, v) est négatif,

• La capacité résiduelle est supérieure à la capacité c(u, v)

Par exemple:

• Si c(u, v) = 16, f(u, v) = - 4

= 20
 Ford-Fulkerson – chemins améliorants

• Etant donné un réseau de transport et un flot,

• Un chemin améliorant p est un chemin élémentaire de s vers t dans le

réseau résiduel Gr

• D’après la définition du réseau résiduel chaque arc (u, v) d’un chemin

améliorant admet un flot positif supplémentaire de u vers v tout en
restant soumis à la contrainte de capacité sur cet arc.
 Ford-Fulkerson – coupe

Définition:
• Soient G=(X,A,C) u reseau, S sous-ensemble des sommets contenant s et pas p et T= X - S

• On appelle coupe séparant s et p (ou s-t coupe) un ensemble d’arcs ayant pour extrémité
initiale un sommet en S et pour extrémité finale en T

• La capacité de la coupe que l’on note C(S,T), est la somme des capacités des arcs les
constituant.
 Ford-Fulkerson – coupe

Exemple de s-t coupe:

 Ford-Fulkerson – coupe

• La méthode de Ford-Fulkerson augmente progressivement le flot

dans les chemins améliorants jusqu’à atteindre un flot maximum

Le théorème de « flot maximum & coupe minimum »

• Un flot est maximum si et seulement si son réseau résiduel ne

contient aucun chemin améliorant
 Exemple
flux capacité

source puits
 Exemple

Objectif:

 Trouver un chemin améliorant

 Calculer la capacité du goulot d'étranglement
 Augmenter chaque bord et le débit total
 Exemple
 Trouver un chemin améliorant
 Calculer la capacité du goulot d'étranglement
 Augmenter chaque bord et le débit totale
 Exemple
 Trouver un chemin améliorant
 Calculer la capacité du goulot d'étranglement
 Augmenter chaque bord et le débit totale

8
8

On commence par le chemin: SADT

 Exemple

Amélioration de 8
 Exemple

10

2
10

On prends le chemin: SCDT 2

 Exemple

Amélioration de 2 la valeur devient: 8 + 2 = 10

 Exemple
4

4
4

14

On prends le chemin: SCDABT 6

On a f(A, D) = 8 donc f(D, A) = - 8
 Exemple

Amélioration de 4 la valeur devient: 10 + 4= 14

 Exemple

10 6

2
16

On prends le chemin: SADBT

 Exemple

Amélioration de 2 la valeur devient: 14 + 2 = 16

 Exemple

19

On prends le chemin: SCDBT 9

 Exemple

Amélioration de 3 la valeur devient: 16 + 3 = 19

 Exemple

On remarque qu’on ne peux pas augmenter la

valeur de l’arc (A, C) puisque les chemins sont
tous saturés. Donc la valeur du flot est 19
Exemple 2
Exemple 2
Exemple 2
Exemple 2
Exemple 2
 Exemple 3
Utiliser l’algorithme de Ford-Fulkerson pour déterminer la valeur maximale du flot dans le réseau suivant,
ou la source est le sommet 000 et le puits est le sommet 111.
 Exemple 4
Utiliser l’algorithme de Ford-Fulkerson pour déterminer la valeur maximale du flot de A vers J.
Flot dans un réseau de transport
Flot dans un réseau de transport
Flot dans un réseau de transport
Exemple de Flot
 Exemple de Problème
• Un magasin «M» spécialisé dans les téléphones mobiles a une capacité de vente de 500
appareils par jour . Il se les fait livrer chaque matin à partir de deux entrepôts «E1» et «E2».

• La capacité de livraison de «E1» et «E2» vers «M» est de 400 et 300 appareils respectivement.

• Les entrepôts se font eux-mêmes approvisionner régulièrement : la capacité moyenne des

arrivées sur l’entrepôt «E1» est de 500 appareils par jour. Pour l’entrepôt «E2» elle est de 900.

• Le gérant du magasin s’est aperçu que la capacité d’accueil de ses entrepôts dépassait la capacité
de vente de son magasin. Il a donc aussi développé un système de vente directe dans ses
entrepôts. La capacité de vente de l’entrepôt «E1» est de 400 appareils par jour. Celle de
l’entrepôt «E2» de 500 appareils.

Question: Dans ces conditions combien peut-il vendre au maximum d’appareils chaque jour ?
 Exemple de Problème

Modélisation du problème sous forme de graphe

• Chacune des contraintes (capacité de vente, de livraison, d’approvisionnement)
devra apparaître sous la forme d’un et un seul arc.

• Création des chemins possibles entre les approvisionnements et ventes.

 Exemple de Problème
Début de modélisation

Au tout début du circuit commercial, il y a les approvisionnements des deux entrepôts. On

va donc commencer à placer ces deux arcs avec leur deux contraintes (500 appareils pour
«E1» et 900 pour «E2»).
 Exemple de Problème
Suite de modélisation

Il y a deux usages possibles des appareils arrivés dans les entrepôts : soit ils sont vendus
directement sur place, soit ils sont livrés au magasin «M». Depuis l’entrepôt «E1» on peut en
vendre 400 et en livrer 400, depuis l’entrepôt «E2» on peut en vendre 500 et en livrer 300.
 Exemple de Problème
Fin de la modélisation

Les appareils arrivés au magasin doivent être vendus. On ajoute donc cette capacité au graphe (500).
Toutes les contraintes seront alors reportées sur le modèle. Mais un graphe de transport ne doit avoir
qu’une seule entrée (la source) et qu’une seule sortie (le puits). Donc on ajoute un somme «S» pour
servir d’origine à tous les arcs en début de graphe, et un sommet «P» pour servir de destination à
tous les arcs en fin de graphe.