TD N°4 : Problème du flot maximum

1. Définitions
1.1 Réseau

Un réseau est un graphe sans boucle, où chaque arc est relié par une application
mathématique à un nombre c(u) ≥ 0, appelé "capacité de l’arc u". En outre, ce réseau
doit vérifier les conditions suivantes.

➢ Il existe un seul nœud s qui n’a pas de prédécesseurs, tous les autres en ont au
moins un. Ce nœud est appelé l’entrée du réseau, ou la source.
➢ Il existe également un seul nœud p qui n’a pas de successeurs, tous les autres
en ont au moins un. Ce nœud est appelé la sortie du réseau, ou le puits.

1.2 Flot

Un flot f dans un réseau est une application mathématique qui associe à chaque arc u
une quantité f(u) qui représente la quantité de flot qui passe par cet arc, en provenance
de la source et en destination vers le puits.

Un flot doit respecter la condition suivante: la somme des quantités de flot sur les
arcs entrants dans un nœud (autre que s et p) doit être égale à la somme des quantités
de flot sur les arcs sortants de ce même nœud. En d’autres termes, la quantité totale
de flot qui entre dans un nœud est égale à la quantité totale de flot qui en sort.

1.3 Flot compatible

Un flot f est compatible avec un réseau si pour tout arc u, 0 ≤ f(u) ≤ c(u). Autrement
dit, pour chaque arc, le flot qui le traverse ne doit pas dépasser la capacité de l’arc.
Parmi les flots compatibles, Le plus évident est le flot nul, c’est-à-dire que pour tout
arc u, f(u) = 0.

1.4 Flot complet

Un flot f est complet si pour tout chemin allant de la source au puits, il y a au moins un
arc saturé, c’est-à-dire que le flot qui le traverse est égal à la capacité de l’arc.

1.5 Flot maximum

La valeur du flot maximum correspond au flux net partant de s, c'est à dire le flot sortant
moins le flot entrant de s. La valeur du flot peut être définie de manière équivalente
comme le flux net arrivant à P, c'est à dire le flot entrant moins le flot sortant de P.

1
 1.6 Chaîne augmentante

C’est une chaîne pour laquelle les arcs dans le sens direct n'ont pas atteint leur limite
maximum et les arcs en sens indirect ont un flot non nul qui les traverse.

Exemple : On considère une chaîne augmentante de A « Source » »Puits » à F

faisant partie d'un réseau de transport.

Dans cette chaîne, on peut augmenter le flot de :

✓ 4 entre A et B,
✓ 3 entre B et C,
✓ 2 entre C et D,
✓ 6 entre D et E.
✓ 3 entre E et F

On augmentera donc de 2 le flot dans cette chaîne. Ce qui signifie:

✓ augmenter de 2 le flot entre A et B,
✓ augmenter de 2 le flot entre B et C,
✓ diminuer de 2 le flot entre D et C,
✓ augmenter de 2 le flot entre D et E.
✓ augmenter de 2le flot entre E et F.

1.7 Loi de Kirchhoff

La somme des intensités qui arrivent au nœud est égale à la somme des intensités qui
en repartent.

2. Problème du flot maximum

Connaissant les capacités des arcs d’un réseau, le problème du flot maximum consiste
à déterminer quelle est la quantité maximum de flot qui peut circuler de la source au
puits. L’algorithme le plus utilisé pour la résolution de ce type problème est celui de
Ford et Fulkerson. Deux méthodes sont utilisées.

➢ La première est basée sur la recherche d’une chaîne dans le réseau.

➢ La seconde construit un graphe "d’écart" dans lequel on recherche un chemin.

2
2.1 Algorithme de FORD-FULKERSON « chaine augmentante » CHAINE
AUGMENTANTE

On commence par un flot compatible « le flot nu » où pour tout arc u, f(u) = 0. Après,
on cherche une chaîne reliant la source au puits de telle sorte que son flot peut être
augmenté. Si on n'en trouve pas, le problème est terminé. Dans le cas contraire, on
augmente le flot sur cette chaîne. Ensuite, on recommence à chercher une autre chaîne
augmentante et ainsi de suite. L'augmentation de flot maximum pour une chaîne est le
minimum des écarts entre le flot courant et le flot maximal pour les arcs directs ou le
flot courant pour les arcs indirects. Autrement dit, une chaîne « C » est augmentante
dans les deux cas suivant:

➢ pour tout arc u direct, f(u) < c(u),

➢ pour tout arc u indirect, f(u) > 0.

Le flot f sur cette chaîne « C » peut être augmenté de :

f(C) = min({c(u) - f(u)/ u C et u sens direct} {f(u)/ u C et u sens indirect})

Remarque

➢ Tour arc u sens direct de C sera augmenté de f(C) s’il n’est pas saturé
c’est-à-dire que c(u) ≠ f(u).
➢ Tour arc u sens indirect de C sera diminué de f(C) si f(u) ≠ 0.

Mise en œuvre de l’algorithme de Ford-Fulkerson

La mise en œuvre de l’algorithme de Ford-Fulkerson se fait par marquage des

sommets tout en gardant chaque prédécesseur des sommets marqués. Un sommet x est
marqué par un couple (x ; Fxy), où x est un sommet déjà marqué, précédent de y, et
Fxy la valeur numérique du flot entre x et y.

