11
$\begingroup$

Cayley's formula tells us that the number of labeled trees with $n$ vertices is $n^{n-2}$. Here is Wikipedia's visualization for $n=2,3,4$.

How can we use Mathematica to visualize cases where $n > 4$?

$\endgroup$
8
$\begingroup$

I have upvoted @Szabolcs answer. I am sure there are better code to tree approaches than mine in the following. IGraphM is ideal as Szabolcs illustrates. I post this just to extend visualization for $n>4$ case.

Happy New Year to all MSE users

Just some visualization options:

fun[code_] := 
 Module[{v = Range[Length[code] + 2], cd = code, e = {}, c},
  While[Length[v] != 2,
   c = Sort[Complement[v, cd]];
   AppendTo[e, {cd[[1]], c[[1]]}];
   v = DeleteCases[v, c[[1]]];
   cd = Drop[cd, 1];];
  Graph[UndirectedEdge @@@ AppendTo[e, v], VertexSize -> 0.3, 
   VertexLabels -> 
    Table[i -> Placed[Style[i, White, Bold], {1/2, 1/2}], {i, 
      v[[-1]]}], 
   VertexStyle -> 
    Table[i -> ColorData["Rainbow"][i/v[[-1]]], {i, v[[-1]]}]]]
disp[n_] := 
 Grid[Partition[Column[{#, fun[#]}] & /@ Tuples[Range[n], n - 2], n], 
  Frame -> All]
man[u_] := 
 Manipulate[fun[{##}[[All, 1]]], ##, ControlType -> SetterBar] & @@ 
  Table[{Symbol["x" <> ToString[i]], Range[u]}, {i, u - 2}]

So, disp[4]:

enter image description here

And man[10] (note this is inspired by this Wolfram Demonstration but generalizes the visualization and I do not use the same code for creating tree from Prufer code). : enter image description here

| improve this answer | |
$\endgroup$
  • $\begingroup$ ubpdqn: Wonderful answer. Out of curiosity: did you make the video of you mousing over man[10] with Mathematica, or another tool? $\endgroup$ – George Dec 31 '19 at 16:30
  • $\begingroup$ @George ScreenToGIF $\endgroup$ – ubpdqn Dec 31 '19 at 22:24
  • 1
    $\begingroup$ Happy New Year to all $\endgroup$ – ubpdqn Dec 31 '19 at 22:25
20
$\begingroup$

You can use Prüfer sequences to generate all labelled trees. IGraph/M has the required functionality.

coloredPruferTree[p_] := 
  IGFromPrufer[p, GraphStyle -> "BasicBlack", VertexSize -> 1/4] // 
   IGVertexMap[ColorData[97], VertexStyle -> VertexList]

allTrees[n_] := 
  coloredPruferTree /@ Tuples[Range /@ ConstantArray[n, n - 2]]

Now you can list all labelled trees on 3 vertices:

allTrees[3]

enter image description here

Or 4 vertices:

allTrees[4]

enter image description here

Furthermore, you can group the trees by isomorphism class using

allTrees[5] // GroupBy[CanonicalGraph] // Values
| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ A tiny comment on German orthography: When you don't have access to Umlaut characters, don't just leave out the Umlaut but replace it by a letter E. So Prüfer becomes Pruefer without Umlaut. That said, fantastic work Szabolcs! $\endgroup$ – Roman Dec 31 '19 at 11:55
  • 1
    $\begingroup$ @Roman Do you mean in the function name? I actually thought for a while about whether to use IGFromPrufer or IGFromPruefer, then did a search to see what most other systems use. None of the ones I found were using Pruefer so I went with Prufer ... But then many of them don't even spell Prüfer correctly in their documentation, so perhaps I should have consulted a native German speaker. (In text / documentation I made sure to always put on the umlaut. I do care about it as Hungarian has it too.) $\endgroup$ – Szabolcs Dec 31 '19 at 12:39
  • $\begingroup$ Yes, like GroebnerBasis computes the Gröbner basis, MandelbrotSetBoettcher and JuliaSetBoettcher the Böttcher function, MoebiusMu the Möbius function, etc. $\endgroup$ – Roman Jan 9 at 18:45

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.