Prüfer Codes of Labeled Trees

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

In 1889, Cayley proved that there are labeled trees on nodes. In 1918, Prüfer found a method for constructing each tree.

[more]

Consider the tree with code {2, 8, 9, 4, 7, 7, 2} that is given as the default tree in this Demonstration. The first digit of the Prüfer code is the branch that has the smallest isolated number. Pruning that branch gives a new tree, and the process repeats, as shown in the Details.

[less]

Contributed by: Ed Pegg Jr (March 2011)
Open content licensed under CC BY-NC-SA


Snapshots


Details

The smallest non-branch number is 1. Cut it from 2. The smallest non-branch number is 3. Cut it from 8. The smallest non-branch number is 5. Cut it from 9. The smallest non-branch number is 6. Cut it from 4. The smallest non-branch number is 4. Cut it from 7. The smallest non-branch number is 8. Cut it from 7. The smallest non-branch number is 7. Cut it from 2.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send