Pour ceux qui répondent à l'exercice: je supprime les commentaires contenant la réponse après avoir validé avec vous afin que d'autres puissent s'entraîner !
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, Soient 3 sommets du graphe i , j , k tels que : k -> i -> j Si le flot(k,i) > 0 et flot(i,j) < capacité(i,j) alors le graphe d'écart sera sous la forme : k j Dans mon cours, il est noté qu'il est possible de ne pas passer explicitement par le graphe d'écart à chaque itération mais qu'on peut utiliser l'astuce ci-dessus pour aller un peu plus vite. Je ne vois pas comment cette astuce prend tous les cas en compte ( par exemple si flot(arc) = 0 ou flot(arc) = capacité(arc) ) Merci d'avance.
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, j’ai eu v(f) = 9 S= (S,5,2) T=(T,4,3,1) Et le flot max = 9+1+2+7+4+9 = 29 Est ce correct ? Et existe t’il un unique flot max pour un graphe ? Merci d’avance.
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 (:
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 !
![ประสบการณ์ จ้าง Developer ที่ผมจะไม่มีวันลืม [ภาค2]](http://i.ytimg.com/vi/pZbsSDRrmXA/mqdefault.jpg)
Merci pour votre vidéo très intelligible et utile
Ravi de savoir que cela t'aide !
merci beaucoup !
Pour ceux qui répondent à l'exercice: je supprime les commentaires contenant la réponse après avoir validé avec vous afin que d'autres puissent s'entraîner !
Oooh j'ai compriiiis
Bonjour avec quel logiciel vous dessinez vos graphes ? Très belle présentation. Je vous remercie
Je fais tout ça sous keynote. Merci ! j'espère que vous allez la partager :) Bonne journée.
Merci
Merci😁
Bonjour Monsieur,
On a trouvé le v(f)= 17 est ce que c'est juste ?
En vous remerciant d'avance.
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,
Soient 3 sommets du graphe i , j , k tels que : k -> i -> j
Si le flot(k,i) > 0 et flot(i,j) < capacité(i,j)
alors le graphe d'écart sera sous la forme : k j
Dans mon cours, il est noté qu'il est possible de ne pas passer explicitement par le graphe d'écart à chaque itération mais qu'on peut utiliser l'astuce ci-dessus pour aller un peu plus vite.
Je ne vois pas comment cette astuce prend tous les cas en compte ( par exemple si flot(arc) = 0 ou flot(arc) = capacité(arc) )
Merci d'avance.
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 !
S = {S, 4, 5, 2}
T = {T, 1, 3}
C(S, T) = 5 + 4 + 2 + 2 = 13
J'ai un exam sur ça demain, j'espère que ça va le faire
Bon courage pour l'examen !
Bonjour, j’ai eu v(f) = 9
S= (S,5,2)
T=(T,4,3,1)
Et le flot max = 9+1+2+7+4+9 = 29
Est ce correct ? Et existe t’il un unique flot max pour un graphe ?
Merci d’avance.
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 :)
13
Oui 13. Mais as tu la coupe pour le prouver :) ?
S = 13
T= 13
C(s,t)= 13
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 !