13. Incremental Improvement: Max Flow, Min Cut

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
View the complete course: ocw.mit.edu/6-046JS15
Instructor: Srinivas Devadas
In this lecture, Professor Devadas introduces network flow, and the Max Flow, Min Cut algorithm.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu

[@anmol9096]

Wish I could sit in that room, answer your questions, get a frisbee :-) but it's still good. Thank you MIT for providing this level of education for free. If I grew up to earn sufficient money, I will surely donate so that you continue with this good work forever.

[@karansvnit]

Cut -> 46:45 Residual Graph -> 1:08:10 Augmenting Path -> 1:18:10

[@Kr4cKHe4D]

thanks mate haha

[@volimsamopare6946]

Thanks!!

[@Dontonethefirst]

You dropped this, 👑

[@wickshawn3994]

thanks bruh

[@ivanmartinezmorales3483]

Not all heroes wear capes

[@ilyakopyl]

I don't know how I would survive algorithm classes in my school without these MIT lectures.

[@matajuan366]

hookers and cocaine my friend

[@brendawilliams8062]

Watching it fit previous diagrams and rounding numbers is interesting

[@nguyenthanhdat93]

The lecture is phenomenal!! Thank you very much MIT for making this course open-source to the public !!

[@MatthewYe]

Only video about network flow I was able to understand - thanks MIT.

[@adrianbona]

You're rocking it, Srinivas 🎉

[@mikhailosiko]

Thank you very much! This was the first clear explanation of this topic. I highly recommend it to those who are studying "advanced algorithms" on coursera.

[@djtiner1]

Very straightforward and clear explanation and illustrative examples. It made me understand this interesting subject! You did in an hour and 20 minutes what my teacher didn't in 2 hours!

[@brendawilliams8062]

I felt the electric 📐 angle on it. A great lecturer.

[@matthewrister]

Love his enthusiasm!

[@ryanc7840]

A huge thanks and kudos to Professor Devadas.

[@M4D4F4K4.]

fuck have an exam next week with this topic. The professor only gave us a week to understand the material. Of course doable for smarties and exceptions but as a normal person. So intimidating.

[@BlackHermit]

The Frisbee of true Computer Science!

[@ivanserranohernandez434]

Thanks MIT for these great lectures!

[@adityakohli5160]

That's a very nice explanation !

[@anishbhanushali]

if anyone's want to jump directly on finding cuts, @ 1:07:00 he starts to explain how you find min-cut

[@Davio88]

thank you very much

[@foreveralice8311]

Great Lecture! Wonderful!

[@h4vret]

Excellent explanation.

[@jenuno2]

Perfect, thanks !

[@shreemaypanhalkar451]

Thank you very much.

[@khailai5204]

Amazing class!

[@mystmuffin3600]

How does the sum at 28:40 even work? The sum of flow values outgoing from all vertices except source and sink equals zero?

[@aybrl]

This is great. Thank you

[@xinli6243]

at 56:14 , one student asked a question about why don't we consider path s -> c. Sirinivas said when you don't have a particular edge from s to c, you can use skew symmetry to argue s->c and c->s cancelled out each other. I don't get his answer. We are considering f(S, T), why does c->s get involved and cancel s -> c?

[@brendawilliams8062]

I don’t know 🤷‍♀️. I just say in real life you need electricity or telephone poles.

[@jeongminyoun5388]

Please, show me upper graph when you explain residual graph network flow, I didn't know that how it works.

[@asian1599]

at 51:36, doesn't it break flow conservation since one of the nodes has 2 going in but 3 goes out?

[@OmarAhmed-od9rf]

What did that student mean at kzbin.info/www/bejne/jIq9eJ-dr9eSd9U?? We did consider c at f(d,c) which is -1 . Not sure what did he mean with his question.

[@avinashpatil8816]

He actually threw frisbee at students at an MIT lecture. That's hilarious....

[@F1mus]

Honestly, the camera guys need to pay attention to the lecture. When he asks about something that's on the board, don't point the camera at Srini. Point it at the BLACKBOARD, so that the viewer can also try to answer the question.

[@mostafaomar5441]

What was the point of disallowing self edges and cycles (u,v), (v,u) at 22:58? I'm not really sure I understand the difference between net-flow and positive-flow and the impact of the professor's assumption on the following definitions/constraints and therefore proof.

[@arjunsingh2183]

Self edges cause accumulation of flow which is not allowed. You can think of this as the amount of flow coming into a vertex must equal the amount of flow leaving it (like Kirchhoff's law for current flowing through wires). Cycles are accommodated by adding an intermediate edge so as to preserve that there was a direction of flow (the capacities remain the same along the newly added edges). This modification helps when we form Residual Networks as then we have the possibility of alternating (2 way) edges. Both these assumptions help significantly in proving the theorems discussed in the video.

[@malharjajoo7393]

How would you claim that using bottleneck value as the flow will always be correct ?

[@dipenbhuva2061]

Informative!! I am eating information like never before :)

