Graph Theory Lessons
Lesson 43:
Spanning Trees
A spanning tree for a connected graph G is a subgraph of G that is a tree and whose vertex set is all the vertices of G. If G is a tree then it has only one spanning tree, G itself. If G is not a tree it has more than one spanning tree.
Petersen Activity:
We will first illustrate a depth first approach to getting a
spanning tree. Get the grid
Grid4, 5. Now click
Properties | Spanning Trees | Depth First Spanning Tree.
You will see the
depth first spanning tree. It looks like figure
43.1
| |
|
Click Graph | Close This Frame to get back to the main Petersen frame and now find a breadth first spanning tree by selecting Properties | Spanning Trees | Breadth First Spanning Tree. You should get a picture like figure 43.2.
| |
|
Java Web Start Activity:
The Java Web Start application below will help you to understand the
difference between a depth first and breadth first spanning tree.
Draw a connected graph in the left pane. The depth first spanning tree
will be displayed in the middle pane and the breadth first tree will
be displayed in the right pane.
- For the Herschel graph, draw a depth first and a breadth first spanning tree and then two other spanning trees.
- Find a graph on five vertices that is not a tree but such that all of its spanning trees are isomorphic.
- Which graph is isomorphic to the breadth first spanning tree of the complete graph Kn?
Answers
© C. Mawata
