Tree

Author

Eric W. Weisstein
January 18, 2024

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Tree.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/Tree.html.

©2024 Wolfram Research, Inc. except for portions noted otherwise

Counts

A000055

1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, …

<<MathWorld`Graphs`

Length/@Table[KTrees[1][n],{n,15}]//Timing

Table[Total[Boole[TreeGraphQ/@ConnectedGraphs[n]]],{n,10}]//Timing

Table[Total[Boole[TreeGraphQ/@Graphs[n]]],{n,10}]//Timing

Table[Total[Boole[TreeGraphQ/@Trees[n]]],{n,15}]//Timing

Table[Length@GraphData["Tree",n],{n,12}]

Trees = Acyclic Connected Graphs

Function[f,Count[f,_?(ConnectedQ[#]&&AcyclicQ[#]&)]]/@Graphs/@Range[9]//Timing

Trees = connected graphs on n nodes with n-1 edges

Table[Count[Graphs[n],_?(M[#]==n-1&&ConnectedQ[#]&)],{n,9}]//Timing

Graphics

GraphicsGrid[Table[Trees[n]/.g_System`Graph:>SetProperty[g,{VertexSize->If[n==1,.02,{"Scaled",.1}],System`VertexStyle->Red,System`EdgeStyle->Black}],{n,6}],Dividers->All]

Recurrence

Unlabeled Rooted Trees

A000081

T[0]=0;
T[1]=1;
T[n_Integer]:=T[n]=Sum[T[n-j]Total[# T[#]&/@Divisors[j]],{j,n-1}]/(n-1)

T/@Range[20]

Polynomial[l_List, x_] := Fold[x #1+#2 &,0,l]

T[x_,n_]:=x Polynomial[T/@Range[n,1,-1],x]

Unlabeled Unrooted Trees

A000055

t[x_,n_]:=Normal[Series[T[x,n]-(T[x,n]^2-T[x^2,n])/2,{x,0,n}]]

t[x,20]

CoefficientList[t[x,20],x]

NumberOfTrees[n_Integer]:=Coefficient[t[x,n],x^n]

Table[NumberOfTrees[n],{n,12}]

Constants

α

Block[{$RecursionLimit=1000},
x/.FindRoot[T[1/x,300]==1,{x,2.9,3},WorkingPrecision->20]
]//Timing

Block[{$RecursionLimit=2000},
With[{n=500},
N[T[n]/T[n-1],20]
]
]//Timing

Actual value is 2.95576528565199497…

N[t[500]/t[499],20]

α=2.95576528565199497471481752412319458837549230466359659535047247890596473313957495108666828367658135;

β

With[{n=600},N[t[n]n^(5/2)/α^n,20]]

(1+Sum[x D[T[x],x]/.x->1/α^k,{k,2,300}])^(3/2)/Sqrt[2π]

(1+Sum[x D[T[x,50],x]/.x->1/α^k,{k,2,100}])^(3/2)/Sqrt[2π]

(1+Sum[x D[T[x,60],x]/.x->1/α^k,{k,2,150}])^(3/2)/Sqrt[2π]

Random tree

ShowGraph[RootedEmbedding[RandomTree[10],1],VertexStyle->Disk[.03]]

Graphics

ShowGraphArray[Flatten[Map[Partition[#,11,11,{1,1},{}]&,Trees/@Range[7],{1}],1]]

Chemical structures

ChemicalData[All]//Length

ChemicalGraph[c_]:=RecognizeGraph[FromAdjacencyMatrix[Normal[ChemicalData[c,"AdjacencyMatrix"]]]]

ChemicalStructureGraph[c_]:=RecognizeGraph[RemoveMultipleEdges[FromAdjacencyMatrix[Normal[ChemicalData[c,"AdjacencyMatrix"]]]]]

{#,ChemicalGraph[#]}&/@Take[ChemicalData[All],20]

{#,ChemicalStructureGraph[#]}&/@Take[ChemicalData[All],20]

Alkanes

DeleteCases[{#,ChemicalGraph[#]}&/@ChemicalData["Alkane"],{_,{}}]

CentralAlkane[n_]:=Module[{r=Range[n],s=1.5},
Graph[List/@Join[Partition[r,2,1],{#,#+n}&/@r,{#,#+2n}&/@r,{{n,3n+2},{1,3n+1}}],
List/@Join[{0,#}&/@r,{-s,#}&/@r,{s,#}&/@r,
{{0,1-s},{0,n+s}}]]
]

Ethane

ShowGraph[CentralAlkane[2],ImageSize->100]

Position[CanonicalForm/@Trees[8],CanonicalForm[CentralAlkane[2]]]

Trees[8][[22]]//ShowGraph

PadVertices[ToCommonEdges[CentralAlkane[2],Graph["Ethane"]]]

Propane

ShowGraph[CentralAlkane[3],ImageSize->100]

Position[CanonicalForm/@Trees[11],CanonicalForm[CentralAlkane[3]]]

Trees[11][[231]]//ShowGraph

PadVertices[ToCommonEdges[CentralAlkane[3],Trees[11][[231]]]]

Butane

ShowGraph[CentralAlkane[4],ImageSize->100]

Position[CanonicalForm/@Trees[14],CanonicalForm[CentralAlkane[4]]]

Trees[14][[68]]//ShowGraph

GraphDataString[CentralAlkane[4],
"Name"->"butane",
"StandardName"->"Butane",
"AlternateNames"->{"14-tree 68"},
"AlternateStandardNames"->{{"Tree",{14,68}}},
Debug->True
]

Isobutane

ShowLabeledGraph[isobutane=Graph[List/@Sort/@{{1,6},{6,9},{6,7},{6,8},{1,10},{10,13},{10,12},{11,10},{1,2},{2,5},{4,2},{2,3},{14,1}},List/@Join[{{0,0}},Flatten[Table[RotationMatrix[2s Pi/3].#&/@{{1,0},{1,1},{1,-1},{2,0}},{s,-1,1}],1],{{-1,0}}]]]

Position[CanonicalForm/@Trees[14],CanonicalForm[isobutane]]

Trees[14][[48]]//ShowGraph

GraphDataString[isobutane,
"Name"->"isobutane",
"StandardName"->"Isobutane",
"AlternateNames"->{"14-tree 48"},
"AlternateStandardNames"->{{"Tree",{14,48}}},
Debug->True
]

Pentane

ShowGraph[CentralAlkane[5],ImageSize->100]

Hexane

ShowGraph[CentralAlkane[6],ImageSize->100]

Heptane

ShowGraph[CentralAlkane[7],ImageSize->100]

Octane

ShowGraph[CentralAlkane[8],ImageSize->100]

Nonane

ShowGraph[CentralAlkane[9],ImageSize->100]

Decane

ShowGraph[CentralAlkane[10],ImageSize->100]