Does anyone has experience with writing a program that can calculate the number of possible non-isomorphic trees for any node (in graph theory)?
Any tree can be converted to an equivalent (isomorphic) binary tree by taking child-brother pointer. Therefore , Peter's answer can be taken for any tree.
See Harary and Palmer's Graphical Enumeration. Also https://oeis.org/A000055
A general method to obtain the number of non-labeled structures (such as trees) consists:
1) in computing the so-called Cycle Index Series- CIS- (Polya) of the structure and
2) for all i, replacing x_i by x^i in the CIS
3) collecting and summing terms of same degrees in x.
Result: The coefficient of x^n will give you the number of unlabeld structures on n points.
There has been a similar question by Prasanth G. Narasimha-Shenoi which runs since Jun 12, 2013. The (two) answers and references given there may be of some help.
Dear Patricia,
The following articles seem to provide solutions to your queries.
J Boomen, Non-isomorphic spanning trees of graphs - http://www.math.ru.nl/~bosma/Students/JannekevandenBoomen/JannekevdBoomenMScthesis.pdf
K. Yamanaka, Y. Otachi, S.-I. Nakano, Efficient Enumeration of Ordered Trees with k Leaves, http://link.springer.com/chapter/10.1007%2F978-3-642-00202-1_13
Hi Patricia,
If you mean number of rooted trees with n nodes, please check http://oeis.org/A000081
If you mean number of trees with n unlabeled nodes, please check http://oeis.org/A000055
Also, please check my question in following link that is about your question !
https://www.researchgate.net/post/Is_there_a_method_based_on_product_and_sum_principles_for_counting_non-isomorphic_trees_acyclic_graphs
- Badges
- Science topic
- Similar topics
- Linguistics
- Composition Studies
- Publication