Cours 8

CHAPITRE IV Problème de flot maximum

Cours 8

Le problème de flot maximum consiste à trouver, dans un réseau de transport, un flot réalisable depuis une source unique et vers un puits unique qui soit maximum.

Définitions :

On appelle réseau de transport un graphe orienté antisymétrique valué G= (S, A, C), sans boucle et dans lequel il existe :

- un sommet s1 sans prédécesseur nommé entrée ou source (s) du réseau

- un sommet sn sans successeur nommé sortie ou puits (t) du réseau

et tel qu'au moins un chemin unisse s1 et sn

La fonction de pondération C est supposée positive et l’on nomme capacité de l’arc a le nombre C (a)

Un exemple de graphe de flot. la source est s , et le puits est t . Les nombres indiquent le flot sur la capacité.

La principale question qui se pose pour un réseau de transport donné est de déterminer un flot de valeur maximale ainsi que les flux le long de chaque arc.

Il arrive fréquemment également que l’on doive considérer des réseaux avec des capacités localisées non seulement sur les arêtes mais également sur les sommets.

C’est notamment le cas pour les réseaux téléphoniques pour les-quels la limite de capacité est autant due aux lignes qu’aux centraux. On peut ramener aisément ce problème au précédent ; il suffit de dédoubler chaque sommet en une entrée et une sortie liées par un arc ayant pour capacité celle qu’on attribuait précédemment au sommet.