Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 LabeledTreeToPruferCode

Source Notebook

Find the Prüfer code associated with a labeled tree

Contributed by: Wolfram Staff (original content by Sriram V. Pemmaraju and Steven S. Skiena)

ResourceFunction["LabeledTreeToPruferCode"][g]

gives the Prüfer code associated with the labeled tree g.

Details and Options

A labeled tree is a tree graph of n vertices where each vertex is uniquely associated with one of the integers 1-n.
For a labeled tree with n vertices, the Prüfer code (also known as the Prüfer sequence and Prüfer numbers) is a list of n-2 integers {i1,i2,…,in-2} with 1≤ij≤n.

Examples

Basic Examples (1) 

The Prüfer code of a labeled tree:

In[1]:=
ResourceFunction["LabeledTreeToPruferCode"][\!\(\* GraphicsBox[ NamespaceBox["NetworkGraphics", DynamicModuleBox[{Typeset`graph = HoldComplete[ Graph[{1, 2, 4, 3, 5, 6}, {Null, {{1, 2}, {2, 3}, {2, 4}, {4, 5}, {4, 6}}}]]}, TagBox[GraphicsGroupBox[ GraphicsComplexBox[{{0., 0.8164965809277261}, { 0.8164965809277261, 1.6329931618554523`}, { 0.8164965809277261, 0.8164965809277261}, { 1.6329931618554523`, 0.8164965809277261}, { 1.2247448713915892`, 0.}, {2.041241452319315, 0.}}, { {Hue[0.6, 0.7, 0.5], Opacity[0.7], LineBox[{{1, 2}, {2, 3}, {2, 4}, {4, 5}, {4, 6}}]}, {Hue[0.6, 0.2, 0.8], EdgeForm[{GrayLevel[0], Opacity[0.7]}], DiskBox[1, 0.022945218072026957], DiskBox[2, 0.022945218072026957], DiskBox[3, 0.022945218072026957], DiskBox[4, 0.022945218072026957], DiskBox[5, 0.022945218072026957], DiskBox[6, 0.022945218072026957]}}]], MouseAppearanceTag["NetworkGraphics"]], AllowKernelInitialization->False]], DefaultBaseStyle->{"NetworkGraphics", FrontEnd`GraphicsHighlightColor -> Hue[0.8, 1., 0.6]}, FormatType->TraditionalForm, FrameTicks->None]\)]
Out[1]=

Properties and Relations (6) 

Use FromDigits to obtain an integer-valued Prüfer code:

In[2]:=
GraphData[{"BananaTree", {3, 6}}]
Out[2]=
In[3]:=
ResourceFunction["LabeledTreeToPruferCode"][%]
Out[3]=
In[4]:=
FromDigits[%]
Out[4]=

For a tree with n vertices, the length of the Prüfer code is n-2:

In[5]:=
g = CompleteKaryTree[4, 2]
Out[5]=
In[6]:=
ResourceFunction["LabeledTreeToPruferCode"][g]
Out[6]=
In[7]:=
Length[%] == VertexCount[g] - 2
Out[7]=

Empty Prüfer code corresponds to a tree with only two leaves:

In[8]:=
ResourceFunction["LabeledTreeToPruferCode"][ Graph[{1 \[UndirectedEdge] 2}]]
Out[8]=

The resource function PruferCodeToLabeledTree can be used to reconstruct the tree from its Prüfer code:

In[9]:=
ResourceFunction["LabeledTreeToPruferCode"][\!\(\* GraphicsBox[ NamespaceBox["NetworkGraphics", DynamicModuleBox[{Typeset`graph = HoldComplete[ Graph[{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40}, {Null, SparseArray[ Automatic, {40, 40}, 0, {1, {{0, 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78}, {{2}, {3}, {4}, {1}, {5}, {6}, {7}, {1}, {8}, {9}, { 10}, {1}, {11}, {12}, {13}, {2}, {14}, {15}, {16}, {2}, { 17}, {18}, {19}, {2}, {20}, {21}, {22}, {3}, {23}, {24}, { 25}, {3}, {26}, {27}, {28}, {3}, {29}, {30}, {31}, {4}, { 32}, {33}, {34}, {4}, {35}, {36}, {37}, {4}, {38}, {39}, { 40}, {5}, {5}, {5}, {6}, {6}, {6}, {7}, {7}, {7}, {8}, { 8}, {8}, {9}, {9}, {9}, {10}, {10}, {10}, {11}, {11}, { 11}, {12}, {12}, {12}, {13}, {13}, {13}}}, Pattern}]}, {VertexCoordinates -> CompressedData[" 1:eJxTTMoPSmViYGDQAGIQjQ7idnnyMK0WOgDhfdiPKvthP1TeAcYXv3nue/Bj Cah6hgOo+hkOQOQ54Hwf807HhKc/YObCxBnQ5O3R9Dugme+AKi8B5wtEWG45 8U0Kai7HAVT3cRwAG39BDM635bq+uGCvCJyP6n6OAynW9/17pwvA+SDltly8 aOZzwPkg68v2saDpZ4DzUf0Pk/8A558HmrZ09gM4HzV44PL2aPrhfNTwg9vv gOY+OB81fOH+c0DVLwDno4Y/PPzgfGj4opkvAedD4wfOBwDt+6tp "]}]]}, TagBox[GraphicsGroupBox[GraphicsComplexBox[CompressedData[" 1:eJxTTMoPSmViYGDQAGIQjQ7idnnyMK0WOgDhfdiPKvthP1TeAcYXv3nue/Bj Cah6hgOo+hkOQOQ54Hwf807HhKc/YObCxBnQ5O3R9Dugme+AKi8B5wtEWG45 8U0Kai7HAVT3cRwAG39BDM635bq+uGCvCJyP6n6OAynW9/17pwvA+SDltly8 aOZzwPkg68v2saDpZ4DzUf0Pk/8A558HmrZ09gM4HzV44PL2aPrhfNTwg9vv gOY+OB81fOH+c0DVLwDno4Y/PPzgfGj4opkvAedD4wfOBwDt+6tp "], { {Hue[0.6, 0.7, 0.5], Opacity[0.7], LineBox[{{1, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}, {2, 7}, { 3, 8}, {3, 9}, {3, 10}, {4, 11}, {4, 12}, {4, 13}, {5, 14}, {5, 15}, {5, 16}, {6, 17}, {6, 18}, {6, 19}, {7, 20}, {7, 21}, {7, 22}, {8, 23}, {8, 24}, {8, 25}, {9, 26}, {9, 27}, {9, 28}, {10, 29}, {10, 30}, {10, 31}, {11, 32}, {11, 33}, {11, 34}, {12, 35}, {12, 36}, {12, 37}, { 13, 38}, {13, 39}, {13, 40}}]}, {Hue[0.6, 0.2, 0.8], EdgeForm[{GrayLevel[0], Opacity[0.7]}], DiskBox[1, 0.07642189684349937], DiskBox[2, 0.07642189684349937], DiskBox[3, 0.07642189684349937], DiskBox[4, 0.07642189684349937], DiskBox[5, 0.07642189684349937], DiskBox[6, 0.07642189684349937], DiskBox[7, 0.07642189684349937], DiskBox[8, 0.07642189684349937], DiskBox[9, 0.07642189684349937], DiskBox[10, 0.07642189684349937], DiskBox[11, 0.07642189684349937], DiskBox[12, 0.07642189684349937], DiskBox[13, 0.07642189684349937], DiskBox[14, 0.07642189684349937], DiskBox[15, 0.07642189684349937], DiskBox[16, 0.07642189684349937], DiskBox[17, 0.07642189684349937], DiskBox[18, 0.07642189684349937], DiskBox[19, 0.07642189684349937], DiskBox[20, 0.07642189684349937], DiskBox[21, 0.07642189684349937], DiskBox[22, 0.07642189684349937], DiskBox[23, 0.07642189684349937], DiskBox[24, 0.07642189684349937], DiskBox[25, 0.07642189684349937], DiskBox[26, 0.07642189684349937], DiskBox[27, 0.07642189684349937], DiskBox[28, 0.07642189684349937], DiskBox[29, 0.07642189684349937], DiskBox[30, 0.07642189684349937], DiskBox[31, 0.07642189684349937], DiskBox[32, 0.07642189684349937], DiskBox[33, 0.07642189684349937], DiskBox[34, 0.07642189684349937], DiskBox[35, 0.07642189684349937], DiskBox[36, 0.07642189684349937], DiskBox[37, 0.07642189684349937], DiskBox[38, 0.07642189684349937], DiskBox[39, 0.07642189684349937], DiskBox[40, 0.07642189684349937]}}]], MouseAppearanceTag["NetworkGraphics"]], AllowKernelInitialization->False]], DefaultBaseStyle->{"NetworkGraphics", FrontEnd`GraphicsHighlightColor -> Hue[0.8, 1., 0.6]}, FormatType->TraditionalForm, FrameTicks->None]\)]
Out[9]=
In[10]:=
ResourceFunction["PruferCodeToLabeledTree"][%]
Out[10]=

The Prüfer code of a path is a sequence of n-2 distinct integers:

In[11]:=
n = 10;
In[12]:=
GraphData[{"Path", n}]
Out[12]=
In[13]:=
ResourceFunction["LabeledTreeToPruferCode"][%]
Out[13]=

The Prüfer code for an n-pointed star with the center vertex k is a sequence of n-1 copies of k:

In[14]:=
StarGraph[6, VertexLabels -> "Name"]
Out[14]=
In[15]:=
ResourceFunction["LabeledTreeToPruferCode"][%]
Out[15]=

Possible Issues (2) 

LabeledTreeToPruferCode does not work on non-explicit trees:

In[16]:=
ResourceFunction["LabeledTreeToPruferCode"][CompleteKaryTree[n, m]]
Out[16]=

Substitute numbers for symbolic values to find the Prüfer code:

In[17]:=
CompleteKaryTree[n, m] /. {n -> 4, m -> 2}
Out[17]=
In[18]:=
ResourceFunction["LabeledTreeToPruferCode"][%]
Out[18]=

LabeledTreeToPruferCode accepts only trees with vertices numbered sequentially, starting from 1:

In[19]:=
g = Graph[{1 \[UndirectedEdge] 2, 1 \[UndirectedEdge] "three"}]
Out[19]=
In[20]:=
ResourceFunction["LabeledTreeToPruferCode"][g]
Out[20]=

Normalize labeling:

In[21]:=
VertexReplace[g, {"three" -> 3}]
Out[21]=
In[22]:=
ResourceFunction["LabeledTreeToPruferCode"][%]
Out[22]=

Version History

  • 1.0.0 – 28 July 2020

Related Resources

License Information