Travailler avec une seule source et un seul puits

Il est possible de ne travailler qu'avec une seule source et un seul puits. Ainsi, il est inutile de garder en mémoire la liste des contributions des sommets en dehors de celles de la source et du puits. On crée un sommet noté $s$ et appelé super source ou tout simplement source. Ensuite, pour chaque sommet $i$ tel que $b(i)>0$, on ajoute un arc $(s,\,i)$ de capacité maximale $b(i)$ et le tour est joué. Finalement, on pose $b(s)=\sum\limits_{i \in X \; b(i) > 0} b(i)$. Réciproquement, on crée un sommet $t$ (le puits) et une collection d'arcs $(i,\,t)$ pour chaque sommet de contribution négative et l'on pose $b(s)=\sum\limits_{i \in X \; b(i) > 0} b(i)$. La figure suivante montre comment appliquer ce principe sur un exemple simple.

Figure 5.2: Exemple de suppression de sources et puits multiples