[@varunnarayanan8720]

I have a doubt in the flow conservation formula. f(u,v) is 0 only for all edges between u and v right. If there's an indirect edge then we take it also as 0 right. In the case how f(s,t) also should be equal to 0 right as there's no direct edge between s and t?

[@yujeong8373]

Cool class

[@malharjajoo7393]

I think there is a small mistake at the end in the example. Edge from c-> t should be 0:2

[@amsainju]

The lecture is really good but the movement of the camera is making me dizzy.

[@malharjajoo7393]

The proof at 1:03:00 seems a bit odd. he has broken up the RHS term in the parenthesis into 2 parts( but the rules he gave earlier break the LHS term in the parenthesis )

[@viveksengupta]

you can always negate and break the LHS, same deal

[@junzhai1715]

a super short proof of the Theorem at 40:49: 0=f(V,V)=f(s,V)+f(t,V)+f(V-s-t,V) ({s}, {t}, V-s-t are disjoint sets). Since f(V-s-t,V) = 0 (by conservation property), f(s,V)+f(t,V)=0. i.e. f(s,V) = -f(t,V) = f(V,t)

[@jacobsalzberg8579]

That's the proof I come to as well when I try to come up with the proof on my own. Any idea why he uses a different method?

[@studyup6106]

46:46 cut

[@subhamraj2500]

Cut 47:00

[@shubhamtomar95]

How does f(u, v) work in skew symmetry when (u,v) are not connected by an edge?

[@sambennet1138]

It would be 0 = -0 since we define any (u,v) with no explicitly given capacity as 0

[@rifathasan6017]

is it related to gomory hu's algorithm?

[@snlgrg]

Can somebody Plz provide me the link to the next lecture, which is continuation of this one.. !!

[@mitocw]

+snlgrg If the next video (14. Incremental Improvement: Matching) isn't visible as the top recommend video in the top right column, see this playlist to see it and the rest: kzbin.info/aero/PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp

[@RayvinLai]

I saw Erik on the seat when camera zoom out

[@videofountain]

At the time point kzbin.info/www/bejne/jIq9eJ-dr9eSd9Um40s we can see some numeric summation and the graph diagram at once. That is helpful. Then after that we rarely see them both at the same time, which is not helpful. MIT does provide the pdf at their website for more clarity. Their is a unfortunate combination of red chalk, handwriting, and excess camera movement. There is a simple summation of values, positive and negative and the explanation does not reflect that simplicity. Looking at the pdf document and the video simultaneously is useful. MIT might consider full screen pip (picture in picture) and chalkboard centric view simultaneously for ease of viewing.

[@omercreateswords]

at 42:14 why f(s,V)=f(V,V)-f(V-s,V)?

[@junzhai1715]

because V-{s} and {s} are disjoint sets. By the third property, we have f(s,V)+f(V-s,V)=f(V,V)

[@pratyushvatsa7490]

His bag is actually a 4-dimensional container

[@osmankhalid2005]

Min-cut example part not clear.

[@inesoliveira7418]

my teachers never gave me frisbees

[@AmarVashishth]

Mr. Cameraman focus on the BOARD more than on the teacher.

[@videofountain]

The MIT site has (pdf) documents for the lectures which you might enjoy. You may also pause the video. You may want to have side by side windows on your computer to see both at the same time.

[@raynoldcsya8317]

i think the camera panning is automated right? seems like there is some tracking going on... If so that is pretty amazing

[@SannaFarrukh]

videofountain k

[@user-hs7qg5tt8t]

@@raynoldcsya8317 yeah imagine them holding the camera and track the board and professor for over 1 hour... a lot of endeavors

[@hendelsrkearny]

What's CLRS?

[@hendelsrkearny]

Yup. Thanks. It’s pretty overrated. If you go to Amazon, most of the reviewers are trying to sound smart and are just parroting each other. Then there are a bunch of negative reviews from people who are unhappy about damage to the copies they got. And then finally, there are some very well-thought-out and well-written criticisms of the book which really should be heeded. Amazing how mediocrity gains such credibility.

[@dkg4975]

I don't know about others but I don't like these kind of teachers

[@buraknuhemiroglu6033]

its unbelievable he managed to extend a simple 20 minute topic (at max ) and lecture it for 1 hour and 22 minutes. im in 1h15min and still havent seen a defn about ford fulkerson method which he tries to explain. completely trash. if you want to learn the algorithm, dont waste your time on this video, watch ucdavis, idk.

[@mr.arikodus7527]

Kanka 6 sene olmuş ama ben senin kadar köylü bir adam görmedim. Dersin ana konusu zaten ford fulkerson algoritması değil, adam algoritmanın çalışma mantığının altında yatan sebepleri ve teoriyi anlatıyor bazılarının da kanıtlarını veriyo. Bir sike sap olabildin mi çok merak ettim bu kafayla