Welcome to a lesson on spanning trees.
For a quick review,
a tree is a connected graph containing no cycles,
meaning the graph is acyclic.
A cycle is a path that starts and stops at the same vertex.
One of the advantage of trees
is that they give us a few simple ways
to travel through the vertices.
If a connected graph is not a tree,
then we can still use these traversal algorithms
if we identify a subgraph that is a tree.
First, we should consider if this even makes sense.
Given any connected graph G,
will there always be a subgraph that is a tree?
Well, this is straightforward.
We could just use a single vertex of G.
Recall that a single vertex is considered a tree.
However, if we want to use this subgraph
to tell us how to visit all vertices,
then we want our subgraph to include all of the vertices.
We call such a tree a spanning tree.
It turns out that every connected graph has one,
and usually many.
Given a connected graph G,
a spanning tree of G is a subgraph of G
which is a tree and includes all the vertices of G.
Every connected graph has a spanning tree,
and there are two common methods
for determining a spanning tree given a connected graph.
One is called the Cutting Down Method,
which is a method we will use.
There's also a method called the Building-Up Method.
For the Cutting Down Method,
the first step is to start
by choosing any cycle in the graph G.
Step two, remove one of the edges in the cycle.
Step three, repeat this process
until there are no cycles left
For the Building-Up method,
the first step is the select edges of graph G one at a time,
such that no cycles are created.
Step two, repeat this process
until all the vertices are included.
We will now find two different spanning trees
for the given graph.
And again, we will use the Cutting Down Method.
So we begin by identifying a cycle in the graph.
For example, here on the left,
there's a cycle among these three vertices.
Let's go ahead and remove this edge.
Next, we have a cycle among these three vertices.
Let's remove this edge.
We have a cycle among these three vertices.
Let's remove this edge.
We have a cycle here at the top among these three vertices.
Let's remove this edge.
We have a cycle here on the right
among these three vertices.
Let's remove this edge.
Now, we're not quite done yet.
Notice there's still a cycle among these five vertices here.
Let's go ahead and remove this edge here,
and now we're done.
One possible spanning tree for the visual graph
is shown here in the right.
You notice how we removed
this edge, this edge, this edge,
this edge, this edge, and this edge
to form the spanning tree.
This is one possible spanning tree,
because the graph contains all the original vertices,
and there are no cycles in the graph.
And now let's work on determining a different spanning tree
for the same original graph.
Notice, from the first spanning tree,
we didn't remove this bottom edge here.
Let's go ahead and start
by removing this edge in the original graph.
And now from here, whatever we do,
we are going to have a different spanning tree.
Starting back on the left,
let's go ahead and remove this edge
to remove the cycle among these three vertices.
Let's remove this edge here
to break the cycle among these three vertices,
and let's remove this top edge
so we no longer have a cycle among these three vertices.
Let's remove this edge here
so we no longer have a cycle among these three vertices.
But we still have a cycle among these four vertices here.
Let's go ahead and remove this edge here.
And now I think we have our second spanning tree,
which looks like this.
Again, we removed this bottom edge.
We removed this edge, this edge,
this edge, this edge, and this edge,
which we can see does give us the original graph.
And once these edges are removed,
all the original vertices are still in the graph,
but now the graph doesn't have any cycles or is acyclic,
and therefore this is another possible spanning tree.
I hope you found this helpful.