Flots 2 : l'algorithme de Ford-Fulkerson pour construire un flot max.dans un graphe

[@suprayz5321]

3 ans qu'on fait le même truc en informatique, en licence et en master et toujours je regarde ta vidéo pour me réviser, merci infiniment !

[@EL-KHABIR]

Algorithme Ford-Fulkerson (Flot maximal) Méthode marquage kzbin.info/www/bejne/j5-uiX13rbp0q5Y

[@HelenaWelo]

J'ai partiel et j'ai passé des heures sur mes notes sans rien comprendre, et votre vidéo a tout débloqué. Merci infiniment!

[@remichevallier8934]

Super Vidéo, hyper claire, ça a sauvé 120 personnes de ma promotion pour nos partiels d'optimisation! Un grand grand merci

[@lucasph5481]

inchallah ça va nous sauver

[@remichevallier8934]

@@lucasph5481 mdr, vous ici? étonnant , vraiment!

[@theoberra6979]

Quel bonheur de comprendre, merci Rémi! 😂

[@paullandais8653]

@@lucasph5481 hello august quand même pour toi

[@remichevallier8934]

bordel mais y'a toute l'indiana à cette heure là sur cette vidéo XD z'etes les pires ^^

[@clementoberhauser4467]

Merci pour la vidéo, j'ai 22 ans et j'adore

[@k2no548]

J'ai regardé la video avec la vitesse*1.5 et j'ai bien commpris. Merci beaucoup Monsieur

[@elieamar9923]

Bravo, c'est expliqué a la perfection !

[@Melia-200]

Merci boucoup monsieur . Que dieu vous facilite la vie .

[@benjamindeporte3806]

Toujours aussi excellent. Un grand merci.

[@nanyymelancc]

c'est d'une clarté ! merci infiniment, vous m'avez sauvé un temps fou, je suis en licence en espagne et comprendre la professeur est très compliqué

[@a_la_decouverte_des_graphes]

Merci ! Tant mieux si ça vous a aidé à suivre vos études..

[@Herbus2142]

J'ai eu 100% des points sur un exercice portant sur Ford-Fulkerson merci ! J'espère qu'on vous verra expliquer d'autres algorithmes de sciences informatique comme Floyd-Warshall.

[@EL-KHABIR]

Algorithme Ford-Fulkerson (Flot maximal) Méthode marquage kzbin.info/www/bejne/j5-uiX13rbp0q5Y

[@nizarjdoub6126]

Explication très pertinente!! merci chef

[@lyka8509]

merci beaucoup, j'aime bien votre méthode. bonne continuation .

[@a_la_decouverte_des_graphes]

ly ka . Merci pour votre retour.

[@vagnonaandrianandrasana-di6373]

Merci beaucoup, mon partiel va bcp mieux se passer mtn :)

[@a_la_decouverte_des_graphes]

Bonne chance !

[@mokrzyckimaxime3113]

Merci ça m'a sauvé tu régales

[@a_la_decouverte_des_graphes]

Mokrzycki Maxime. Heureux que ça soit utile.

[@faizkami]

بارك الله فيك شيخ

[@sanasa2496]

Merci beaucoup monsieur

[@DaulianeAlidaTCHOMTSEU]

Merci beaucoup mais j'ai une question : sur quelle base a partir de la source on choisit d'emprunt un chemin plutôt que l'autre ?

[@yeskouyesko3079]

Merci infiniment ❤

[@droidcheat4396]

Bonjour, la coupe (bleue) aurait-elle pu être seulement composée des sommets {S,a,e} ?

[@thiagoturri4167]

Très util et très clair, merci beaucoup !

[@anas.2k866]

Salut, pour le choix des chaînes améliorantes est-il aléatoire ? Si oui est ce que cela ne posera pas un problème pour des grand graphe car lors des choix des chaînes on serait pas capable de savoir est-ce que on a déjà choisit cette chaîne ou pas. Merci d'avance

[@a_la_decouverte_des_graphes]

anas .2k. En fait il y a des façons judicieuses pour choisir les chaînes améliorantes mais pour les décrire il faudrait un peu plus de temps de présentation. Je vous invite à consulter de la documentation (livre. page Wikipedia,...) plus précise pour en avoir une description. Si vous les choisissez aléatoirement par exemple l’algorithme va marcher mais vous n’aurez pas la garantie d’une exécution avec une complexité polynomiale...

[@anas.2k866]

@@a_la_decouverte_des_graphes D'accord! Merci

[@oualid1598]

Grand merci pour vos vidéo, vous m'avez tellement apporté ! Est ce qu'une vidéo concernant le flow de coût minimum est prévue ?

[@a_la_decouverte_des_graphes]

Merci pour votre commentaire. Pour l'heure je n'ai pas prévu de vidéo sur ce thème.

[@Lachainedaure]

le sexxe est toujours aussi dur

[@smartlearners3257]

Belle vidéo, svp Comment trouve t-on la coupe minimale ici?

[@abdelkarimsmaili3234]

merci bcp

[@a_la_decouverte_des_graphes]

