0
$\begingroup$

Suppose you are given an ancestry matrix $M$ which means that $M[ij] = 1$ iff node $i$ is an ancestor of node $j$. If $M$ represents no cycles (treated as an adjacency matrix) the corresponding graph is a tree (or a forest). My question is what is the number of trees where their ancestry matrix is $M$.

Is this question any simpler than counting number of directed graphs which are compatible to a general ancestry matrix?

$\endgroup$
2
  • 2
    $\begingroup$ Hint: Can you come up with 2 different trees that generate the same ancestry matrix? $\endgroup$ Aug 3 '19 at 18:22
  • $\begingroup$ Thank you very much @j_random_hacker $\endgroup$
    – Dandelion
    Aug 4 '19 at 5:08
0
$\begingroup$

As hinted in the comments by @j_random_hacker, ancestry matrix, if valid, characterizes a unique rooted tree. A simple algorithm would be to create the tree from leaves to the root or vice versa.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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