0:02

To get started, we're going to look at a general scheme for solving max-flow

min-cut problems, known as the Ford-Fulkerson algorithm,

Dates back to the 1950s. And the idea is to start with no flow

anywhere. So, we initialize all edges to have

capacity zero. And then find any path from s to t, so

that you can increase the flow along that path.

Now, the simplest case is when the edges all go in the same direction from source

to target. We'll look at the other case in a minute.

In that case, so there is a path, and this is the general algorithm that works for

any path and if there's a path from s to t, go ahead and find it.

And if there's capacity left in each one of the edges, if none of them were full,

then what we want to do is augment the flow along that path.

So we put as much flow as we can through that path.

In this case, we can put ten units of flow through each path.

Through each edge, there's room to put ten, and two of the edges fill up in that

case but we've increased the flow in the network by ten in that case.

And the algorithm is just, continuing that way, finding a path.

So here's another path. And this one also the edges all flow from

source to target. And in this case again, we can add ten

more units a flow cuz the last edge only has capacity ten.

So load up those edges with that flow, and now, we've got twenty units a flow in the

network. Notice, when we augment along in edge,

we're preserving the vertex equilibrium, local equilibrium at a vertex property.

We're putting some flow in and taking the same amount of flow out.

So, here's another augmenting path. Now, this one has what's called a backward

edge. So notice that if, the path going from s

to t goes backwards along that edge, And the idea is, that you can augment flow

through the whole network by removing flow in that path.

That is, if we add five units of flow from s to this vertex, and five units of flow

from s to this vertex, then what we can do is remove five units of flow along this

edge. That's to preserve the local equilibrium.

Essentially, that five units of flow gets transferred right through.

After we remove five units and we add five here.

That's five coming in, There's still ten going out.

And then for the forward edges, we add the flow.

That is, we can augment the flow along an augmenting path, by adding flow to forward

edges and subtracting flow from backward edges.

The maximum amount of flow that we can push through is the remaining capacity in

forward edges and the amount of flow in backward edges.

You can't remove more flow than is there. In this case, we can augment the flow in

the network by five. That, fills up the first edge.

And so now we've got 25 units of flow in the network.

And again, the idea of removing flow from a backward edge is very simple.

It's just a way to ensure that the local equilibrium conditions always remains

satisfied as we're moving along the path. In this case there's one more augmenting

path. Okay. And that's, forward, forward,

forward, forward, backwards along that one again and then forward, forward.

So, and then what's the maximum amount that we can push through in this case,

this one has got five in it and it's got a capacity of eight so we can put three more

units of flow through this network. And we get a now we have 28 units of flow

going through the network. And the algorithm terminates when there's

no way to find an augmenting path from s to t.

And what's that mean? That means that every augmenting path,

Every path from s to t contains either a full forward edge or an empty backwards

edge. We can't put more flow through a forward

edge and we can't remove flow from an empty backward edge.

So when there's no more augmenting paths, the algorithm terminates.

And so that's the algorithm. We start with no flow.

As long as there is an augmenting path, We, we find that path and look through the

path to find the amount, the, amount capacit left in the most full forward edge

and the amount of flow left in the most empty back edge.

And we increase the flow in the path by that amount.

And if we can't find an augmenting path, then we're done.

Now there's a few questions about this. So that solves the maximum flow problem.

We have to look at how to compute and min-cut.

We have to figure out a way to find an augmenting path.

That's not to hard. That's similar to many other graph

processing problems that we have already solved.

And we have to, ensure that or at least show that it always computes a max-flow.