Network Flows: Max-Flow Min-Cut Theorem (& Ford-Fulkerson Algorithm)

we're going to talk about network flows and I don't want this video to be an exhaustive resource for this it's just going to be carrying the intuition to you of kind of the roadblocks that I had to understanding this concept so that you can understand this as well we have a graph here and this is called a flow Network and all it is is a directed graph which you can also call a digraph which is a set of vertices a set of edges so there's a set of vertices a set of edges and every one of these edges indicates a capacity we're going to denote that as C of E the capacity of the eath edge or edge e every single edge has a capacity C sub e and we have a start vertex which is a vertex with in degree zero and we have a sink T and a sink just means that it's a vertex with no outward going edges so it's out degree is zero and so what flow networks are all about is that each one of these edges are kind of like pipes and what our goal is is to drive as much water through these pipes as possible and these are just properties about the graph it has each edge represents a capacity we have a start water is going to be created from the start and the sink T this is where the water is going to want to end up so I think the best way to visualize this is imagine these are pipes instead of edges and this is the confusing thing if you see it this way it's more confusing when we get to the next part I'm going to show you but let me revisit for you okay so this is kind of the visualization we should have in our heads when we see this network right now there's no flow going through the network and flow is just this conceptual unit quantity where we're going to try to push it let's just imagine is water these pipes have a certain capacity and we cannot push more than the capacity of a pipe at any single moment in time and that means the maximum that we can ever push out of the start is going to be the sum of the capacities coming out of the start if we're able to push all of the flow out of the start then we've reached the maximum flow that we can even generate so if I filled up this pipe to going outwards and I fill up this one then that's three there's more restrictions on what we can do here so each Edge is going to have a certain amount of flow going through it it's going to we can denote that as f of e and so the amount of flow going to a certain edge it can't be less than zero and it can't be greater than the capacity of the edge so that's what restricts the amount of flow that we can push through any given edge and we haven't pushed any flow through this flow network yet so we're going to get to that part but we're just imposing some restrictions on what this is going to look like for us and so the value of a flow will denote that as V of F so the value of this flow that we're going to create is going to be the amount of flow that we can get to come out of the start vertex and we can see that the max you can never be as three because we'll have two coming out here one coming out there and then if we put out any more we're going to break the pipes so now this is just going to be three that's the sum of all of the edge capacities coming out of the start and we'll denote it like that so in this case it's it's going it's going to be three at the end of this once we're done pushing flow through but it's going to be the we say F out of SS but in this case we're just summing the amount of flow we're going to push through the edge capacities but not in every case will we be able to push as much water as we want so in certain networks we're going to be limited and that's going to bring us to max-flow min-cut our max flow that we can push out of the start will be limited by the minimum cut that we can find in this flow Network and we'll get to that but for now we're just trying to find an optimal flow and then we're going to draw that relationship later so we're going to get rid of this and so now what we can do is we can just eyeball this and decide what to do so we have a capacity of two capacity of 1 we see these guys are pointing that way this 3 is pointing down we have that one pointing that way that two pointing that way why don't we take a greedy approach we could just push as much capacity out of the largest edge coming off of the start so we can push to flow out but now that we've pushed to flow out we have to of this conceptual quantity of flow at the U there's another thing where we have to conserve flow so if 2 units of this water goes into u 2 units has to leave you as well so we could be greedy again we could push it through this 3 edge as much flow as possible out of here so we can go this way okay so what you just saw was we just pushed 2 units of water down this way so now you is happy two units of water are coming out of it what we're actually doing is we're following a path to tea finally reroute this water all the way we fill this final pipe and so this is it what is the value of our flow the the answer that question is how much flow is coming out of the start you see that the value of our flow is two but the issue here is have we maximized that value and we maximize the water that we can push through this flow Network and the answer is no we haven't maximized it and the reason is there's still one unit of water left here now we need to reassess what we're doing we are limited here if I push one unit of water this way where can that water go the water can't go up because this edge is coming down here it water can only flow down and then where this pipe is full going this way we can't break this edge this pipe will explode so we're stuck here and the key realization we can make is how much flow is going through here to how much flow is going through here to what happens if we backed off a bit here what happens if we erase some of the flow going through here we just push one unit through this pipe remember this pipes capacity is three well if we just push one unit of flow here by conservation we still have to push one unit out of U and V has too much coming out of it only one units coming to V so let's fix V the V T edge okay so now do you see what's happening now we fix the V T edge so now we said you you have two units of flow before we were pushing all two units so is great we've got used equilibrium we got you to equilibrium but now we have one unit of flow still left to push out of you and which way could that go it can go this way and now you is back to equilibrium so now this are we seeing what's going on here the greedy approach gave us a dead end and we couldn't get this last unit of flow out but now we realized if we back off on how much flow goes through here this U is still happy it got rid of the two units coming into it it got out one this way one that way and then V said okay now I have one unit coming my way well how do I get rid of it I go towards the T but now how do we maximize our flow we can push one unit of flow through the SV edge and now V has one unit of flow to get rid of because we just pushed one unit and now he needs to push it finally to tea so this is the optimized flow Network and why do we know that well what is the value of this flow we're pushing out three units of flow from the start and as a symmetrical statement we can say we're getting three units of flow to the end and so the values now three and we know that this is the maximum amount of water that we can create and push through this flow network because this is the maximum that the starts the starting Genesis edges can actually fit we only can ever create at maximum three units coming out of these start edges or else we would break the the very beginning edges so no more flow can be pushed through this network and we're complete we've reached the maximum flow so now that we've demonstrated how the greedy approach makes us get stuck and there's actually more optimal ways to push flow through this flow network we need to think about a way to systematize this and this is going to bring us to the ford-fulkerson algorithm which is the algorithm we're about to do to create a generic way to always find the optimal flow in a flow Network and again if you want to see proofs for all this there's great text books to reference I'll link them below we're not going to get into any of the deep proofs but we're going to go over the overarching intuitions before we get to the ford-fulkerson algorithm we need to lay a definition and it's something called a residual graph and all this is is it's not different from anything we were just doing that's why I wanted to lay down that intuition base right what we had before is the original so this is the original that's the original flow Network and each of these are capacities all of the pipes are empty there's no flow there's no water going through this network that's how I want you to think about this and now we're going to try to push water through this that's what we want to do that's our desires push as much water out of this start and through the network successfully to the sink vertex push as much water as possible what the residual graph is going to show us is it's going to precisely show us where can we undo flow and when Karen when can we push more flow and based on these two things we're going to be able to optimize how much flow we can push through our network so now let's go back to what our greedy approach did when we push two units of flow what happened we we we would push it along a certain path the path was su VT so this is what our greedy algorithm said and said push as much flow as possible from the largest edge and then just find its way to the end so now we push two units of flow from s tu and that's our path for every one of the edges on that path and we have three edges one two three on that path we're going to show what the residual would look like so if I push one unit of flow this way this is what the residual would look like so just follow me on this so why did we just do that this is saying there was a flow quantity pushed from s to u we can undo that by two this means that there are two units of flow at U which way can they go if we wanted to undo that action we could push two units back now that there are two units of flow at U we need to push that through this through this residual graph but this is going over an edge with value three so if we push two units over this three edge we can undo too this is saying from u to V push two units of flow now there's two units of V that means we can undo two units of flow push it back to you well we won't push it back we can just undo how much we're pushing from you that's what that's symbolizing but there's still more that can go through this edge its capacity is three so we actually can push one more unit of flow so the forward edges are going to symbolize hey can I push more flow over this edge yes because it's three we only push to the backwards edges the edge is pointing into this vertex you are saying we pushed that much from this vertex to the other we push two from u to V that means we can we can lesson up lesson up on how much we were pushing before and now there's two units of flow sitting here if we're still staying with what we were doing so now that needs to go over the capacity to pipe and this is why I said we want to start with the conceptualization as pipes because if you see these edges and we immediately jump two more edges it's very confusing what's happening just remember these are capacities they're not actually they're different from what's going on from here these are just capacities so this is two if we push two units of flow across now the residual graph is going to tell us we pushed two units from V to T I can back off by two units I can back off how much flow I'm pushing out but then I'm going to have to put it somewhere else by conservation that flow has to go somewhere but in this case it's just saying hey if you want to undo some flow you did here you can do that but you'll have to find another way to redirect it so now all the other edges stay the same so here's probably here this is why this is so important and this is possibly the most confusing part at least it was for me this residual graph has giving us a lot of information it's saying there's still one unit of flow I can pass from s to V and notice there's actually a path on this residual graph let's call it P Prime it goes SV jumps from V to u that's confusing and then you to T so this is really confusing because if we look at our original graph you're not allowed to go from V to u that's that's not allowed the edge goes downwards right but actually what our residual graph is really telling us is I can push one unit from s to V that's pretty obvious right there's still one unit of this this edge as one capacity I can push it but here's the biggest realization we can make there's two units of flow we can undo and we can drain back into U but what happens I have to get rid of it but because we found a path because P Prime is a path in the residual graph I know for a fact there is a way to redirect that flow to get it to the end in a way that creates more space or allows us to increase the value of our flow so what happens is remember how you saw we kicked back one unit of flow back into U and redirected it our residual graph is literally telling us let me push one unit this way and then let me pull back one unit here and then I'll push one unit that way so what our residual graph is telling us it's not directly telling us which way the flow goes it's telling us which which edges are critical to look at if we want to maximize the flow that's what it's telling us and and this is actually the basis of the ford-fulkerson algorithm this brings us to following the residual path this is the next jump I want you to make we were at the original graph we were dealing with capacities there but this is the next large jump what we can do here is we can push one unit of flow this way so this edge goes backwards were following that SV path so we finished this edge we finished the SV edge but now the UV edge so the UV a Janine's to be dealt with so what is this telling us if we just pushed one unit of flow this way and we want to follow the path through the residual graph to optimize the global flow this edge going forward is not saying it's not saying push V to u it's not saying that it's saying undo one unit of flow and if I undo one unit of flow what is what do the new arrows become the new arrows become this right they become this because now how much how much can we undo going from u to V we can undo one unit of flow because we only pushed one we pulled back a bit at U but now you need to get rid of one more unit of flow we're following the P prime path here's our final edge and this is not saying the flow goes this way it's just optimizing the the actual max flow we were trying to achieve before fault by by augmenting paths that can push flow and pulling back on edges that can pull back flow and redirects but now we're at the U now we can redirect that one unit of flow this way and so this residual graph if we look at it is actually telling us the value of the flow we're saying I can undo to going out of this start I can undo two and then one that's a total of three so the value of the flow is three and so this brings us over here the we see that we were able to get three units of flow into the sink T so that's that's a symmetric statement to what we were saying there because if we got it out of here and got it there in the first place we would never pushed flow if there wasn't an ST path in the residual graph we would have never adjusted the flow we were pushing so now that we saw the original graph and then after that we saw what immense to push flow and then we saw the greedy approach and now we saw the residual graph which gives us a more intelligent way to bring back flow and redirect it we're not going to actually get into the proof of why this generates an optimal flow every time but we're going to get into the overarching pseudocode of the ford-fulkerson algorithm and then from there you can draw your own generalizations and now that you have this intuition underneath everything l should be a bit more straightforward to grasp so as a high-level overview the ford-fulkerson algorithm is going to start every single edge start the flow going every single edge as zero no flow will traverse any edge not the start not the end not any edges in the middle so that says the flow for every single edge every single edge that's an element of the edges is going to be zero and so next now that the flow is zero we're starting with all empty pipes like before exactly what we're doing before next we want to continue to push flow through the residual graph and we won't get into proving why this actually works but push flow through the residual graph while we saw there was an ST path in the residual graph that indicated a smarter way to redirect flow so while a path exists from s to T in G Prime learn the residual graph we're going to push flow so this is a while loop we're going to extract a path and we can do this with breadth-first search and Big O V Plus E time we're going to extract a path then we're going to try to push flow through that so we're going to pull that path out into a variable P follow this path and the residual graph and we're going to augment this path it's we will call it augmenting and so while we're doing this we're going to be updating the original graph G and then after all this is over we're going to want to update the the flow value the actual number value of the flow and we're going to want to update the residual graph to reflect the new meta information about where flow is going in the graph and so that is kind of the overarching view the residual graph is giving us critical information about what to do in the original graphs flow and then once we operate on the original graph along that path then we're going to have a more optimized flow and we're going to update the residual graph at the final step so next iteration our residual graph is fresh so that we can see is there another path where we can improve the flow in the original graph so now we're going to talk about max flows and min cuts and I'm not going to go too deep into this all the proofs all of the really definition heavy stuff I'll leave to the textbook but we're going to get into that very quickly so basically what the max-flow min-cut theorem states is we we want to take an ST cut so what is a cut a cut is a partitioning of the vertices into two disjoint subsets so what does that mean that means that the Union the union of these two partitions we take is going to be the original set of vertices but the intersection the intersection is the empty set and that is what a cut is going to do it'll literally cut the graph along a certain line so think of it like that that's a cut the a has s B has u T and V so what we're trying to do is we're trying to find the capacity we're trying to find the capacity of the edges crossing this partition so let's imagine this if we take a cut like this and I'm going to keep the edges out of the picture just so you see that this is literally a cut of the vertices what are the edges crossing the cut so if we see the original graph we see u T we see u V and then we also see s V so the the capacity the max-flow that could be pushed across the cuts is going to be 3 plus 2 plus 1 which is going to be 6 so that is the capacity of a cut we're interested in the smallest capacity cut the smallest capacity cut will dictate the maximum flow that we can achieve in the flow Network so this is actually what we were doing before remember when I said the amount of capacity coming out of the start in this case seven gives us an upper bound on the flow we can create but is that is it the tightest upper bound what the min flow max cut theorem wants to do is it wants you to get that upper bound as tight as possible because if we can get that upper bound to the min cut then we know the maximum flow we can achieve without even doing anything as long as we can find cuts and find the min cut so what is the min cut in this case so if we look at this what is the minimum cut so if we take the cut here we see that there's a capacity of seven cross and get so we'll we'll take note of that if we take the cut here and I'm sorry this is an ST cut so s has to be an A and T has to be in this is called an ST cut so Esty Esty cut so s has to be in one partition T has to be and the other and s is going to be an 8 E is going to be in B what is the capacity crossing this we see there's an edge 3 3 2 & 1 so the capacity of this cut is 6 now we bested 7 we best at 7 now the new upper bound on the flow that we can push is 6 and next let's take another cut so we're going to take that so this is also an SD cut so what who is crossing the cut we see four and work only counting edges going out of the cut going outwards we have 4 & 3 so 7 this does not improve our upper bound so let's keep taking cuts so now what it what are the edges crossing this cut we see that there's two edges that sum up to four and they be our new upper bound our new upper bound is 4 and what we actually just found is the cut that is minimum the whole thing that we were saying max-flow min-cut what that actually means is the capacity of the minimum cut which is 4 is going to be the maximum flow if we do the ford-fulkerson algorithm the maximum flow we can achieve given these capacities so the max flow is also 4 so that's exactly what max-flow min-cut is saying the max flow is equivalent to the minimum cut which is the minimum capacity cut where we look at the edges crossing the cut in the forward direction there's a lot going behind the scenes as to saying why this is true but we're not going to get into that the text textbooks can do 10 times more justice and I could ever do in a video but I just wanted to explain the intuition behind this and now that you understand this you have a lot better pre context to go and read about this so this is max-flow min-cut flow networks and the ford-fulkerson algorithm

Channel: Back To Back SWE

Views: 148,503

Keywords: ford fulkerson, flow network, flow networks, graphs, max flow, min cut, max flow min cut, Ford-Fulkerson, network flow algorithms, directed graphs, directed graph

Id: oHy3ddI9X3o

Length: 21min 56sec (1316 seconds)

Published: Sun Oct 27 2019