Ch. 4 — Flots

Le réseau de transport

Un réseau de transport est une infrastructure qui fait circuler des flux (eau, gaz) ou des éléments discrets (marchandises, personnes, informations) : réseau routier, câbles sous-marins, ferroviaire, distribution d'eau. On le modélise par un graphe orienté et valué dont les poids sont des capacités :

Un réseau de transport est un quintuplet G = (S, A, c, o, p) où c associe à chaque arête une capacité, o est la source (sommet sans prédécesseur) et p le puits (sans successeur).

La source et le puits ne font pas partie du réseau réel : ce sont les deux points entre lesquels on veut transporter — on les ajoute au besoin lors de la modélisation.

Flot et valeur d'un flot

Un flot associe à chaque arête une quantité transportée f((x, y)), sous deux contraintes — quand elles sont respectées, le flot est réalisable :

1. capacité : f((x, y)) ≤ c((x, y)) — on note l'état d'une arête [flot|capacité] ;
2. conservation : en chaque sommet (sauf source et puits), le flot entrant est égal au flot sortant — rien ne se crée, rien ne disparaît.

La valeur d'un flot est le flot sortant de la source, toujours égal au flot entrant dans le puits grâce à la conservation. Le flot maximal est le flot réalisable de valeur maximale : « combien d'eau peut-on fournir à la ville ? » est une question de flot maximal.

Le graphe de flot résiduel

Pour améliorer un flot, on regarde ce qui reste possible. Le graphe de flot résiduel a les mêmes sommets que G et, pour chaque arête (s, s′) de flot f et de capacité c :

• une arête aller de poids c − f : de combien on peut augmenter le flot ;
• une arête retour de poids f : de combien on peut le diminuer.

Une chaîne améliorante est un chemin de la source au puits dans ce graphe, privé des arêtes de poids 0. Sa capacité résiduelle est le poids minimal de ses arêtes. L'améliorer revient à ajouter v sur chaque arête aller et à soustraire v sur chaque arête retour — un chemin du graphe résiduel est une chaîne (pas forcément un chemin) du réseau initial, car il peut emprunter des arêtes à contresens.

L'algorithme de Ford-Fulkerson

Entrées : un réseau de transport G = (S, A, c, o, p). Sortie : le flot maximal.

1. soit f le flot nul (0 sur chaque arête)
2. soit R le graphe de flot résiduel de G et f
3. tant que R contient une chaîne améliorante h
4.   soit v la capacité résiduelle de h
5.   pour toute paire x, y consécutifs dans h
6.     si (x,y) est une arête de G : f((x,y)) += v
7.     sinon : f((y,x)) -= v
8.   mettre à jour R pour le nouveau flot f
9. retourner f

La recherche d'une chaîne améliorante se fait par un parcours en largeur depuis la source, arrêté quand le puits est atteint. Quand plus aucune chaîne améliorante n'existe, le flot est maximal. Pour aller plus vite à la main, on peut démarrer d'un flot complet — un flot où tout chemin de la source au puits est saturé (contient une arête à flot = capacité) : on le construit en saturant des chemins non saturés trouvés par parcours en profondeur, puis Ford-Fulkerson prend le relais.

La coupe minimale

Une coupe est une partition des sommets en un ensemble O contenant la source et un ensemble P contenant le puits. Tout flot allant de la source au puits doit emprunter l'une des arêtes qui traversent la coupe de O vers P — sa capacité totale borne la valeur de tout flot. Si ces arêtes sont toutes saturées, le flot est maximal : c'est le théorème flot-max/coupe-min — la valeur du flot maximal égale la capacité de la coupe minimale, la « goulotte » du réseau. En pratique, la coupe se lit sur le dernier graphe résiduel : les sommets accessibles depuis la source forment O, les autres P, et toutes les arêtes de O vers P sont saturées.

Grapp et les grandes modélisations

Grapp maximum-flow --help
Grapp maximum-flow -algorithm Ford-Fulkerson -on g1 -source o -sink p
Grapp draw -result r1.1 -to flot.png

La commande affiche le flot sur chaque arête, la valeur du flot et la coupe ; draw le visualise. Les modélisations du TP balayent tous les cas classiques : réseau de distribution d'eau (quatre réserves a-d vers trois villes j, k, l — le graphe brut n'est pas un réseau valide tant qu'il a plusieurs entrées/sorties : on ajoute source et puits), réseau routier avec capacités de villes (scinder chaque commune en deux), réseau internet (nombre minimal de câbles à couper : remplacer chaque câble par une arête de capacité 1, la coupe minimale compte alors les câbles), capacité d'un routeur (scinder le routeur), et affectation familles-appartements par couplage biparti (chapitre suivant). Comme pour Dijkstra et l'ordonnancement, les 15 dernières minutes du TP vont aux tests auto-correctifs Ford-Fulkerson sur Moodle.

A retenir

• réseau de transport = graphe orienté valué en capacités, avec une source et un puits ;
• flot : capacités respectées + conservation aux sommets ; valeur = flot sortant de la source ;
• graphe résiduel : arête aller c − f, arête retour f ; chaîne améliorante de capacité résiduelle minimale ;
• Ford-Fulkerson : flot nul (ou complet, pour aller plus vite à la main) amélioré tant qu'une chaîne améliorante existe ;
• flot maximal = capacité de la coupe minimale ; la coupe se lit sur les sommets accessibles de la source dans le dernier graphe résiduel ;
• Grapp maximum-flow -algorithm Ford-Fulkerson -source … -sink ….