0:00

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.

Â 0:16

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.

Â 1:30

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,

Â 2:16

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.

Â 2:48

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.

Â 3:31

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.

Â 4:13

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.

Â 4:52

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.

Â 5:16

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.

Â 5:44

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.

Â 6:09

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.

Â 6:41

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.

Â 7:24

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.

Â 7:57

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.

Â 8:10

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.

Â 8:39

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.

Â 8:53

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.

Â 9:28

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.

Â