3
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Are these binary trees, or arbitrary trees? $\endgroup$
    – adrianN
    Oct 19, 2013 at 8:04
  • $\begingroup$ If there is a numbering system for binary trees, I would also be very interested in it. $\endgroup$ Oct 20, 2013 at 20:07

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.