maxflow We saw an image processing algorithm called syncarving for shortest
path. There's another one called segmentation
for maxflow. Again, if you have an image and you have one vertex per pixel you have
a huge, huge graph. And you have many explicit huge graphs and
we've talked about those types of things. But there are other things where the graph
is, is an abstraction that it gets involved in a model of the abstract graph
and the maxflow problem. Its maybe a bit surprising at first, and
we'll look at a couple examples of that to illustrate the point.
Over here is a medical example having to do with it.
That's the, the image processing one on a medical example to help identify some
important part of a medical image. So, we'll look at a, at a couple examples
to that the idea of a general problem solving model that, once we have an
efficient algorithm, then we can think about using the problem solving model.
And later on, we'll see that this, this concept of a general problem solving model
has really profound implications and we'll be looking at that later on.
So, let's just look at a, at a couple of examples.
Here's one called the bipartite matching problem.
So you have this is a bit of an idealized situation.
But it works in more messy, real life situations, too.
So, there's n jobs out there and n students apply for them.
And we'll use a small example where there's five students and five jobs.
But, of course, in the real world, this can be huge.
Now during hiring season, the students go out and apply for the jobs and they each
get a bunch of offers. So looking at it from a student's point of
view. Alice gets offers from Adobe, Amazon, and
Google. Adobe makes offers to Alice, Bob, and
Carol, and like that. So, this is an association between
students and jobs. Everybody gets several offers.
And in question is well, it would be good if everybody got a job, right?
And the question is, is there some way for everybody to get a job.
That's called the bipartite matching problem.
And it comes up in lots of forms directly related to graph processing.
Now, we could study and people do study algorithms for explicitly solving this
particular problem. But what I want to emphasize is that
actually, maxflow is a reasonable model for it.
So, we can use our efficient maxflow implementation to get it solved.
We don't have to come up with a specialized algorithm for this problem.
So, in terms of graphs, it's called the bipartite matching problem,
Given a bipartite graph, find a perfect matching.
And a bipartite graph is one where you have two sets of vertices, in this case,
one to corresponding to students and another corresponding to companies.
And you have every edge in the graph goes from one type of vertex to other, the
other type of vertex. And a matching in the graph is a set of
edges that are disjoint that disconnects two vertices but that's it.
And so, in this case, there's a perfect matching works out that if Alice takes the
Google job and Bob takes the Adobe job and Carol takes the Facebook job and like
that, then everybody gets a job. So, that's a perfect matching.
But you can also have a situation where that's not possible.
So let's look at how to formulate, How to, well, the one thing is, how do we
find the matching? And then the other thing is, is there one?
So this is easy to formulate as a matching network flow problem.
That's what this diagram shows. So, what we'll do is we'll create our
source and target vertices. We'll have one vertex for each student.
One vertex for each company in the flow network.
And we'll add a capacity one edge from s to each student.
And a capacity one edge from t to from each company to t and then it doesn't
matter what the capacity. We'll add an infinite capacity edge from
each student to each job offer. And then, we'll ask for a maximum flow in
this graph. So, you can see that the flow, every
augmenting path has to go from s to a student to a company to t and so, the flow
will give us the match and let's see how it works.
This is a, a one to one correspondence between perfect matchings and bipartite
graphs, and integer value maxflows. so, in this case, there's a flow of value five.
And that flow gives us the matching immediately.
So what the mean cut tells us if, if there's a no perfect matching, explain
why. So, here's an example that maybe could
have happened with the job offers. And when the we're algorithm terminates it
terminates with a cut we're the, a cut of the bipartite graph, which separates two,
four, and five from seven and ten. And essentially the cut tells us that
students in two, four, or five can only be matched to companies seven and ten.
You could see all the edges from two, four, five go to seven and ten, so you
have two companies and three students. So, there's no way that everybody can be
matched, somebody's gonna be left out. So that's a the students, so that they'll
be a mean cut, and the s will be the students on the s side and t will be the
companies on the s side and if it's bigger than, s is bigger than t, then I can't
have a matching. So in this case at, there's only, four
jobs and somebody is going to be left out. It's also interesting to trace through
what happens with the maxflow algorithm on bipartite graphs like this.
Essentially augmenting paths or usually forward edges makes some matching.
And then if it's possible to find a path that undoes some matching.
It, zig zags through, undoing matching and trying other ones to find a way through to
the target. But if there's no perfect matching,
there'll be a mean cut. And that one will explain why.
So, that's a problem, The bipartite matching problem that we can
model as a maxflow algorithm and just use our existing code to solve it.
Here's another one that's even further away.
It doesn't seem to have a graph at all, but it does.
It's called the baseball elimination problem.
In this is again, just to show the breadth of applicability of the maxflow model.
It's interesting at certain times of year, you get near the of the baseball season
and often you'll hear in the news, or see in the paper, or see in the web, that your
team is mathematically eliminated. Actually most of the time, they don't
really get that right because they don't do the computation that we're going to
talk about next. Sometimes, it's easy this is an example
where it's easy. So we've got four teams, they already have
this win-loss record and this is the number of games to play.
So in this case Montreal has only three games to play. so the best they could do
is win 80. Ag, but Atlanta has already got 83 wins so
there's no way Montreal is going to win. So, that's a mathematical elimination that
anyone could figure out. Usually the newspaper will get that one
right. So but sometimes it's more complicated if
you look, say, this case. So Philly has 80 wins, three games to
play. So the best they can do is 83 wins.
So that's interesting. But the thing is that Atlanta has a bunch
of games against, it's got six games against the Mets.
And either Atlanta wins one of them, which would give Atlanta 84 wins, or the Mets
win all of them, in which case, they get 84 wins.
Either way, Philadelphia is mathematically eliminated.
