An easy way to convince yourself of this is to doodle the trees on some paper. Then you can see that a tree with 3 leaves has 1 internal node, 4 leaves have 2 internal nodes, 5 leaves have 3 internal nodes, 6 has 4, 7 has 5, 8 has 6 and so on:
Thursday 4 August 2016
Counting Phylogenetic Ancestors
This was probably the easiest problem so far. In fact, you don't even need to do any programming because the calculation is so simple. The only thing you need to realise is that for any unrooted binary tree with n leaves, the number of internal nodes is equal to n-2.
An easy way to convince yourself of this is to doodle the trees on some paper. Then you can see that a tree with 3 leaves has 1 internal node, 4 leaves have 2 internal nodes, 5 leaves have 3 internal nodes, 6 has 4, 7 has 5, 8 has 6 and so on:
An easy way to convince yourself of this is to doodle the trees on some paper. Then you can see that a tree with 3 leaves has 1 internal node, 4 leaves have 2 internal nodes, 5 leaves have 3 internal nodes, 6 has 4, 7 has 5, 8 has 6 and so on:
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment