Ravi de savoir que cela t'aide !

Bon courage pour l'examen !

Bonjour Hind, Non v(f) = 17 n'est pas possible. Tu peux le constater en examinant cette coupe S = {s,2,4,5} et T={1,3,t} qui a une capacité de 13. Donc impossible de faire passer plus que 13 unités dans ce graphe. Hadrien

Bonjour Josh, Je ne comprends pas l'astuce en question. En quoi consiste elle précisément et en quoi permet elle de gagner du temps ? Quand tu exécutes l'algorithme à la main, tu peux partir de n'importe quel flot réalisable. L'algorithme peut être initialisé avec un tel flot. Donc si tu veux gagner du temps, tu peux essayer de construire très vite le plus gros flot possible "à la main", par exemple en cherchant juste des chemins qui ont une capa résiduelle positive dans le graphe d'origine et en les saturant de flot. Dès que tu ne voies plus comment augmenter un tel flot intuitivement, tu démarres l'algorithme et tu construits le graphe résiduel. Bon travail !

Bonjour Oumou, Le flot max vaut 13 (v(f) = 13) donc tu as une erreur. La capacité de la coupe que tu donnes vaut c_s1 + c_s4 + c_23 + c_5t = 9+5+2+4=20 si je ne me trompe pas. Donc je ne comprens pas non plus ton 29. Par ailleurs si tu as trouvé le flot max, tu dois fournir une coupe de capacité égale pour faire la preuve de l'optimalité. Dans ce graphe il y a un flot de valeur 13 et une coupe de capacité 13.

Le flot max n'est pas forcément unique, il peut y avoir plusieurs flots différents ayant la même valeur maximum, essaye de faire un exemple simple par toi même d'une telle situation.

@@rechercheoperationnelle8907 Bonjour, merci beaucoup pour votre retour, en effet j'avais pas bien compris l'algorithme et j'avais omis des détails en revenant sur votre vidéo, j'ai refait l'exo à la fin de la vidéo et j'ai obtenu 13 comme la valeur du flot et comme capacité de la st-coupe.Encore merci (:

@@oumoudembele6212 Cool :)

Bonjour, Le flot max vaut bien 13. Tu peux indiquer la coupe en donnant la partition exacte: S = {s,2,4,5} et T={1,3,t}. Je vais effacer ta réponse quand tu auras lu la mienne ! j'espère que ça t'aide, bon travail !