Tip:
Highlight text to annotate it
X
Alright. So now that we've completed our warm up
by showing that at the very least, Prim's algorithm outputs a spanning tree. Let's
move on and actually show it outputs a minimum cost spanning tree.
And to prove this theorem, we're going to have to tackle head-on the kind of crisis
which you always face when designing a greedy algorithm.
So in a greedy algorithm, you're making an irrevocable decision,
like in Prim's algorithm, we're including an edge in our tree and never revisiting
it later. And, how can you be sure that you're not
making a mistake? How can you have a guarantee that the
decision you're making seemingly myopically right now is actually a good
decision won't come back to bite you later?
So it turns out for minimum spanning trees, there is a beautiful condition
which tells you when you're guaranteed to not regret including an edge into a
spanning tree, but guarantees when an edge has to belong
to the minimum spanning tree. So that's called the cut property,
it's the subject of the next slide. So this is a cool enough property that
we're going to bestow it not just with all caps but even with a box.
Now, that's a pretty good property. So what does it states?
Well, consider an edge of a graph, an edge that we are wondering if it's safe
to include it in the tree so far. So here is this sufficient condition
guaranteeing that you won't regret including this edge in the tree so far.
The condition is stated in terms of the cut.
So suppose you can find a cut, A, B with the property that amongst all edges in
the graph G, that happened across this cut, the edge E is the cheapest edge
crossing this cut. Okay? So not only should edge E cross
this cut, A, B, but it should cheapest such edge.
If this condition is met, then we definitely want them include the edge E
in our solution. Indeed, the edge E has to be a member of
any minimum spanning tree of the graph. So in this video, we're going to assume
that the cut property is true. It is by no means obvious.
It definitely requires a proof. I'll give you the proof in a separate
video. It's not,
it's a little bit tricky. It's based on a subtle exchange argument.
For this video, we're going to assume that it's true, however, and we just want
to be quiet, so that we want to figure out what it's good for.
Now, I will soon show you that it actually implies correctness of Prim's
algorithm. But just to get a feel for it, let's look
at a much simpler graph. Let's just look at a four cycle.
Four nodes, four edges with edge costs 1, 2, 3, and 4.
So let's look at, let's look at a few cuts.
So, let's look at the cut. We're on one side of the cut,
I put the upper right vertex, and on the other side of the cut, I put
the other three vertices. So there are two edges crossing this cut,
the edge that has cost 1, the edge that has cost 2.
So the edge with cost 1 is the cheapest edge crossing this cut, so by the cut
property, the edge of cost 1 has to be in the MST.
Okay. So we looked at one cut and both the cut
let's look another cut. Let's look at a cut where on one side, we
just put the bottom right vertex, and on the other side, we put all Now
this cut has two edges crossing it the edges that have cost 2 and cost 3.
The edge of cost 2 is the cheapest edge crossing this cut.
So by the cut property, it has to be in the MST.
So that's cool. So we know the two has got to be there.
Now let me point out something interesting that's happened,
which is that, it is not the case that this edge of cost 2 is the cheapest
crossing, every single cut that it crosses. Remember when we looked at cut
number 1, this edge of cost 2 was actually the most expensive edge crossing
that cut. But, we found a different cut that is the cheapest crossing and that's
enough to justify the cut property. So in other words,
all that's important for the cut property,
I just got to find you one cut for which an edge is the cheapest, that's enough to
conclude its presence in the MST. So similarly, we can look at a third cut
just consisting of the bottom left vertext and the other three vertices.
And it's the same story, there are two edges crossing this cut, the edge of cost
3, the edge of cost 4. The edge of cost 3 is the cheapest edge
crossing this cut, so we know it's got to be in the MST.
And again, when we look at cut number 2, it didn't tell us whether or not the edge
of cost 3 is in the MST, but when we looked at cut number 3, that was enough
to conclude that the edge of cost 3 has to be in the MST. So there we go.
So we could use the cut property that construct an entire MST.
On the other hand, there's no way to use the cut property to try to justify the
edge of cost 4. Any cut that you pick for which the edge
of cost 4 crosses, there will be some other cheaper edge crossing it.
So you can never use the cut property as one would hope to justify the inclusion
of the edge of cost 4 and you'd better not be able to, because 4 is not in the
MST. Now a quick side note, some of you might
be wondering when I wrote in the conclusion of the cut property,
I said the MST of G, so that would seem to indicate that the minimum spanning
tree is unique. So that deserves a quick comment.
so first of all, if the edge costs are not distinct, if you have ties between
edges, then you can certainly have multiple different minimum spanning trees
and you have to state the cut property a little bit differently.
But again, in the lectures we are just going to assume distinct edge costs, so
that's not a problem. And in fact, something that will be a
consequence of the next slide, we'll notice that the minimum spanning tree is
unique with distinct edge cost. It's not obvious, but we'll prove it
shortly. All right.
So what I want to do to finish up this video is I want to assume that the cut
property is true. And then, from that, I want to derive, I
want to argue that Prim's algorithm is correct,
always outputs an MST. The proof of the cut property is
non-trivial and deserves its own video, which you can see separately.
All right. So given the tools that we've developed, this argument is actually
going to be quite short. So let's assume that the cut property is a true statement
and let's begin by building on the previous video.
The previous video argued that Prim's algorithm outputs a spanning tree, didn't
argue it was a minimum one, but it argued it's a spanning tree, it spans all the
vertices and has no cycles. Let's call the output of Prim's algorithm
at the end of algorithm T star. Now,
stare at the cut property, stare at the pseudocode of Prim's
algorithm. What happens in each iteration of Prim's
algorithm? Well, we have our set capital X, that's
what we spanned so far. There's the rest of this stuff, V - X, so
that's a cut X, V - X. What does Prim choose to include next?
Well, in brute-force searches through the edges, the cross is cut and it adds the
cheapest one of them. Well, that is right in the wheelhouse of
the cut property. What does the cut property says? It says
cheapest edges crossing cuts have to be in the MST.
So they just fit together beautifully. Prim's algorithm explicitly picks an edge
at each iteration which satisfies the hypothesis of the cut property and
therefore has to be in the MST. So remember, the conclusion of the cut
property says edges so justified must belong to the MST. So if everything in T
star is justified by the cut property, then everything in T star is in the MST
so T star is a subset of the MST. But T star, of course, as we have argued,
is already a spanning tree in it of itself.
And, if you add more edges to T star, it's no longer going to be a spanning
tree, because you are going to pick up cycles, right? If you ever have something
that is connected, there is a path from each pair of vertices, and you add a new
edge, you are going to close a path, you're going to get a loop.
Okay? So T star is already a spanning tree, and
you can't have anything bigger and still be a spanning tree.
So therefore, this has to be the minimum spanning tree,
there cannot be anything else. So for this reason, T star must in fact
be the minimum cost spanning tree of the graph.
Since the input graph was arbitrary, assuming only it was connected, this
completes, assuming the cut property, the proof of correctness of Prim's minimum
spanning tree algortihm.