Ford Fulkerson Flot maximal

[saad17453]

montrer que si la sortie s du reseau r ne peut etre maquer avec ford fulkerson alors le flot est maximal
-----

[Tryss]

Bonjour,

http://forums.futura-sciences.com/ma...ces-forum.html

Merci et au revoir

[saad17453]

Bonjour tout le monde
j'ai vu sur un exam la question suivante
montrer que si la sortie s du réseau r ne peut être marqué avec la procédure de marquage de ford fulkerson alors le flot (f0) est maximal

pour la démontrer j'ai essayé de procéder par ABSURDE donc j'ai fait :
Supposons qu'on ne marque pas la sortie S du réseau et le flot n'est pas maximal
Donc il existe un flot (f1)>(f0)
c.a.d il existe un arc tel que: f1=C (la capacité de cet arc)
et puisque (f1)>(f0) donc C>(f0) donc la sortie S va être marqué.absurde
Mais bon je ne sens pas que c'est juste je sens que quelque chose manque ou ne va pas
alors j'éspère avoir de l'aide.
Merci