What Else?

Loading...

Do curso por University of California San Diego

Introduction to Graph Theory

100 classificações

University of California San Diego

Introduction to Graph Theory

100 classificações

Curso 3 de 5 em Specialization Introduction to Discrete Mathematics for Computer Science

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.

Na lição

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!

The Framework8:17

Ford and Fulkerson: Proof11:36

Hall's theorem10:06

Conheça os instrutores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering

Now let's make some more general comments about these things.

So, I started with the importance of the initial task.

It's really a practical problem.

And so, people really care about this.

And there are better algorithms.

Our Ford-Fulkerson algorithm first is only for

integer capacities and it's not optimal and it was improved many times.

And is a significant part of the Efficient Algorithm Theory.

And having a good algorithms for maximal flow and minimal cuts.

We also have good algorithm for matchings.

And also, this is not the most difficult thing.

So, for example, we can consider the problem for

matching when there is not a bipartite graph.

We have just a graph and we want to find maximum number of edges preferably

including all the vertices but

just the maximum number of edges which do not have common vertices.

They are called matchings in a graph without parts

and can be called "matching for same sex marriage."

Again, it's just a terminology.

No claims about your life.

And also, we can consider the cases when there are several types of commodities.

For example, we have a set of railway lines and each railway line,

of course, it's not like a pipe.

You cannot send water and oil in the same pipe.

But the railway line,

you can make a combined train.

So, that is just the limit of capacity for all commodities sent.

And then, you can have several commodities and you want to send them somewhere.

Or you have not one source of oil and one destination,

but you can have several oil sources and several destinations and you need to

organize thing or you want to try to minimize the cost of this or whatever.

So, there is a lot of practical problems and they are much more complicated.

We consider only the simplest case.

But most of these problems are a special case of what is called linear programming.

It's a very important thing. We will not cover in our course but you can probably

find many sources and courses about linear programming.

And what I want to say that,

this effect that maximal solution matches the bumps into minimal obstacle,

is a general phenomenon for linear programming problems.

It's called duality. It's very important to understand that if you do linear programming.

And finally, like in a good opera,

if there was some theme in the overture,

the theme usually appears somewhere in the opera.

And so, we will start with tilings.

Let's explain why Ford-Fulkerson whole theorem is important for tilings.

So, if you forgot this already,

this is what we consider domino problem,

which we have a region in a cell paper and we want to tile some region with dominoes.

And the question whether it's possible and,

looking at the region, how to find the tiling or prove that it's impossible.

And the tool is the reduction to a matching problem in a bipartite graph, actually.

And this graph looks strange but let me tell you what are the vertices of this graph.

Left vertices are white cell and right vertices are black cells.

And edges between white cell and black cells exist when they are neighbors.

And if you draw this graph,

any matching in this graph

is a tiling and perfect matching is the full tilings, so to say.

So, any set of edges with this joint endpoints corresponds to tiling of

some part of the region and the perfect matching correspond to full tiling.

So, do you see why it happens?

Just you can think about about this yourself.

But I prepared a picture showing this.

But maybe you already understand what I'm saying.

Anyway, here are the picture.

So, here are the regions.

So, this is what you want to tile.

This don't exist for us.

And of course, in the picture,

you can tile easily.

You can put things here and things here.

So, the problem is easy but I just need small example.

But just in general,

what do you see here?

So, imagine we have a tile.

The tile has a domino, one times two.

And we can look at the style as a kind of connection between two cells.

One of them is white and other is black.

So, the possible connections, the possible tiles,

and/or the possible connection between cells

are just neighbor pairs of white and black cells.

And we can draw all of them.

So here, just looking at the region,

we create this picture where the tile could be.

And now, the only thing we need is to find the matching because if you find the matching,

if we delete some edges and get a set of pairs,

and this is just what we need because each pair makes a tile.

And we are done. And what is nice then for this case,

we don't need complicated same sex marriages.

We have a matching problem for bipartite graph and we know how to use this.

This is Ford-Fulkerson.

So, now you know how to solve any problem about tiling.

You just construct a graph.

You convert it to a network.

And then you apply Ford-Fulkerson to this network.

And either you get a flow and a matching and a tiling,

or you get a cut,

or a set of obstacle in the matching problems,

which now means that you find some set of

key white vertices for which there is not enough black neighbors.

So, if in the picture you find key black vertices and

they are organized in a way that they don't have enough black neighbors,

then it's obvious that there is no tiling.

These vertices cannot be covered at the same time.

So, this is a reduction.

It's the best standard technique for algorithm.

You reduce some problem to some other problem.

And so an algorithm which gives the solution for the second problem

can be now brought back for the first problem.

So, for a region,

you know how to find either a tiling or a proof that tiling doesn't exist.

And this is what we started with.

So, now, somehow you can be satisfied that

the initial question which we post before the course is now solved.

Of course, we chose the question this way.

But still, you should be satisfied with this.

Here's the final take home message.

This is reduction. You applied Ford-Flukerson.

It finds the tiling if it exists and defines an obstacle if there is no tiling.

But it does not draw a chain of reduction.

So, the idea of reduction is very important and you will see

these reductions in computer science.

When you prove some problem is difficult,

you show that some other problem can be reduced to it.

And if you want to show that the problem is easy,

you reduce this problem to some other problem.

So, we use the second thing.

We started with Ford-Fulkerson.

We solve that with flow problem.

We solve it and then we reduce the matching problem to Ford-Fulkerson.

And then we reduce tiling to matchings.

So, finally we solved the tiling problem. Okay.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play