3
$\begingroup$

Is there a way I can generate all the spanning tree in the following graph:

enter image description here

Also, is there a way to insert the adjacency matrix, then I get an output of all possible spanning trees?
The adjacency matrix $$ A = \left( \begin{matrix} 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 \end{matrix} \right) $$

$\endgroup$
2
  • $\begingroup$ What have you tried so far? Have you written the adjacency matrix for this? Please, share such things with us so that we may help to better answer your question? $\endgroup$ Mar 9 at 7:42
  • $\begingroup$ @CATrevillian Thank you, I add the adjacency matrix, but I don't know where to start to final all the possible spanning tree. $\endgroup$ Mar 9 at 7:56
7
$\begingroup$
am = {{0, 1, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0}, {0, 1, 0, 1, 1, 0}, {0, 
    0, 1, 1, 0, 1}, {0, 0, 1, 1, 0, 1}, {1, 0, 0, 1, 1, 1}};

g0 = UndirectedGraph[SimpleGraph @ AdjacencyGraph @ am, 
  VertexCoordinates -> Reverse @ CirclePoints[{1, Pi}, 6], 
  VertexLabels -> "Name"]

enter image description here

trees = Select[TreeGraphQ[Graph@#] &] @ Select[VertexCount @ # == 6 &]@ 
  Subsets[EdgeList[g0], {5}];

Length @ trees
32

This matches what we should expect from Kirchhoff's Theorem:

Det[KirchhoffMatrix[g0][[2 ;;, 2 ;;]]]
32

We can also get the same number using IGSpanningTreeCount from IGraphM package:

<< IGraphM`
IGSpanningTreeCount[g0]
32

These 32 trees fall into three isomorphic groups:

Length /@ Gather[Graph /@ trees, IsomorphicGraphQ]
{10, 16, 6}
Graph[#, VertexLabels -> Placed["Name", Center], VertexStyle -> White,
    GraphLayout -> "LayeredEmbedding", 
    VertexShapeFunction -> (Disk[#, Offset[7]] &), 
    AspectRatio -> 1] & /@ trees // Multicolumn[#, 6] &

enter image description here

HighlightGraph[g0, #, GraphHighlightStyle -> "Thick"] & /@ trees // 
 Multicolumn[#, 6, Appearance -> "Horizontal"] &

enter image description here

$\endgroup$
3
  • $\begingroup$ You are amazing! Thanks a lot. $\endgroup$ Mar 9 at 9:17
  • $\begingroup$ I didn't think your answer could be improved. But then you added Kirchhoff's Theorem! Awesome! $\endgroup$
    – Adam
    Mar 9 at 9:53
  • $\begingroup$ Thank you @Adam and Mubarak for the kind words. $\endgroup$
    – kglr
    Mar 9 at 9:58
3
$\begingroup$

Does the following what you want? First we create the graph from the adjacency matrix:

a = {{0, 1, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0}, {0, 1, 0, 1, 1, 0}, {0, 
    0, 1, 0, 1, 1}, {0, 0, 1, 1, 0, 1}, {1, 0, 0, 1, 1, 0}};
agr = AdjacencyGraph[a]

Then we create the spanning trees:

FindSpanningTree[{agr, #}, VertexLabels -> "Name"] & /@ Range[6]

$\endgroup$
1
  • $\begingroup$ Thank you. But it does not generate all of them. But @Kglr solved it. $\endgroup$ Mar 9 at 9:17
1
$\begingroup$

I may as well add a way to construct the graph

g=Graph[Join[#\[UndirectedEdge]#+1&/@Range@5,{1\[UndirectedEdge]6,
3\[UndirectedEdge]5,4\[UndirectedEdge]6}]]

In general Mathematica has no good way to do this. Here's a naive method.

Trees on $n$ vertices have $n-1$ edges. For every length $n-1$ tuple of edges, is it a tree?

trees=Select[Tuples[EdgeList@g,{VertexCount@g-1}],TreeGraphQ@Graph@#&]

For the g in question, I find 3840 unique trees. Of course Subsets is appropriate as opposed to Tuples, which causes this confusion. Here's a neat way to find all isomorphic trees:

Module[{l={}},For[i=1,i<=Length@trees,++i,
    If[And@@Table[Not@IsomorphicGraphQ[Graph@e,Graph@trees[[i]]],{e,l}],
    AppendTo[l,trees[[i]]]
]];l]

which produces 3 unique-up-to-isomorphism trees.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.