Hello everybody, welcome back to our network flows unit. Today we're going to be talking about some tools that are actually very useful. A tool called the Residual Network for coming up with new flows, or adding a little bit of flow to an existing flow. So remember last time we formally defined these things. We defined what a network was, and we defined the flow on this network was, and then defined what the maxflow problem, which is the one we're working towards solving. There's a very basic technique to solving maxflow, that is basically what we are going to be working towards for the next bunch of lectures. And the idea is to build up your flow a little bit at a time, and this is really what we did in the original example in the first lecture, where we routed a bunch of cars along one road, and then routed some more cars along another road and so on and so forth, and built up the final flow as the sum of a bunch of little flows. So how do we this in practice? Well suppose that we have the following network. Here, all the edges have capacities 1, for simplicity, and what we can do is, we can just add flows of those together a little bit at a time. We can know, hey, we can send the unit of flow along this top path, and if we just have a unit of flow on each of these edges, everything balances. But after we do that, we can send another unit of flow along the bottom path, and then another unit of flow along the middle. And once we've done this, we now have a maximum flow, but we built it up in nice convenient little pieces. Okay, so let's consider another example, this one's actually a little bit simpler. We have our network here, the maximum flow is 2, as we've shown here, but we're going to try and add flow increment. So let's start by adding flow along this path, it's a perfectly valid path, we can route a unit of flow through it. And now we want to try to add our second unit of flow and there's a bit of a problem. We can't readily add a second unit if we've already used up these piece edges, the remaining edges just don't connect to each other we can't actually get the flow to work. Now it turns out this away around this, which of course there is since the maximum flow is 2, and it involves with the rounding flow along with this blue path, which is a little bit weird since we can not actually do that. We can't actually send flow down along the middle edge since there was not an edge there, but if you think about it in the right way, you can think of sending flow down this middle edge as cancelling out the flow that we currently send in the up direction. If the flow going up and the flow going down are thought to cancel each other, then once we add these two flows together, we just get this flow, which is perfectly valid, because there's no flow running along the middle edge. And so,the moral of the story is that if you want to be able to appropriately add your little bit of flow, sometimes it's not enough to just add flow along new edges but sometimes you also have to let your flow cancel flow along existing edges. So given a network G and a flow f what we're going to do is construct what's called the residual network, g sub f, and this is a new network that represents the places where flow can be added to f. But this includes not just edges where there's more room for extra flow to go along that edge, but also places where we could cancel out existing flows. So to define this formally for each edge e of our graph our residual graph, our residual network is going to have edges, well it's going to have an edge along e. And the capacity is going to be the capacity of the edge, the original capacity of the edge, minus the flow along that edge. And the point is this is the amount of remaining capacity that we have of course, if the flow is equal to the capacity we can ignore this edge because it would have no capacity. We also need to have an edge opposite e with capacity equal to the flow along e, because this will represent the amount of flow that we can cancel going in the other direction. So for example, up top we have the following net, we have a network, and it has a flow assigned to it, there are various units of flow assigned to various edges. Down below will give us the residual network, so if you look at the edge on the left, for example, well we used up all five units of its flow. So what does this mean? Well, we've got no edge left pointing down, because there's no extra flow that we can push in that direction. However, we do have a new edge pointing up with five units of flow, saying there are five units of flow going the other way that we might cancel out later. If you look at the top edge we use five out of seven total units of flow, so there's two units of flow left. So there's this one edge up top with two units of flow, and then there's this additional edge going the opposite direction representing the five units of flow that can be still be cancelled. And so we do that also for all the other edges of the graph, and this gives us the residual network. So if we look at what this does to our previous example, we have this graph, we route flow like this. Now we can't add to it directly, but if you look at the residual network, we're actually going to have an edge going back in the opposite direction from each of these. And in this residual graph there is actually a path that supports user flow, it involves this middle edge that says that we're cancelling out flow along the middle. Okay, so given a network g and a flow f, any flow g on the residual graph it turns out can be added to f to get a new flow on the original graph. So, the point is that if you have flow along this edge in the same direction that you had in the original graph, that's saying, you should add that much flow along that edge. However, if you got flow sort of in one of these opposite direction pointing edges, that's saying that that much stuff should be cancelled From the flow that you had before along that edge. So just to make it clear, let's look at this problem. So we have a network with a flow on it, f this upper left corner. Down below it we show what the residual network is corresponding to that flow. Now in the upper right we have a flow, little g, for the residual network. And the question is if we want to compute the sum of the flows, f plus g, what is the flow of f plus g along this highlighted edge from source to. Well, what do we get? The original flow along that edge was two, we need to add the flow of g along that same edge. That's four extra units of flow and we need to subtract off the flow in the canceling direction, so that's plus four minus two, That's a total of four units of flow from S to T in the residual. And you can compute the other edges and yes, f + g does give you a valid flow for the original map work. In fact, the theorem is as follows, if you have a graph G and a flow f and then have any flow you like g on the residual map work, a few things happen. Firstly, f + g is always a flow on the original network which is nice. If you want to look at the size of the flow, the size of f + g is just the size of f plus the size of g. And finally and importantly, any flow on the original network you can always get by finding some appropriate residual flow like adding it to f. Now the proof of this is actually not that hard, if you want to look at conservation of flow, conservation of flow of f, and conservation of flow of g, if you combine them,imply that you have conservation of flow on f + g. Next if you want to look at the total flow f + g sends through an edge, well the flow it sends through edge E is equal to at most the flow of f along that edge plus the flow of g along that edge, which is at most the flow of f plus the capacity of that edge in the residual. But that capacity is just the original capacity minus the flow that you sent from f and so that's just the capacity of our original network. On the other hand, you can't end up with negative flow along an edge because g isn't allowed to cancel more flow along that edge than you had originally. And so, putting this together, f + g has to be a flow. Next, if you look at the flow of f plus g out of a source, this can be shown to be the flow of f out of that source plus the flow of g out of that source. So combining this, the sum of the size, the size of the sum of the flows is the sum of the sizes. And finally if you're given any flow h for our original network, it's not hard to construct a g that's somehow h- f, that's a flow on the residual graph. And so you can then write as h as f + g for some appropriate flow on the residual graph. So, in summary, flows on the residual network, so it exactly correspond to ways to add flow to our original f. And this is very useful because our big picture idea for our algorithm is going to be start with some flow, and then add little bits of flow, and the residual graph will tell us exactly how we can add little bits of flow. So that is all we have for this lecture, come back next time and we will talk a little bit about how to show that we actually have the best flow when we do.