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?

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

1 Answer 1

Reset to default
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.

Improve this answer
$\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.