HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Numbering of unlabelled trees

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
numberingunlabelledtrees

Problem

For labelled trees there are the Pruefer numbers that uniquely identify them. Is there a similar numbering system for unlabelled trees?

Solution

According to Wikipedia, a closed-form formula for the number of unlabelled trees is not known, so a numbering in the form of a bijection between the set of unlabelled trees on $n$ vertices and $\{1,\ldots,T_n\}$ (for an appropriate $T_n$) is probably hopeless. Tree isomorphism is in P, so if you want an "effectively unique" identifier for trees, you can get it by using the Prüfer numbering and applying the algorithm to test equality. It is also possible that you can canonicalize trees (using the same ideas as in the algorithm), thereby creating a coding scheme in which two isomorphic trees get the same (Prüfer) number.

Context

StackExchange Computer Science Q#16223, answer score: 3

Revisions (0)

No revisions yet.