Every connected graph has a spanning tree. A spanning tree T of a graph G is a tree that is (a) a subgraph of G (i.e., that includes only edges from G) and (b) includes every vertex of G. On the right we show a connected graph and below we show its eight spanning trees. Note that the graphs are regarded as being labelled (even though we don't explicitly show the labels in the list of spanning trees). The set of labelled trees corresponds to the spanning trees of the complete graph; the set of free trees correspond to the unlabelled spanning trees of the complete graph. Both of these sets of trees may be generated by COS from the tree generation page.
The tree graph of G, denoted T(G), is the graph whose vertices are the spanning trees of G and whose edges join those spanning trees that differ by an edge exchange: one edge removed, another added. Proofs that the tree graph is Hamiltonian may be found in Cummins (Hamilton circuits in trees graphs, IEEE Trans. Circuit Theory, CT-13 (1966) 82-90) and Holzmann and Harary (On the tree graph of a matroid, SIAM J. Applied Math., 22 (1972) 187-193).
The output of COS is a Hamilton path in T(G). Below we show a tree graph of our example graph and the Hamilton path that is output by COS.
Compare with the actual output of COS shown below. The green edge is the one that just entered the tree; the one above it is the one that left. In the case of Gray Code output, aside from the initial spanning tree, only the entering and leaving edges are shown.
Edges |
Gray Code |
---|---|
1-2, 1-4, 2-3 | 1-2, 1-4, 2-3 |
1-2, 2-4, 2-3 | In: 2-4 Out: 1-4 |
1-2, 2-4, 4-3 | In: 4-3 Out: 2-3 |
1-2, 1-4, 4-3 | In: 1-4 Out: 2-4 |
1-2, 2-3, 4-3 | In: 2-3 Out: 1-4 |
1-4, 2-3, 4-3 | In: 1-4 Out: 1-2 |
1-4, 2-3, 4-2 | In: 4-2 Out: 4-3 |
1-4, 4-3, 4-2 | In: 4-3 Out: 2-3 |
The algorithm we use is due to Malcolm James Smith (Generating Spanning Trees, M.Sc. Thesis, Dept. Computer Science, University of Victoria, 1997).
Determining the number of spanning trees of a graph can be reduced to the problem of computing the determinant of a certain matrix....
this section yet to be completed!