AALG5: Flow networks, maximum bipartite matching example

[@yelgabs]

After a million tutorials on this topic, I finally understand this topic...
Everyone else seems to overcomplicate things.

[@MakisHMMY]

minor mistake, i think on 2:27 the second maximum matching example is wrong, since it only has 3 edges, instead of 4.
Thank you for the content, really helped me understand the definition

[@NatchaRANCHAN]

So to get the maximum matching i just have to draw the path from bipartite graph like the final result of network flow?

[@jayush8480]

Thank you so much for this fantastic explanation

[@bennurkaya4709]

I'm so grateful...

[@michagarmulewicz4536]

thanks, this is remarkable explaination

[@jemmamariex3]

thanks for the explanation! One question though, why is the upper bound |v|+1? You mentioned that v is the number of vertices, so what does the +1 do?

[@simonassaltenis7839]

It is the length of the augmenting path in terms of the number of *edges*. Look at the path that I drew in the residual network and count the edges. Each vertex from |V| has an edge before it in this path (so |V| edges), plus there is an edge before t.

[@rushikeshmokashi1931]

@@tw6428 yes

[@CristinaA-q6r]

wow i actually understood immediately! thank you so much!

[@test_deneme]

what happens if you increase the all edges capacity as n+1. Ofcourse we will think that |A| =|B| =n.

[@danieldude15]

Good Job! very clear. would you know where can i find information regarding proof of correctness of this algorithm?
I mean why does this promise maximum matching?

[@simonassaltenis7839]

As you can see, the video refers to the popular "CLRS" textbook (mitpress.mit.edu/index.php?q=books/introduction-algorithms). It includes proofs of correctness. In particular, Max-flow min-cut theorem (Theorem 26.6 in CLRS) proves that Ford-Fulkerson finds a maximum flow, then Lemma 26.9 shows that we correctly find a maximum bipartite matching, if we transform the problem into a max-flow problem as shown in the video.

[@danieldude15]

Thank you very much!
how did students manage before the internet?

[@justANovaLoom]

Incredible, thanks u!

[@AtaollahShakeri]

Thank you a very useful learning
it worthies to watch a again

[@dhananjayans]

Awesome explanation (y)

[@jasmeet17mast]

Nice Video Prof!
Thanks

[@SuryaPrakashVIT]

Super sir you made to understand it easily thank you

[@anachoretix]

Thank you very clear lesson.

[@pauliewalnuts6734]

thank you this was amazing

[@guzh]

The residual network is unclear.

[@zahirjacobs716]

What's the textbook you are using?

[@simonassaltenis7839]

+Zahir Jacobs
mitpress.mit.edu/index.php?q=books/introduction-algorithms

[@MrKingoverall]

Thank you sir !

[@noyanali1776]

that's great! cool too!

[@Quas94]

Thanks for this video!

[@yousofkakhki1223]

thanks but your solution is wrong ! the good upper bond is 2*min{ |L| + |R|} + 1

[@spongebobheaven]

THANK YOU SO MUCH!!!!!!!

[@shreyasmohan7151]

the man stuttered so much i couldnt understand half of it

[@bigDeeOT]

Thanks for this

[@laurrsxo]

[@WahranRai]

You had better to change the color of your pens !!! we saw nothing in board

[@bigDeeOT]

+WahranRai I saw the board fine

[@WahranRai]

+bigDeeOT
8:45 I am talking about the gray arrows showing the paths.
Another color (red for example) will bring to light the paths !!!

[@bigDeeOT]

+WahranRai
I can see it clearly.

[@webdarkking]

@bigDeeOT No one gives a fuck what you see or not. He is here to learn and if he can't see it, he can't see it.

[@douwehuysmans5959]

@@webdarkking Civil translation: While it may be true that you can see it fine, for a teacher it is important that all students can get along, therefore he appreciates this feedback so he can change the color of the font, so everyone can get along and not just the people with the best eyesight.

[@zxoowoo6094]

clear