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.