Recherche de la deuxième chaîne améliorante
Les marques avaient été réinitialisées après la mise à jour des flots correspondant à la première 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 4 : Delta(1) = 4 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)=4 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)=4 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é.
Remarque :
On pourrait penser que l'on ne peut pas propager le flot plus loin.
Mais en fait, on peut améliorer le flot en remettant en cause la manière dont on a fait passer les flux en utilisant le premier chemin améliorant.
Pour cela, on va utiliser une chaîne améliorante qui consiste à diminuer le flux sur les arcs à flux non nul que l'on prend à contre sens.
De manière concrète, cela signifie ici,
que 3 des 4 unités de flux qui peuvent arriver jusqu'au point 3 vont être envoyées vers 7, mais qu'en compensation, les trois unités qui allaient de 4 à 3 doivent être enlevées, mais il faudra alors trouver un autre chemin pour aller de 4 à 7 si on veut réellement augmenter le flot.
Comme l'arc (4,3) a un flux (non nul) égal à 3 et que l'on peut propager une augmentation de flot de 4 jusqu'au point 3. Des 4 unités parvenues en 3, on peut en propager 3 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 à 3, le minimum entre Delta(3)=4 et le flux de 3 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, une 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)=3 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 peut être atteint par une augmentation de flot : le point 6.
Le point 6 est devenu vert clair, a été mis à la queue de la file, Delta(6)=2 et Origine(6)=5.
Le point 5, examiné, est devenu violet et a disparu de la tête de la file.
Le point 6 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 7.
Le point 7 est devenu vert clair, a été mis à la queue de la file, Delta(7)=2 et Origine(7)=6.
Remarque :
On a marqué le puits, on a donc trouvé une deuxième chaîne améliorante qui va de la source au puits.
Comme Delta(7)=2, on va augmenter le flot de 2 sur les arcs avant de la chaîne et le diminuer de 2 sur les arcs pris à contre sens.
Pour modifier la chaîne améliorante, on va, comme pour les problèmes de cheminement, remonter les marques placées dans le tableau Origine.
Origine(7)=6 : flot de 2 sur l'arc (6,7)
Origine(6)=5 : flot de 2 sur l'arc (5,6)
Origine(5)=4 : flot de 2 sur l'arc (4,5)
Origine(4)=-3 : flot diminué de 2 sur l'arc (4,3)
Origine(3)=2 : flot de 2 sur l'arc (2,3)
Origine(2)=1 : flot de 2 sur l'arc (1,2)
Origine(1)=0 : flot de 2 sur l'arc (0,1)
Origine(0)="##" : on reconnaît la source 0.
On a modifié les flots sur la deuxième chaîne améliorante.
De nouveaux arcs sont saturés, alors que l'arc (4,3) n'est plus saturé.
On a également réinitialisé les tableaux de marques puisque les flots et les arcs saturés ont changé depuis leur dernier calcul.
Remarque :
Après cette nouvelle modification des flots, on peut vérifier qu'en chaque point du graphe, le flot est bien compris entre 0 et la capacité des arcs et qu'en outre le flot est bien conservatif.
Remarque :
Comme les deux arcs qui arrivent au puits sont saturés.
On sait déjà que l'on est à l'optimum et on connaît même une première coupe minimale qui consiste à placer tous les points sauf le puits d'un côté de la coupe et le poinot 7 seul de l'autre côté.
Le flot maximal trouvé est de 5 et la capacité de la coupe minimale est également de 5.
Néanmoins, pour montrer comment la technique de marquage peut permettre de trouver de manière systématique une coupe minimale, technique nécessaire en particulier, quand la coupe minimale n'est pas en aval de la source ou en amont du puits, nous allons poursuivre la technique de marquage et montrer comment elle se bloque en fournissant une coupe minimale.