Il existe des stratégies pour ‘’bien’’ les choisir mais c’est un sujet que je n’ai pas abordé. Si vous les choisissez de manière ‘’quelconque’’ vous aboutirez bien au résultat mais ça sera peut-être plus long qu’avec ces ‘’bonnes stratégies.

[@abdelkarimsmaili3234]

@@a_la_decouverte_des_graphes merci bcp...autre temp svp fait un video sur la construction d'un couplage avec le deroulement (algorithme)

[@a_la_decouverte_des_graphes]

Il y a déjà deux vidéos sur les couplage sur ma chaîne... dont celle qui a pour titre flot 3

[@Quentinfulldrunk]

Partiel de Opti et RO demain, c'est clair et net merci !

[@gabfernand2702]

bonjour , t'avais validé?

[@Quentinfulldrunk]

@@gabfernand2702 Yes ! Avec 12.5, je viens de regarder mon relevé de notes Je ne comprenais pas grand chose et en regardant plusieurs vidéos ici j'ai pu comprendre déjà mieux !

[@cruelsun5206]

pourquoi est ce qu'il ne choisit pas une flêche rouge entre c et t pour la st coupe ?

[@MkNiTrooX]

Bonjour, comment cela fonctionne pour un graphe non orienté ?

[@michelkumaluta5822]

Mon sujet de mémoire de fin d'études en Génie Informatique/ université de Kinshasa (UNIKIN) 🇨🇩

[@ninanour9325]

merci infiniment !

[@eventdz6182]

quation svp asq on peut dit -s-e-d-a-b t 5:38 un chain mal gres un a->d

[@a_la_decouverte_des_graphes]

Désolé mais je ne comprends pas votre question...

[@feanordunoldor7889]

Tu m'étonnes XD

[@eventdz6182]

XD XD

[@saidameftah2209]

Merci Msr pour votre video, en fait j'ai une question : pourqoui vous n'avez pas dit que le arc 'ct' est un arc sature comme 'dt' et 'dc' ?? merci d'avance!

[@a_la_decouverte_des_graphes]

Car l'arc (c,t) ne "traverse" pas la st-coupe. Ces deux extrémités, c et t sont dans le même ensemble de la st-coupe. Ils ne comptent donc pas dans le calcul de la capacité de la st-coupe mise en lumière dans la vidéo.

[@saidameftah2209]

@@a_la_decouverte_des_graphes merci

[@omarelmellouli3317]

svpj ai pas compros

[@MrWabouz]

Bonjour, très bien expliquée ! L'algorithme est-il bien déterministe ? 🤔 Puisque même en prenant "au hasard" les chemins, on a peu de chemins augmentants et je suis tenté de dire qu'on retombera toujours dans les mêmes situations pour un graphe donné...

[@a_la_decouverte_des_graphes]

Dans cette version de base présentée ici vous pouvez choisir les chemins améliorants comme vous voulez. Au bout du compte vous aurez bien un flot max. Ce qui va faire la différence entre telle et telle façon de choisir est le nombre d'itérations pour arriver au résultat.

[@MrWabouz]

@@a_la_decouverte_des_graphes super ça confirme ce que je pensais, merci beaucoup ! :) Aussi, à la fin vous parlez de la coupe de flot min qui sépare le graphe. Je trouve différentes versions de l'algorithme de Ford-Fulkerson dont beaucoup ne mentionnent pas cette coupe. Comment la trouver ? Je pense par exemple à un BFS un pour chercher les arc/arêtes limitant(e)s🤔

[@a_la_decouverte_des_graphes]

Effectivement la coupe ne fait pas directement partie de l'algorithme de base de F@F ou de ses dérivés car il s'agit pour eux de trouver un flot max. Par contre il est possible de trouver une telle coupe à partir du "produit" d'un de ces algorithmes. C'est un peu long à expliquer dans un commentaire. Je vous invite à consulter un livre de flots ou, peut-être, les pages wikipedia sur ces sujets.

[@simhaackermann8832]

Bonjour, je vous remercie pour vos explications, je reste cependant avec 2 questions: 1) Comment choisit-on le chemin a emprunter de la source au puits a chaque étape? Ceci influence forcement le flot maximal que l'on obtiendra. 2)Pour quelle raison peut-on diminuer de 2 la valeur de l'axe (ad) pour pouvoir l'emprunter et ne peut-on pas diminuer la valeur de l'axe(ab) par la suite? En vous remerciant par avance,

[@a_la_decouverte_des_graphes]

Bonjour. 1/ Dans l'algorithme de F&F, on choisit une chaine améliorante quelconque, tant qu'elle permet d'améliorer la valeur du flot. Par contre dans des versions plus raffinée (non décrites ici) il y a des règles (que je n'explicite pas dans ma vidéo) qui permettent de faire de "meilleurs" choix. 2/ Voir dans ma vidéo la règle que je rappelle : si on prend un arc à l'envers (dans le sens inverse de la flèche) alors on diminue la quantité de flot (mais elle ne doit jamais être négative) et si on prend un arc à l'endroit (dans le sens de la flèche) alors on augmente la quantité de flot (sans jamais dépasser la capacité de cet arc). L'arc (ad) est pris à l'envers et (ab) est pris à l'endroit. Je vous invite à réfléchir à la raison qui pousse à faire cela et à appliquer cette règle qui semble un peu contre-intuitive a priori...

