Eliminer les arcs avec des capacités minimales non nulles

L'utilisation de capacités minimales entraîne des lourdeurs algorithmiques non négligeables. Aussi, il peut être judicieux de les éliminer avant le traitement du problème. Insistons néanmoins sur le fait que le procédé que nous allons expliciter peut conduire à un graphe si grand qu'il n'en justifie plus l'intérêt. Aussi, on pourra se reporter à [1] pour les techniques permettant de traiter directement les réseaux à capacités minimales non nulles. On peut considérer un arc $(i,\,j)$ de capacité inférieure $l_{ij} > 0$ comme un arc de capacité supérieure $u_{ij} - l_{ij}$ reliant un puits de contribution $b(i) = -l_{ij}$ à une source de contribution $b(j)=l_{ij}$. En effet, on remplace la contrainte de passage d'un minimum de flot sur cet arc par la disparition de la même quantité de flot en entrée et sa restitution en bout d'arc. La deuxième partie de l'opération consiste à éliminer le nouveau puits et la nouvelle source ainsi crées par l'opération précédente. Cette technique est illustrée sur la figure suivante :

Figure 5.3: Exemple de suppression des arcs de capacité inférieure non nulle