Problème de flot maximum

Carte Commune · n° 390667

Le problème de flot maximum consiste à trouver, dans un réseau de flot, un flot réalisable depuis une source unique et vers un puits unique qui soit maximum. Quelquefois[Quand ?], on ne s'intéresse qu'à la valeur de ce flot. Le s-t flot maximum (depuis la source s vers le puits t) est égal à la s-t coupe minimum du graphe, comme l'indique le théorème flot-max/coupe-min.

Lire sur Wikipédia · Image Min_cut.png: Maksim derivative work: Cyhawk (talk), CC BY-SA 3.0