[@simhaackermann8832]

Je vous remercie pour votre réponse, d’après mes lectures, dans l'algorithme F-F, on peut effectivement choisir une chaîne améliorante quelconque, contrairement a Edmonds-Karp, qui ne fonctionne qu'avec BFS . Wikipedia: The path in step 2 can be found with for example a breadth-first search (BFS). If you use the former, the algorithm is called Edmonds-Karp.

[@a_la_decouverte_des_graphes]

Simha ACKERMANN. Oui c’est une des variantes.

[@lyka8509]

j'aimerais bien si vous partagez une autre vidéo comment trouver le flot maximum de coût minimum .

[@IslamWeldMalek]

❤ thank you

[@sue5973]

thanks for the explination

[@Overdrink7]

Super explication

[@a_la_decouverte_des_graphes]

Merci ! Il y a d’autres vidéos sur les flots sur la chaîne, allez les voir...

[@mezennersarah6450]

Monsieur pouvez m'aider svp ? Le prof ma demandé de faire la résolution du flot maximum par la programmation linéaire et le simplexe ( pour mon mémoire fin d'étude) pouvez-vous me donner une idée svp ?

[@soufianeboutahiri327]

merci beaucoup :)

[@aymericpelletier2630]

Incroyable

[@a_la_decouverte_des_graphes]

Qu'est-ce qui est incroyable ?

[@GasherProdStudio]

À la découverte des graphes Sûrement votre pédagogie !

[@عبدالباسطبريكاتالقناةالثقافية]

Super!

[@lakehalhadjer7478]

ohhh thank u mister ❤❤❤

[@متعةالرياضة-خ3ص]

j ai pas compris comment choisir la zone rouge et bleu

[@a_la_decouverte_des_graphes]

Ce n’est pas expliqué dans la vidéo. Cela demanderait d’aller plus en détail.

[@متعةالرياضة-خ3ص]

@@a_la_decouverte_des_graphes dcrr mrc bcp

[@cedricvumisa7416]

merci beaucoup

[@elalem4952]

Thanks indeed sir

[@marwahero6843]

slt monsieur jspr tu voix mon commantaire svp fais l'algorithme de bellman ford jai besoin dans mes examens bientot

[@nesrinehached6533]

Merci

[@a_la_decouverte_des_graphes]

Nesrine Hached. Je vous invite à regarder aussi la 3ème vidéo sur les flots ainsi que... toutes les autres de ma chaîne ! N’hésitez pas à la recommander aussi autour de vous si vous connaissez des gens qui travaillent sur ce domaine.

[@donquijotedice8317]

Merci!!

[@a_la_decouverte_des_graphes]

Regardez aussi les autres videos sur le même sujet.

[@lydiahadjout1208]

Pour l'arc ct on a 1 donc il est saturé nn ?? 🙄

[@a_la_decouverte_des_graphes]

Oui, et alors ?

[@lydiahadjout1208]

Pour on compte ps sa valeure !!

[@lydiahadjout1208]

Comment choisir les arc saturé qu'on doit calculer

[@a_la_decouverte_des_graphes]

@@lydiahadjout1208 la méthode pour les trouver n'est pas détaillée dans la vidéo. Ce n'est pas très compliqué mais trop long à expliquer dans une vidéo de vulgarisation.

[@lydiahadjout1208]

Vous n'avez pas compris ma question dans cette exemple vs avez calculer la capacité de 3 arc selment (ab)(dc)(dt) je veux savoir pourquoi on a pas calculer la capacité de l'arc (ct) "sinn c grâce a vs que j'ai compris et j'ai adorée la théorie des graphes MRC bcp monsieur "

[@alaeddinebensalah7019]

vous avez une faute la somme des arcs entrante < arcs sortante 9+4< 10+1+3

[@a_la_decouverte_des_graphes]

Non ce n'est pas une faute. Il est tout à fait possible que la somme des capacités des arcs sortants de la source soient différente de la somme des capacités des arcs entrants dans le puits. Revoyez la première vidéo sur les flots.

[@paulnougarede3471]

bonjour

[@eventdz6182]

mrciiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii bc

[@a_la_decouverte_des_graphes]

De rien. Profitez aussi des autres vidéos sur ce sujet et abonnez-vous si ce n'est pas encore fait.

[@eikichio266]

trop de pubs ca y est

[@a_la_decouverte_des_graphes]

Et oui hélas. Pourtant ma chaîne n’est pas monétisée (je ne gagne pas d’argent). C’est Google…

[@madanybah8635]

Merci beaucoup

[@ariellelauviahboutandoubil2068]

Merci

[@mezennersarah6450]

Merci beaucoup

[@rondamounir7375]

merci