view release on metacpan or  search on metacpan

lib/Graph/Maker/FibonacciTree.pm  view on Meta::CPAN

=for stopwords Ryde subtrees Steinhaus Stechert AVL ie undirected Viswanathan Iyer Udaya Kumar Reddy Intl Math Engg WTb preprint MeanDist OEIS

=head1 NAME

Graph::Maker::FibonacciTree - create Fibonacci tree graph

=for test_synopsis my ($graph)

=head1 SYNOPSIS

 use Graph::Maker::FibonacciTree;
 $graph = Graph::Maker->new ('fibonacci_tree', height => 4);

=head1 DESCRIPTION

C<Graph::Maker::FibonacciTree> creates C<Graph.pm> graphs of Fibonacci
trees.

Various authors give different definitions of a Fibonacci tree.  The
conception here is to start with year-by-year rabbit genealogy, which is
rows of width F(n), and optionally reduce out some vertices.  The
C<series_reduced> form below is quite common, made by a recursive definition
of left and right subtrees T(k-1) and T(k-2).  A further C<leaf_reduced> is
then whether to start T(0) empty rather than a single vertex.

=head2 Full Tree

The default tree is in the style of

=over

Hugo Steinhaus, "Mathematical Snapshots", Stechert, 1938, page 27

=back

starting the tree at the first fork,

            1
          /   \          height => 4
        2       3
       / \      |
      4   5     6
     / \  |    / \
    7  8  9  10   11

The number of nodes in each row are the Fibonacci numbers 1, 2, 3, 5, etc.

A tree of height H has a left sub-tree of height H-1 but the right delays by
one level and under there is a tree height H-2.

                tree(H)
              /        \             tree of height H
        tree(H-1)       node
         /    \           |
     tree(H-2) node    tree(H-2)
       /   \    |       /    \
     ...  ...  ...    ...   ...

This is the genealogy of Fibonacci's rabbit pairs.  The root node 1 is a
pair of adult rabbits.  They remain alive as node 2 and they have a pair of
baby rabbits as node 3.  Those babies do not breed immediately but only in
the generation after at node 6.  Every right tree branch is a baby rabbit
pair which does not begin breeding until the month after.

The tree branching follows the Fibonacci word.  The Fibonacci word begins as
a single 0 and expands 0 -E<gt> 01 and 1 -E<gt> 0.  The tree begins as a
type 0 node in the root.  In each level a type 0 node has two child nodes, a
0 and a 1.  A type 1 node is a baby rabbit pair and it descends to be a type
0 adult pair at the next level.

=head2 Series Reduced

Option C<series_reduced =E<gt> 1> eliminates non-leaf delay nodes.  Those
are all the nodes with a single child, leaving all nodes with 0 or 2
children.  In the height 4 example above they are nodes 3 and 5.  The result
is

            1
          /   \          height => 4
        2       3        series_reduced => 1
       / \     / \
      4   5   6   7
     / \
    8   9

A tree order k has left sub-trees order k-1 and right sub-tree k-2, starting
from orders 0 and 1 both a single node.

             root               tree of order k
           /      \               starting order 0 or 1 = single node
    order(k-1)    order(k-2)

This is the style of Knuth volume 3 section 6.2.1.

=cut

# GP-DEFINE  F(n) = fibonacci(n);
# GP-Test  vector(5,n,my(n=n-1); 2*F(n+1)-1) == [1,1,3,5,9]

=pod

Each node has 0 or 2 children.  The number of nodes of each type in tree
height H are

                       count
                     ----------
    0 children         F(H+1)
    2 children         F(H+1)-1
    total nodes      2*F(H+1)-1

=for GP-Test  my(H=4); 2*F(H+1)-1 == 9

=head2 Series and Leaf Reduced

Options C<series_reduced =E<gt> 1, leaf_reduced =E<gt> 1> together eliminate
all the delay nodes.

            1
          /   \          height => 4
        2       3        series_reduced => 1