Le problème de flot maximal

De tous les problèmes de flot dans les réseaux, le problème du flot maximal (ou flot max pour les intimes) est assurément le plus simple. Il consiste à tenter de faire circuler sur le réseau la plus grande quantité de flot possible. Pour ceci, on fixe arbitrairement la contribution de la source à $+\infty$. Une alternative consiste à supprimer les contributions des sommets $s$ et $t$ et à rajouter un arc $(t,\, s)$ de capacité infinie et appelé arc de retour. On appelle valeur du flot et l'on note habituellement $v$ la somme du flot sortant de la source (ou entrant au puits). Soit donc :

$$v=\sum\displaystyle_{i:(s,\,i)\,\in\,G}x_{si}\quad=\quad \sum\displaystyle_{j:(j,\,t)\,\in\,G}x_{jt}$$