Algorithmes : problème de flux maximal et coupe minimale s-t

Question

Soit G un graphe d'entrée pour le problème du flux maximal. Soit A une coupe s-t minimale dans le graphe. Supposons que nous ajoutons 1 à la capacité de chaque arête du graphe. Est-il nécessairement nécessairement vrai que A est toujours une coupe minimale ? Si oui, prouvez-le, sinon donnez un contre-exemple.

[Note : Je pense que la réponse est non, pas nécessairement, mais je ne peux pas trouver de contre-exemple]. Veuillez noter qu'il s'agit d'une question de devoir, je cherche un indice ou toute aide que je peux obtenir :)

Answer 1

Avec la remarque de l'utilisateur 57368, il est facile de construire des contre-exemples simples.

Par exemple, V={A,B,C,D}, E={(A,B,2,5), (B,D,1), (C,D,1)}. La coupe minimale est {(B,D), (C,D)} avec un poids de 2.

Si on ajoute le poids 1 à chaque arête, on obtient E2={(A,B,3.5), (B,D,2), (C,D,2)}. Voici la coupe minimale {(A,B)} avec un poids de 3,5.