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.