De nombreux problèmes en informatique peuvent être représentés par un graphe composé de nœuds et de liens entre eux. Les problèmes de flux de réseau impliquent le transport de biens ou de matériaux sur un réseau, par exemple un système ferroviaire.
Vous pouvez représenter un flux de réseau par un graphique dont les nœuds sont des villes et dont les arcs sont des lignes ferroviaires entre eux. (Ils sont appelés flux car leurs propriétés sont semblables à celles de l'eau qui coule à travers un réseau de tuyaux.)
Une contrainte clé dans les flux de réseau est que chaque arc possède une capacité, c'est-à-dire la quantité maximale pouvant être transportée dans l'arc sur une période fixe.
Le problème de flux maximal consiste à déterminer la quantité totale maximale pouvant être transportée dans tous les arcs du réseau, en fonction des contraintes de capacité.
La première personne à avoir étudié ce problème était le mathématicien russe Tolstoï, dans les années 1930. La carte ci-dessous montre le réseau ferroviaire réel pour lequel il souhaitait trouver un flux maximal.
OR-Tools propose plusieurs résolveurs pour les problèmes de flux réseau dans ses bibliothèques de graphes.
Les sections suivantes présentent des exemples de problèmes de flux réseau et montrent comment les résoudre: