Avant d’établir un projet de construction d’autoroute on désire étudier la capacité du réseau autoroutier, représenté par le graphe ci-dessous, reliant la ville E à la ville S.
Pour cela, on a évalué le nombre maximal de véhicules que chaque route peut écouler par heure, compte tenu des ralentissements aux traversées des villes et villages, des arrêts aux feux etc... Ces évaluations sont indiquées en centaines de véhicules par heure sur les arcs du graphe. Les temps de parcours entre villes sont tels que les automobilistes n’emprunteront que les chemins représentés par le graphe.
Quel est le débit horaire total maximal de véhicules susceptible de s’écouler entre les villes E et S ?
En utilisant l’algorithme de Ford-Fulkerson, augmenter le flot entre les sommets E et S jusqu’à ce qu’il devienne maximal. (La valeur initiale du flot : valeurs indiquées à côté des capacités)
