Théorème flot-max/coupe-min

Le théorème flot-max/coupe-min (ou max flow/min cut en anglais) est un théorème important en optimisation et en théorie des graphes. Il stipule qu'étant donné un graphe de flots, le flot maximum pouvant aller de la source au puits est égal à la capacité minimale devant être retirée du graphe afin d'empêcher qu'aucun flot ne puisse passer de la source au puits. Ce théorème est un cas particulier du théorème de dualité en optimisation linéaire et généralise le théorème de Kőnig, le théorème de Hall (dans les graphes bipartis) et le théorème de Menger (dans les graphes quelconques). Théorie des graphes#Flots dans les réseaux Soit un graphe orienté. Un graphe de flots vérifie les deux conditions suivantes : il possède deux sommets particuliers distincts, une source et un puits ; chaque arc de possède une capacité, qui représente le flot maximum pouvant passer par cet arc. Cette capacité est positive. Un flot dans un graphe de flot est une fonction qui, à chaque arc , associe une quantité . Un flot doit vérifier les conditions suivantes : la contrainte de capacité : pour tout arc ; la loi de conservation du flot : pour tout sommet . Cette contrainte s'appelle aussi la loi des nœuds des lois de Kirchhoff. La valeur du flot, notée , est la quantité de flot allant de la source au puits. Elle est égale à la quantité de flot sortant de la source : . Problème de flot maximum Le problème de flot maximum est le problème de maximiser la quantité de flots allant de la source au puits. Cela se traduit par la maximisation de la valeur du flot . Coupe minimum On appelle coupe s-t de un couple de sous-ensembles de sommets disjoints d’union tels que et . La capacité de la coupe , notée , est la somme des capacités respectives des arcs de à , soit Le problème de coupe minimum est la minimisation de la capacité , c'est-à-dire la recherche d'une coupe qui minimise la capacité de la coupe s-t''. Le théorème flot-max/coupe-min est le suivant : Le théorème a été prouvé par Lester Randolph Ford junior et Delbert Ray Fulkerson en 1954, l'article est paru en 1956.