In this lecture, we are going to begin going over the minimum spanning tree.
And before we start talking about a minimum spanning tree, we just need to get an understanding of
what a spanning tree is and what the rules are for it.
So we have three rules.
The first one is we need to be connected.
The second one is no cycles, and the third one is the number of edges is equal to vertices minus one.
So number of vertices minus one.
So we'll start with something simple and we'll say that we have zero one, two and three, and we're
going from 0 to 1, 1 to 2, 2 to 3, 0 to 3 and 3 to 1.
So we see that we're definitely connected.
We're able to get to every node from any node through some form of a path or another.
But we see that rule number two is currently being broken here.
So this is currently not a spanning tree because we see that 031 is cyclic.
We can go 013 cyclic and we can make a couple of cycles out of this, but we also see that we have more
edges than we do nodes, so too many edges in this case as well.
So for us to make this a spanning tree, we can do 0 to 3 to 2 to 1.
That's a spanning tree.
We can do 0 to 1, to 2 to 3.
That is a spanning tree.
And we can also do 0 to 3 to 1 to 2.
And that is also a spanning tree.
And we can continue making more spanning trees out of this.
But I just wanted to show you some examples of what a spanning tree looks like.
So these are all
spanning.
Trees.
So if we want to start looking at a minimum spanning tree, then the sum of weights.
Oh, the.
Some of the edges.
Wait.
Should.
Be.
Minimum.
All right.
So if we take our same example from above of zero one, two and three, and now we start assigning some
weights to them, so we have 0 to 3 is to zero, or 3 to 2 is one, 0 to 2 is three, 1 to 2 is four
and 0 to 1 is five.
So if we want to create a minimum spanning tree to this, then we want to satisfy our three rules above
of it being connected with no cycles and the number of edges is equal to the number of vertices minus
one.
So for us to do this, we we can start out at vertex zero and we see that from vertex zero, we can
go to three or to one, but we see that we have an edge of weight two.
So let's take that.
And then from three we only have one path that we can go, which is one.
So we can go to number two, vertex two.
And we see that we go we can go from 2 to 0 or 2 to 1, but if we take 2 to 0, then we become, then
we create a cycle.
Therefore, there would no longer be a spanning tree.
So our only path that we can take here is going to be to one as well.
And now we have a connected graph and we are minimum because we have two plus four plus one is equal
to seven.
And every other path that we take from here to create a minimum spanning tree will be greater than seven.
So that was a pretty simple example that we could look at.
And so now we can create a slightly more complex graph where we can say zero one, two, three, four
and five, and we can have one, two, seven, two, one.
Three, six,
four, and from 4 to 2 we will go three.
And from 1 to 3 we will go five.
So we'll start at vertex zero again and we see that we can go two different directions.
We can go to either vertex five or one and we'll go with vertex five because it is has a weight of one.
From five.
We can go to four or we can go to one.
And again we'll choose four because we have the lower weight on that edge from four.
We can go to three or we can go to two.
And if we go to three, we have seven as our weight.
And if we go to two, we have three as our weight.
So we'll go to two since we have a weight of three from two.
We can go to one or we can go to three.
So we will go to one.
And from two, we can also go to three.
Where we have a weight of to.
So here the weight of our minimum spanning tree is going to be equal to nine.
And we see that we are connected entirely.
We have no cycles and we have one, two, three, four, five edges and we have one, two, three,
four, five, six vertices.
So this would be our minimum spanning tree.
So in the next lecture we will go over the implementation for a minimum spanning tree.
So if you have any questions about a minimum spanning tree, please feel free to ask me in the Q&A section.