/ 
Graph-Maker-Other-2
River stage zero No dependents
/ Graph::Maker::FibonacciTree

NAME

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

SYNOPSIS

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

DESCRIPTION

Graph::Maker::FibonacciTree creates Graph.pm graphs of Fibonacci trees.

Full Tree

The default is a tree in the style of Hugo Steinhaus "Mathematical Snapshots", 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 original 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 -> 01 and 1 -> 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.

Series Reduced

Option series_reduced => 1 eliminates non-leaf delay nodes. These are all the nodes with a single child. 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 N has left sub-trees order N-1 and right sub-tree N-2, starting from orders 0 and 1 both a single node.

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

This is the style of Knuth volume 3 section 6.2.1.

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

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

Series and Leaf Reduced

Options series_reduced => 1, leaf_reduced => 1 together eliminate all the delay nodes.

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

This style can be formed by left and right sub-trees of order N-1 and N-2, with an order 0 reckoned as no tree at all and order 1 a single node.

         root               tree of order N
       /      \               starting order 0 = no tree at all
order N-1     order N-2                order 1 = single node

In this form nodes can have 0, 1 or 2 children. For a tree height H the number of nodes with each, and the total nodes in the tree, are

                count
               -------
0 children      F(H)
1 children      F(H-1), or 0 when H=0
2 children      F(H) - 1, or 0 when H=0
total nodes     F(H+2)-1

The 1-child nodes are where leaf_reduced has removed a leaf node from the series_reduced form.

This tree form is the maximum unbalance for an AVL tree. In an AVL tree each node has left and right sub-trees with height differing by at most 1. This Fibonacci tree has every node with left and right sub-tree heights differing by 1.

Leaf Reduced

Option leaf_reduced => 1 alone eliminates from the full tree just the delay nodes which are leaf nodes. In the height 4 example in "Full Tree" above these are nodes 8 and 11.

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

The effect of this is merely to repeat the second last row, ie. there is a single child under every node of the second last row.

FUNCTIONS

$graph = Graph::Maker->new('fibonacci_tree', key => value, ...)

The key/value parameters are

height          =>  integer
series_reduced  =>  boolean (default false)
leaf_reduced    =>  boolean (default false)

Other parameters are passed to Graph->new().

height is how many rows of nodes. So height => 1 is a single row (the root node only).

Like Graph::Maker::BalancedTree, if the graph is directed (the default) then edges are added both up and down between each parent and child. Option undirected => 1 creates an undirected graph and for it there is a single edge from parent to child.

SEE ALSO

Graph::Maker, Graph::Maker::BalancedTree

Math::NumSeq::FibonacciWord

LICENSE

Copyright 2015 Kevin Ryde

This file is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

This file is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with This file. If not, see http://www.gnu.org/licenses/.