0:03

Today we're gonna finish off our discussion of graph processing by looking

at Max Flow algorithms. This is another general problem solving

model for which we have efficient algorithms, so where at the difference

between having a good algorithm and not having one makes a difference between

being able to solve all kinds of practical problems and not being able to address

them at all. As an introduction we'll take a look at

what the problem is and some of it's implications.

So first we'll start with what's called the mincut problem.

So this is a. takes as input a Edge Weighted Digraph and now we are going to

assume that the edge weights are positive, and we referred to the weight as a

capacity and you will see why in just a minute.

And also we specify a source and a target vertex.

This is not an absolute requirement but it will simplify our discussion for the

lecture. So we have an edge weighted digraph where

the source and target vertex and every edge has a positive capacity.

Now a cut, an ST cut, S and T are specified remember? Is the partition of

the vertices into two disjoint sets, Where s is one set and t is in the other.

And we'll indicate a cut as we've done before by coloring the vertices in one

set. So in this case, the cut consists of s in

one set, and all the other vertices in the other.

So s is in, one set and t is in the other, that's an st cut.

Now given a cut. We talk about the capacity of the cut.

And that's gonna be the sum of the capacity of the edges that go from the set

containing s to the set containing b If you have edge going the other way we don't

count it. So in this case, the, this cut with the

vertex containing just s in one set has capacity 30 ten + five +fifteen.

Here's another cut this one contains three vertices,

S and two at the bottom there. Again it's an ST cut, cause s is colored t

is not. And then we can look at the capacity of

that cut. Again, we count the vertic, the edges that

go from to the cut containing s to the cup containing b, B.

In this case, is ten + eight + sixteen That's the edges going out is 34.

That's the capacity. We don't count the edges that go in from

the sec containing t to the sec containing s Capacity of the cut is the sum of the

capacities of the edges going out. Here's the third example, and this one's

got capacity 28. Now the three cuts that we've seen you

notice have different capacities: 30, 34, 28.

So the mincut problem, clearly, is to find the minimum capacity cut.

Find a way to divide the vertices into two sets, one containing s and the other

containing t with the property that the capacity of the cut is minimized.

That's the mincut problem. And this an important practical problem

with all kinds of applications. Just for fun we take an application from

the 1950's. This is around time these sorts of

problems were first articulated. So this is, has to do with the cold war

and these are rail networks that connects the Soviet Union with countries in Eastern

Europe. This map actually wasn't declassified

until 1999. But it shows a graph with the vertices,

directed graph with vertices corresponding to cities and edges corresponding to rail

lines. And if you look closely, you can see that,

Each of the edges is labeled with a capacity.

The goal. So the goal of the free world say if there

was gonna be a real war was to find a way to cut the Soviet Union from Eastern

Europe. And they wanna do that.

You can assume maybe the cost of cutting a rail line is proportional to its capacity.

So they wanna find the cheapest way to cut off supplies.

From Soviet Union, Eastern Europe. That's an example of a min cut

application. We'll look at some other applications

later on. Well, look at a future, well maybe this is

a cut for today's world. So now you have a huge graph, maybe a

social network. And maybe there's a government and power

in some area of the world, and the goal of that government would be to cut off the

communication to some set of people. And again, they want to do that in the

cheapest way possible. Find the minimum way to cut off

communication. And certainly, people are writing programs

to process graphs like this with such goals in mind nowadays.

These are huge, huge graphs and certainly are going to need efficient algorithms.

In the 1950s, the graphs were pretty huge by 1950s standards.

And it wanted efficient algorithms then too, for sure, 'cause computers were

slower. Alright, that's one problem.

So let's talk about a different problem, called the max-flow problem.

And it's the same setup inputs and edge weighted digraphs, source for text s, and

a target for text t, every edge has a positive capacity.

And now what we're gonna talk about is what's called a flow.

It's a assignment of values to the edges. So, we have the capacities, and we're

gonna assign another integer to each edge, called its flow.

And then flow has to satisfy two properties.

The first one is that the flows have to be positive and they can't be greater than

the capacity. You can think of the, edges again as a

rail line containing some commodity or a pipe containing some fluid.

So the flow is how much stuff can you put through that edge?

You can more than zero but you can't put more than capacity.

The other thing about a flow is that there has to be local equilibrium at the

vertices. And again that's a natural constraint to

think about stuff flowing in on rail lines to a city and you want, you want to keep

things going the local elibrium constrains says that the stuff coming in has to equal

the stuff going out at every vertex except for the source everything leaves from the

source. And the target, everything goes to the

target. And those have the source has no inflow

and the target has no outflow. So what you want is the inflow at a

vertex, say, in this example inflow at v, there's five coming in on this edge and

five coming in on that edge. So that's a total of ten coming in and there has to be

just ten going out. So that's, happens on this one edge.

And that has to be satisfied at every vertex.

So this flow's got five coming in there and five going out.

Ten going in there and five going out each way and so forth.

Every vertex except S and T. And we can even make it true for S and T

by drawing an edge from T all the way back to S.

So that's the max flow problem, well, the, that's the definition of a flow, and of

course the max flow problem is to assign a value to the flow.

Well that's how much stuff you can get to the source.

To the target. Or equivalently, how much stuff can you

push out of the source. And so the value is how much can you get

into the target. There's lots of different ways to assign

flows to the network to satisfy the capacity equilibri-, equilibrium

constraint. Which one maximizes the flow, that's the

maximum ST flow problem, or the max flow problem.

So that's two different problems. The min cut problem.

How do we cut the graph efficiently, with a minimal amount of work.

And the max flow problem. What's the maximum amount of stuff that we

can get through the graph? And again, if we look at, the 1950's

graph. What the Soviet Union wanted to do was

find a way to maximize the flow of supplies to Eastern Europe.

Now that was their goal in this case, and again you can see in this whole map, this

is a assignment of a flow to this network that does maximize the flow for this

network, So they figured it out.

And nowadays in the huge graph, maybe the free world wants to do the opposite.

They want to maximize the flow of information to some specified set of

people. How do we get the most information in

there and is there another way to think of it?

And again, these are huge graphs and we want efficient algorithms.

So that's two problems both have an input weighted digraph with a specified source

and target and then cut problem is to find them in capacity cut and max flow problem

is find a maximum value flow. It's a lot of computation to do for

example in the max flow problem we have to assign a value to each edge.

So that's more work than just finding a path as we've done in other graph

processing problems. So it's more complicated and the amazing

thing about these two problems is that they're actually pretty much the same

problem. They're what we call dual.

If you solve one you're able to solve the other.

So that's an introduction to max flow