MthSc 360: Project 5


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.

  1. New Tree: the color of both vertices is zero.
  2. Growing Tree: the color of one of the vertices is zero.
  3. Grafting Two Trees: the color of each vertex is different and nonzero.
  4. Cycle: the color of both vertices is the same and nonzero.
Depending on the case, we adjust the colors appropriately and recurse. In the case of a Cycle, we do nothing.

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