Here are the rules for Project 5.
Project 5 addresses the problem of finding all the spanning trees of a given graph. For a graph, G = (nV,E), a spanning tree will have nV-1 edges. Because of this,the approach is to recursively find all subsets of nV-1 edges from E. The posTree routine of Exercise 18 did this, but his approach can be improved by pruning. Specifically, add an 1-by-nV array of "colors", one for each vertex. Then as we add edges to the forest we check the edge for four cases.
Depending on the case, we adjust the colors appropriately and recurse. In the case of a Cycle, we do nothing.
- New Tree: the color of both vertices is zero.
- Growing Tree: the color of one of the vertices is zero.
- Grafting Two Trees: the color of each vertex is different and nonzero.
- Cycle: the color of both vertices is the same and nonzero.
Your recursive routine, spanTree.m, should be defined as follows:
function count = spanTree(nV, E, forest, colors, count, printFlag)Your driver program, Proj5.m should contain the usual comments documenting who you are and what you did, and it should contain the following lines.
nV = 6
E = [1 1 1 2 4 4 5; 2 3 6 3 5 6 6]
PlotG(nV, E)
colors = zeros(1,nV)
count = spanTree(nV, E, [], colors, 0, 1)Turn in a printout of Proj5.m, spanTree.m, the plots of the spanning trees, and a print out of the command window.
Professor: Daniel D. Warner, Mathematical Sciences, Clemson University
Send questions and comments to: warner@math.clemson.edu
Last Updated: September 2, 1996