Message Boards Message Boards

2
|
6241 Views
|
5 Replies
|
7 Total Likes
View groups...
Share
Share this post:

How to use NumberOfSpanningTrees ?

Posted 11 years ago
Hey there, 

The documentation page of this function is quite limited. I followed the instruction but following code does not output useful information:
Needs["Combinatorica`"]
NumberOfSpanningTrees[HypercubeGraph[3]]
I want to draw the spanning true of a hypercube, do you know any internal functions other than this one?  

Thanks
POSTED BY: Shenghui Yang
5 Replies

IGraph/M now includes a function to count spanning trees.

In[1]:= Needs["IGraphM`"]

During evaluation of In[1]:= IGraph/M 0.3.99.1 (May 1, 2018)

During evaluation of In[1]:= Evaluate IGDocumentation[] to get started.

In[2]:= IGSpanningTreeCount[HypercubeGraph[3]]
Out[2]= 384

To explore the topic, you might find it useful to generate some more random spanning trees and visualize them.

g = HypercubeGraph[3, VertexLabels -> Automatic]

IGRandomSpanningTree[g, 20] // 
  DeleteDuplicatesBy[AdjacencyMatrix] // 
  Map[HighlightGraph[g, #, GraphHighlightStyle -> "Thick"] &]

Mathematica graphics

While this graph has 384 distinct labelled spanning trees, only 6 of them are non-isomorphic.

IGRandomSpanningTree[HypercubeGraph[3], 100] // 
 DeleteDuplicatesBy[CanonicalGraph]

Mathematica graphics

POSTED BY: Szabolcs Horvát
Very handy!! This is definitely more flexible than what I have done manually with EdgeStyle: 
HypercubeGraph[3,
EdgeStyle -> {1 \[UndirectedEdge] 5 -> {Blue, Thick},
   6 \[UndirectedEdge] 5 -> {Blue, Thick},
   2 \[UndirectedEdge] 6 -> {Blue, Thick},
   2 \[UndirectedEdge] 4 -> {Blue, Thick},
   4 \[UndirectedEdge] 8 -> {Blue, Thick},
   8 \[UndirectedEdge] 7 -> {Blue, Thick},
   7 \[UndirectedEdge] 3 -> {Blue, Thick}}]

POSTED BY: Shenghui Yang
Posted 11 years ago
The output of 384 refers to the number of spanning trees in the 3-hypercube graph. A spanning tree is basically a connected acyclic subset of edges in the graph such that each vertex in the graph is incident on at least one edge in the subset. (Kirchoff's Theorem gives a very nice and efficient algorithm for computing the number of spanning trees, and Combinatorica.m uses that approach.)

You can use Combinatorica's MinimumSpanningTree to get at least one MST. To get other ones, you could delete an edge you would like to avoid and put the edge-deleted graph through MinimumSpanningTree again. That feels kind of hacky, but it is easy enough to do for only ~10 MSTs if you just need them quickly.

 Block[{$ContextPath}, Quiet@Needs@"Combinatorica`"]
 
 Needs@"GraphUtilities`"
 
 g = HypercubeGraph@3;
 
 cg = Combinatorica`MakeUndirected@ToCombinatoricaGraph@g;
 
 mst = Combinatorica`MinimumSpanningTree@cg;

Combinatorica`ShowGraph@mst

AdjacencyGraph@Combinatorica`ToAdjacencyMatrix@mst

POSTED BY: William Rummler
Definitely two thumbs up to the workaround !

My secound question would be what this 384 means? I think I can only draw several (not full set but definitely not more than 10) spanning trees for a 3-cube graph, per my understanding, it is just a set of edges of 3-D cube, right? 
POSTED BY: Shenghui Yang
Posted 11 years ago
Hey Shenghui,

HypercubeGraph returns a System`Graph, not a Combinatorica`Graph. Try this:

Block[{$ContextPath}, Needs@"Combinatorica`"]

Needs@"GraphUtilities`"

Combinatorica`NumberOfSpanningTrees@
ToCombinatoricaGraph@HypercubeGraph@3

(* Out: 384 *)

--William
POSTED BY: William Rummler
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract