Max Flow Algorithme en temps linéaire, Trouver un flux valide

Question

Laissez-moi donc expliquer la question :

On vous donne un graphique. Vous trouvez le flux maximum. Mais il s'avère qu'une arête, e_i, avait la mauvaise capacité. Elle en avait une de moins. Malheureusement, le débit maximal a été atteint avec l'ancienne capacité.

Calculer le nouveau flux maximal en temps linéaire (en termes de nombre d'arêtes et de sommets) une fois qu'on vous a dit que e_i avait la mauvaise capacité.

Voici mon plan : (1) Vous ne pouvez pas seulement diminuer le flux à l'arête e_i par un à une arête car vous devez violer certaines contraintes : comme le flux est conservé à une arête. Fixez les flux pour obtenir un flux valide. Mais comment ?

(2) Quelqu'un m'a donné un conseil : il serait utile de montrer le flux valide = flux précédent -1.mmm...

Aide.

Answer 1

Voici quelques conseils :

1. Supposons que vous trouviez un chemin avec un débit non nul (c'est-à-dire >= 1 ), et contient cette arête e_i. Comment pourriez-vous utiliser ce chemin pour que le flux global redevienne valide ? Maintenant, supposons que l'on ne vous donne pas ce chemin. Comment pourriez-vous l'obtenir vous-même ?
2. Maintenant, vous savez que le flux maximum du nouveau graphe est soit le même, soit un de moins qu'avant (pourquoi ?). Comment pouvez-vous déterminer lequel des deux en temps linéaire ?