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, 2021 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, 2021 at 7:56

3 Answers 3

8
$\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, 2021 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, 2021 at 9:53
  • $\begingroup$ Thank you @Adam and Mubarak for the kind words. $\endgroup$
    – kglr
    Mar 9, 2021 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, 2021 at 9:17
3
$\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 and acknowledge you have read our privacy policy.

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