RO03

Flot de circulation

Les problèmes des flots apparaissent quand il s’agit de maximiser (ou minimiser) la quantité transportée d’une ou plusieurs sources vers une ou plusieurs destinations. Ce problème est modélisé par un graphe valué, appelé réseau de transport.

Un exemple pratique serait un réseau routier qu’entretient une ville. On s’intéressera par exemple dans ce cas à calculer le nombre maximum de voitures pouvant circuler par heure à travers ce réseau, et à augmenter ce nombre en créant d’autres voies ...