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$?
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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]:
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). :
-
$\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– George2019-12-31 16:30:36 +00:00Commented Dec 31, 2019 at 16:30 -
$\begingroup$ @George ScreenToGIF $\endgroup$ubpdqn– ubpdqn2019-12-31 22:24:36 +00:00Commented Dec 31, 2019 at 22:24
-
1$\begingroup$ Happy New Year to all $\endgroup$ubpdqn– ubpdqn2019-12-31 22:25:23 +00:00Commented Dec 31, 2019 at 22:25
$\begingroup$
$\endgroup$
3
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]
Or 4 vertices:
allTrees[4]
Furthermore, you can group the trees by isomorphism class using
allTrees[5] // GroupBy[CanonicalGraph] // Values
-
2$\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– Roman2019-12-31 11:55:44 +00:00Commented Dec 31, 2019 at 11:55
-
1$\begingroup$ @Roman Do you mean in the function name? I actually thought for a while about whether to use
IGFromPruferorIGFromPruefer, then did a search to see what most other systems use. None of the ones I found were usingPrueferso I went withPrufer... 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– Szabolcs2019-12-31 12:39:10 +00:00Commented Dec 31, 2019 at 12:39 -
1$\begingroup$ Yes, like
GroebnerBasiscomputes the Gröbner basis,MandelbrotSetBoettcherandJuliaSetBoettcherthe Böttcher function,MoebiusMuthe Möbius function, etc. $\endgroup$Roman– Roman2020-01-09 18:45:52 +00:00Commented Jan 9, 2020 at 18:45