Étape 1 : Initialisation par un flot réalisable. Au début, le flot Fxy = 0 pour tout arc de
2 sommets (x , y).

Étape 2 : On marque le sommet initial S avec (- , ∞) : S n’a pas de sommet précédent

(-) et a un flot maximal (∞). x=S

Étape 3 : Pour chaque sommet marqué x, chercher tous les sommets non marqués y
adjacents à x, que les arcs (x ; y) soient dans toutes les orientations.

S'il n'existe aucun sommet non marqué y, c'est que le flot est maximal : Fin.

S'il existe au moins un sommet non marqué y, pour chaque y trouvé il y a deux cas
possibles :

Cas 1 : l’arc (x ; y) est bien orienté x→ y et la capacité Cxy > Fxy (arc non saturé) :

3
Marquer y avec le couple (x, Cxy – Fxy), où x est le sommet précédent de y, et Cxy -
Fxy la valeur du flux entre x et y. Si Cxy = Fxy (arc saturé) ne pas marquer y.

Cas 2 : l’arc (x, y) est mal orienté x  y et Fxy > 0 (flot pas nul) :

Marquer y avec le couple (x, Fxy) où x est le sommet précédent de y, et Fxy la valeur
du flux entre x et y. Si Fxy = 0 (flot nul) ne pas marquer y.

Si y = sommet final T aller à l'étape 4, sinon x=y et répéter l'étape 3.

Étape 4.

- A l'aide des sommets précédents des y marqués, constituer une chaîne augmentante
menant de S à T.

- Calculer le flux Fmin de la chaîne augmentante = valeur minimale des flux des
sommets y marqués

- Pour chaque arc (x, y) bien orienté x→ y de la chaîne constituée, Fxy = Fxy + Fmin

- Pour chaque arc (x, y) mal orienté x  y de la chaîne constituée, Fxy = Fxy - Fmin

Étape 5.

Effacer toutes les marques et retourner à l'étape 2

Exercice 1 : Avant de mettre en application un projet de distribution d’eau potable, on

désire étudier la capacité du réseau d’approvisionnement en eau potable, représenté
par le graphe ci-dessous, reliant le quartier ville P au quartier S d’une même ville.
Pour cela, on a évalué le nombre maximal de clients que chaque canal de conduite
d’eau peut supporter. Ces évaluations sont indiquées en milliers de tonnes d’eau (par
jour) sur les arcs du graphe. Le volume d’eau entre quartiers sont tels que les abonnés
ne dépasseront pas est représenté par le graphe.

Déterminer, en indiquant le type de problème à résoudre et en détaillant la

méthode utilisée, le volume total maximal d’eau susceptible de s'écouler entre les
quartiers S et P.

4
Le problème consiste à déterminer un flot maximal dans un réseau de conduite d’eau.
On peut utiliser l'algorithme de marquage des sommets de Ford-Fulkerson. Plutôt que
de démarrer du flot nul, construisons un flot en étudiant toutes les chaînes de S
« source » à P puits.
Sur la chaîne SADGP, on peut faire passer un flux de 4 (l'arc SA est alors saturé).
Sur la chaîne SBDGP, on peut augmenter les flux de 6 (l'arc DG est alors saturé).
Sur la chaîne SBEGP, on peut augmenter les flux de 2 (l'arc BE est alors saturé).
Sur la chaîne SBCEP, on peut augmenter les flux de 2 (l’arc CE est alors saturé).
Sur la chaîne SBEP, on peut augmenter les flux de 2 (l'arc BE est alors saturé).
Enfin, sur la chaîne SCEP, on peut augmenter les flux de 2 (l'arc CE est alors saturé).
Enfin, sur la chaîne SCFP, on peut augmenter les flux de 3 (l'arc CF est alors saturé).

Depuis S sur la chaîne SADGP, on ne peut pas marquer A (saturation de SA)

Depuis S on peut marquer B par (S, 4) et C par (S, 3).
Depuis B, on peut marquer D par (B, 5).
Depuis A, on peut marquer D par (A, 2),
Depuis A, on peut marquer E par (A, 9).
Depuis E, on peut marquer F par (E, 2), G par (E, 1) et P par (E, 3).
Ainsi on peut augmenter le flot de 4 sur le chemin SBDAEP. (-4 sur l'arc AD)

Tous les chemins de S vers P contiennent au moins un arc saturé. On arrête le

marquage. Le flot obtenu est donc de valeur maximale.
Ainsi le débit total maximal de volume d’eau susceptible de s'écouler entre les
quartiers S et P est de 17000 tonnes par jour.

5
Exercice 2 : Avant d'établir un projet de construction d'autoroute, on désire étudier la
capacité du réseau routier, représenté par le graphe ci-dessous, reliant la ville S à la
ville P.

On a évalué le nombre maximal de véhicules que chaque route peut écouler par heure,
compte tenu des conditions de ralentissements aux traversées des villes et villages, des
arrêts aux feux etc... Ces évaluations sont indiquées (en milliers) de véhicules par heure
sur les arcs du graphe. Les temps de parcours entre villes sont tels que les conducteurs
n'emprunteront que les chemins représentés par le graphe.

On demande d’établir quel est le nombre maximal de véhicules qui peut passer dans
ce réseau de la ville VS à la ville VP.

Exercice 3 : Soit le réseau suivant :

Déterminer le flot maximum entre S et P.