Forest

Author

Eric W. Weisstein
May 29, 2004

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

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

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

Enumeration

Length/@(forests=Select[#,AcyclicQ]&/@Graphs/@Range[8])//Timing

Length/@(forests=Select[#,AcyclicQ]&/@Graphs/@Range[9])//Timing

Length/@(GraphData["Acyclic",#]&/@Range[7])

Check

Unconnected forests

ConnectedComponentGraphs[g_System`Graph]:=Subgraph[g,#]&/@System`ConnectedComponents[g]

l=Monitor[{g=#,!ConnectedGraphQ[GraphData[#]]&&(TreeGraphQ/@(And@@ConnectedComponentGraphs[GraphData[#]]))//Timing}&/@GraphData[All],g];//Timing

Acyclic

GraphData[{8,14},#]&/@{"Forest","Acyclic"}

wrong=Select[GraphData[All],GraphData[#,"Forest"]=!=GraphData[#,"Acyclic"]&]

l={#,{0,GraphData[#,"Acyclic"]}}&/@wrong

Figure

ShowGraphArray[Flatten[Partition[#,6,6,{1,1},{}]&/@Take[forests,5],1],VertexStyle->Disk[.12],
GraphicsSpacing->.2]

ForestEmbedding[g_Graph]:=GraphUnion@@(RootedEmbedding/@(InduceSubgraph[g,#]&/@ConnectedComponents[g]))

Show[GraphicsArray[
Block[{$DisplayFunction=Identity},Map[ShowGraph[ForestEmbedding[#],
VertexStyle->Disk[.12]]&,Flatten[Partition[#,6,6,{1,1},{}]&/@Take[forests,5],1],
{2}]
]
],
GridLines->{{Automatic,Black},{Automatic,Black}}
]

ConectedComponents[forests[[3,

ShowGraphArray[Flatten[Partition[#,6,6,{1,1},{}]&/@Map[RootedEmbedding,Take[forests,5],{2}],1],VertexStyle->Disk[.12]]

Connected Components

cc=Sort/@Map[Length[ConnectedComponents[#]]&,forests,
{2}]

Plus@@@cc

ave=Mean/@cc

N[ave]

Through[{Numerator,Denominator}[ave]]

counts=(Length/@Split[#]&)/@cc

Plus@@@counts