We invite you to a fascinating journey into Graph Theory — an area which connects the elegance of painting and the rigor of mathematics; is simple, but not unsophisticated. Graph Theory gives us, both an easy way to pictorially represent many major mathematical results, and insights into the deep theories behind them. In this course, among other intriguing applications, we will see how GPS systems find shortest routes, how engineers design integrated circuits, how biologists assemble genomes, why a political map can always be colored using a few colors. We will study Ramsey Theory which proves that in a large system, complete disorder is impossible! By the end of the course, we will implement an algorithm which finds an optimal assignment of students to schools. This algorithm, developed by David Gale and Lloyd S. Shapley, was later recognized by the conferral of Nobel Prize in Economics. As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students.
Ford and Fulkerson: Proof
Loading...
来自 University of California San Diego 的课程
Introduction to Graph Theory
120 个评分
University of California San Diego
120 个评分
课程 3（共 5 门，Specialization Introduction to Discrete Mathematics for Computer Science）
从本节课中
Flows and Matchings
This week we'll develop an algorithm that finds the maximum amount of water which can be routed in a given water supply network. This algorithm is also used in practice for optimization of road traffic and airline scheduling. We'll see how flows in networks are related to matchings in bipartite graphs. We'll then develop an algorithm which finds stable matchings in bipartite graphs. This algorithm solves the problem of matching students with schools, doctors with hospitals, and organ donors with patients. By the end of this week, we'll implement an algorithm which won the Nobel Prize in Economics!
与讲师见面
Alexander S. KulikovVisiting Professor
Department of Computer Science and Engineering
Now we have the statement of the theorem, so what else can we do?
We should provide the proof.
So here are the proof.
And to provide the proof we start with understand our theorem in some
special case.
It's generally a good idea to give a theorem before proving it you should look
at what the theorem really states and
understand this better you should consider this case, this case, that case and so on.
But in our it's not only an example but also a tool for the general case.
So it's often also happens to you after you prove some special case you can reduce
the general cases as a special one.
Anyway what is a special case?
It's a case where there is no flow, it is not possible to send any oil
from source to destination, no positive flow.
And the theorem for maximum flow is zero then and
the theorem says that the minimal cut should be zero so there should be cut
when there is no outgoing edges of positive capacity.
So if there is no flow, there should be a cut,
which make the flow impossible.
Can you say why it happens?
It's actually not difficult.
If you think, you will guess this.
Here is the statement again.
And now we need to explain this.
To explain this we introduce the node as a notion of reachable node.
So by definition, the source node A is reachable,
and every node which can be reached from
a reachable node by an edge of positive capacity is reachable.
So, we just somehow look where the oil can connect the pit arrive.
Just the independent of quantity.
Just when there is a chance to send some oil.
And technically, you can say that we have considered
directed graph made of edges of positive capacity and
you look what vertices are reachable from A in this graph.
And by assumption, our B is not reachable.
There is no path from A to B, which goes through edges of positive capacity.
And y, then there is a cut.
So if B's reachable, let me say it in another position.
If B's reachable, then there is no zero flow.
Let's look at this path from A to B with edges of positive capacity.
Technically, it can happen that this path is not simple path.
It goes twice to some vertex or even through some edge.
But of course, you can delete all the cycles and so
you get a path without when you never come to the same vertex.
And then you can send if the capacity is a positive integer you
can send at least one unit of oil along this path.
So if the vertex B is reachable then there exists a non-zero flow and
an integer case is one unit flow is possible at least.
But what if B is unreachable?
The other case.
Then there is the zero cut.
And it's easy, what is this cut?
Do you see it?
Of course it is just made of unreachable vertices.
By definition, there is no edge going of positive capacity
going from reachable vertex to a non-reachable.
So just make a section, we know that this capacity zero and
A's inside and B's outside, so this is just the cut we look for.
So our special case is now completely proven.
So the cut, let me repeat the cut, is the set of reachable nodes from A and
reachable means reachable on the graph of positive capacities.
So the special case is considered, now we want to go to the general case.
And the proof idea is very simple, in one sentence we increase
the flow until we will find a bump into an obstacle and this obstacle is minimal cut.
But while we should of course explain what we do.
So our special case is a good start, either we bump into this zero
cut immediately or we can increase the flow and
as we have discussed there is one flow of size one.
So it's a good start, but
maybe it's not optimal of course, and we should increase it further.
So this is our special case.
What special case says, and then we repeat this procedure somehow and
each time we increase the flow by 1 until we bump into some matching cut.
Of course, as we don't know why we will bump into some matching cut.
And we need to explain what happened.
And this explanations in just the reduction to our special case and
the tool of this reduction is what called residual network.
A network of reserves, per se.
And let me explain, I prepared some picture for that.
What is the reserve?
So imagine we have an edge somewhere in the graph is just
a small edge in a big graph.
And imagine that its capacity and this is flow.
So you see that this edge is not fully used.
We can still send some oil here, and maximal oil we can send is two.
We can send more flow.
But also, so to say, we can decrease the flow by ten here.
Why ten?
Because we have now plus four and
we can have six, we can stop this four and
use this six in other direction.
Now we assume that this edge is symmetric.
It's plus minus six.
It's not clear from this picture so the edge is symmetric.
It's six in any direction, now we can use it in four in one direction and
then we can switch direction and
make six the difference between plus four and minus six is ten.
So this is this residual network.
It has capacity two in this direction and capacity ten in the other direction.
Actually, it's not so unreal.
There are long stories when there is some guest sending from A to B,
and then somebody want to send the guest from B to A, the other company.
And the simplest thing is to just decrease the flow and
use the guest where it's not sending it.
But there are a lot of legal difficulties with that.
But in our mathematical model, there are no legal problems.
And so we have a reserve residual edges of 2 and 10.
And for the general case I prepared the slide.
This exact situation we had.
We had the flow 8, and so
here was 4 goes here and 4 goes here and
capacities are 6, 4, 4, 6, 1.
And we just compute the residual network, we can send two more or
we can send them here or in this here we can send anything, but
in the back direction we can send even 8, and also here things are symmetric.
And here it's not used so we can send one in any direction we want.
And now, what is the meaning of this residual network?
And there are three things, two things sorry.
So, the first, what is the flow in the residual network?
A flow is just increased compared to the current flow.
So we have an original network and there is the sum current flow and
we look how much this current flow can increase or decrease.
What are the changes in the current flow?
And the bounds for these changes are shown in the residual network.
So if there is a path in the residual network from A to B this means that we can
increase the flow in our original network by the capacity of this part.
This is about flows and another thing is about cuts.
So if we have some zero cut.
Here we don't have a zero cut but in our second example we would.
If we have a zero cut in the residual network, it means that all the edges that
go across this cut in the right direction are fully used,
because they have zero capacities in the residual network,
which means that they are fully used in the original network.
So this is a full cut, and so now we see that we consider the residual network.
There are two cases, either there is a zero cut and then we have a cut.
We bump into some cut in the original problem.
Or there is a part in the residual network and
we can increase our flow along this part by one.
So we increase our flow by one, and that's what we want.
So let me repeat the story, the pieces together.
So that's kind of algorithm, so we start with a zero flow and
then we repeat the following procedure.
First, given a current flow we compute the residual network.
First time it will be the third residual network.
And then we apply our result about specialties.
Either we find a path which can improve flow,
which is called the augmenting path, or we find a zero residual cut.
And in this case, the cut means that in the original network
our flow bumped into a minimal cut and maximum flow are the same.
And then we stop.
And after that we have maximal flow into minimal cut that met each other.
So this is the algorithm.
You should think about this.
It's so simple that there is not clear where is the trick.
But really there is nothing counter intuitive.
We do whatever we should do and we are done.
It's very easy if you know how to prove it.
Only thing we should say that's also obvious for
integer capacities, the termination.
So if capacities are integer then each time we increase the flow at least by one.
We know that in this residual network we have a path and
we can assume that it doesn't come back to the same vertex, so
we can just send at least one unit of oil along this part.
So we increase the flow at least by one, and so
we cannot do it infinitely long, we will finally stop.
And also, as this algorithm shows, that for
integer capacity network our maximal flow is also integer,
which is important for some application.
