Recherche d'une troisième chaîne améliorante
Les marques avaient été réinitialisées après la mise à jour des flots correspondant à la deuxième chaîne améliorante.
On examine le point 0 qui est initialement le seul point de la file (indiqué sur le graphe en vert foncé).
Il a deux successeurs : le point 1 que l'on peut atteindre avec une augmentation de flot de 2, écart entre le flot qui circule dans l'arc et la capacité maximale de l'arc : Delta(1) = 2 et Origine(1)=0 ; le point 1 est devenu vert clair et a été mis à la queue de la file ;
et le point 4 mais l'arc (1,4) est saturé, aussi, on ne peut plus marquer le point 4 à partir de 0.
Le point 0, examiné, est devenu violet et a disparu de la tête de la file.
Le point 1 est en cours d'examen et est devenu vert foncé.
Il a un successeur qui peut être atteint par une augmentation de flot : le point 2.
Le point 2 est devenu vert clair, a été mis à la queue de la file, Delta(2)=2 et Origine(2)=1.
Le point 1, examiné, est devenu violet et a disparu de la tête de la file.
Le point 2 est en cours d'examen et est devenu vert foncé.
Il a un successeur qui peut être atteint par une augmentation de flot : le point 3.
Le point 3 est devenu vert clair, a été mis à la queue de la file, Delta(3)=2 et Origine(3)=2.
Le point 2, examiné, est devenu violet et a disparu de la tête de la file.
Le point 3 est en cours d'examen et est devenu vert foncé.
Le point 3 a pour successeur le point 7, mais il ne peut pas être atteint par une augmentation de flot car l'arc (3,7) est saturé.
Le point 3 a un prédécesseur non encore marqué : le point 4.
Comme l'arc (4,3) a un flux (non nul) égal à 1, on peut propager une augmentation de flot du point 4 jusqu'au point 3.
Des 2 unités parvenues au point 3, on peut en propager 1 jusqu'au point 4 en prenant l'arc à contre sens.
On a donc le point 4 qui est atteint et qui devient vert clair.
Delta(4) est égal à 1, le minimum entre Delta(3)=2 et le flux de 1 qui passe sur l'arc (4,3).
Origine(4)=-3 : pour indiquer que l'on vient du point 3, mais en prenant l'arc à contre sens et qu'il faudra donc soustraire et non pas additionner l'augmentation de flot sur l'arc (4,3).
On a ajouté, sur la représentation graphique, la petite flèche bleue sans valeur numérique pour indiquer que l'on prend l'arc à contre sens.
Le point 3, examiné, est devenu violet et a disparu de la tête de la file.
Le point 4 est en cours d'examen et est devenu vert foncé.
Il a un successeur qui peut être atteint par une augmentation de flot : le point 5.
Le point 5 est devenu vert clair, a été mis à la queue de la file, Delta(5)=1 et Origine(5)=4.
Le point 4, examiné, est devenu violet et a disparu de la tête de la file.
Le point 5 est en cours d'examen et est devenu vert foncé.
Il a un successeur qui ne peut pas être atteint par une augmentation de flot car l'arc (5,6) est saturé.
Il n'a comme prédécesseur que le point 4 qui est marqué.
L'augmentation de flot ne peut pas être propagée au delà du point 5 qui va donc devenir examiné et disparaître de la file.
Le point 5, examiné est devenu violet et a disparu de la file.
La file est vide, ce qui signifie qu'il n'y a plus de points marqués et non examinés dont on n'aurait pas encore analysé des propagations de flot potentielles.
On ne peut plus améliorer le flot. On est à l'optimum et on a trouvé une solution pour le problème de flot maximum de valeur 5 (somme des flots qui sortent de la source ou somme de flots qui entrent dans le puits)..
Quand le marquage se bloque, les marques donnent également une solution associée pour la solution du problème dual, le problème de la coupe minimale.
Ici la coupe minimale obtenue a été dessinée en rouge, elle coupe tous les arcs qui vont des points marqués (en violet) vers les points non marqués (en blanc).
La coupe minimale contient donc l'arc (3,7) de capacité 3 et l'arc (5,6) de capacité 2 et a donc une capacité totale de 5 qui est bien égale au flot maximal obtenu.
Il est à noter qu'une deuxième coupe minimale contient les arcs ((3,7) et (6,7) puisque tous les arcs qui entrent dans le puits sont saturés.
Remarque :
Pour le problème du flot maximal dans un graphe, il peut y avoir plusieurs solutions pour le flot maximal et/ou plusieurs solutions pour le problème de coupe minimale.
Remarque :
Pour pouvoir faire passer une plus grande quantité de flot sur un graphe, il faut être capable d'augmenter la capacité d'au moins une unité sur toutes les coupes minimales.
Ici par exemple, en augmentant la capacité de 1 ou 2 unités sur l'arc (3,7) qui appartient aux deux coupes, on pourrait faire passer 1 ou 2 unités de plus à travers le graphe puisque l'on avait une propagation de 2 unités qui atteignait le point 3.
Si, par contre, on ne peut pas augmenter la capacité de l'arc (3,7), alors il faudrait augmenter la capacité des arcs (5,6) et (6,7) pour gagner une unité. Pour en gagner une deuxième, il faudrait recalculer les coupes après ces modifications.
En général, on associe des coûts au fait de pouvoir augmenter la capacité de certains arcs et on obtient alors un nouveau problème : recherche d'un flot de valeur v à un coût minimal.
