++ed by:

1 non-PAUSE user.

Kevin Ryde
and 1 contributors

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.

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 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 leaf_reduced is then whether to start T(0) empty rather than a single vertex.

Full Tree

The default tree is in the style of

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

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 -> 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. 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.

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

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 k-1 and k-2, with an order 0 reckoned as no tree at all and order 1 a single node.

             root               tree of order k
           /      \               starting order 0 = no tree at all
    order k-1     order k-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)
    graph_maker => subr(key=>value) constructor, default Graph->new

Other parameters are passed to the constructor, either graph_maker or Graph->new().

height is how many rows of nodes. So height => 1 is a single row, being 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.

FORMULAS

Wiener Index - Series and Leaf Reduced

The Wiener index of the series and leaf reduced tree is calculated in

    K. Viswanathan Iyer and K. R. Udaya Kumar Reddy, "Wiener index of Binomial Trees and Fibonacci Trees", Intl J Math Engg with Comp, 2009. arxiv:0910.4432

They form a recurrence from the left and right sub-trees and new root, using also a sum of distances down just from the root. For a tree order k (which is also height k), those root distances total

    DTb(k) = 1/5*(k-3)*F(k+3) + 2/5*(k-2)*F(k+2) + 2
           = 0, 0, 1, 4, 11, 26, 56, 114, 223, ...      (A002940)

A recurrence for the Wiener index is then as follows. (Not the same as the WTb formula in their preprint. Is there a typo there?)

    WTb(k) = WTb(k-1) + WTb(k-2) + F(k+1)*DTb(k-2) + F(k)*DTb(k-1)
             + 2*F(k+1)*F(k) - F(k+2)

    starting WTb(0) = WTb(1) = 0

They suggest an iteration to evaluate upwards. Some generating function manipulations can also sum through to

    WTb(k) = 1/10 * ( (2*k+13) * (F(k+2) + 1)*(F(k+2) + F(k+4))
                      + F(k+2)*(10 - 29*F(k+4))  - 9*F(k+4) )

           = 0, 0, 1, 10, 50, 214, 802, 2802, 9275, ...    (A192019)

More Fibonacci identities might simplify further. Term F(k+2)+F(k+4) is the Lucas numbers.

There are F(k+2)-1 many vertices in the tree so a mean distance between distinct vertices is

    MeanDist(k) = WTb(k) / binomial(F(k+2)-1, 2)

The tree diameter is 2*k-3 which is attained between the deepest vertices of the left and right sub-trees. A limit for MeanDist as a fraction of that diameter is found by noticing the diameter cancels 2*k in WTb and using F(k+n)/F(k) -> phi^n, where phi=(1+sqrt5)/2 is the Golden ratio

    MeanDist(k)           1 + phi^2    2 + phi       1
    ----------- ->  MTb = ---------  = -------  = -------
    Diameter(k)              5            5       3 - phi

                = 0.723606...   (A242671)

Wiener Index - Series Reduced

A similar calculation for the series reduced form is, for tree order k,

    DS(k) = 1/5*(4*k-2)*F(k+1) + 1/5*(2*k-8)*F(k+2) + 2
          = 0, 0, 2, 6, 16, 36, 76, 152, 294, ...     (A178523)

    WS(k) = 1/5*( (2*k-18)* (2*F(k+1) + 1) * (2*F(k+1) + F(k+2))
                  + 78*F(k+1)^2 + 54*F(k+1) + 30*F(k+2)  )
          = 0, 0, 4, 18, 96, 374, 1380, 4696, 15336, ...    (A180567)

With vertices 2*F(k+1)-1 and diameter 2*k-3 again (for k>=2) the limit for mean distance between vertices as a fraction of the diameter is the same as above.

                   WS(k)                       
   --------------------------------------  ->  MTb  same
   Diameter(k) * binomial(2*F(k+1)-1), 2)      

Wiener Index - Full Tree

A further similar calculation for the full tree of height k gives

    Dfull(k) = k*F(k+3) - F(k+5) + 5
             = 0, 0, 2, 8, 23, 55, 120, 246, ...

    Wfull(k) = 1/10 * ( (2*k-1)*( 5*F(k+3)^2  + 2*( 2*F(k+3) + F(k+4)) )
                        + 5*( F(k+4) - 6*F(k+3) + 18 )*F(k+4)
                        - 91*F(k+2) - 10  );
             = 0, 0, 4, 32, 174, 744, 2834, 9946, ...

With number of vertices F(k+3)-2 and diameter 2*k-2 (for k>=1) the limit for mean distance between vertices as a fraction of the diameter is simply 1. (The only term in k*F^2 is the (2*k-1)*F(k+3)^2.)

                  Wfull(k)                       
   ------------------------------------  ->  1
   Diameter(k) * binomial(F(k+3)-2), 2)      

HOUSE OF GRAPHS

House of Graphs entries for graphs here include

height=5, https://hog.grinvin.org/ViewGraphInfo.action?id=21059
height=6, series_reduced https://hog.grinvin.org/ViewGraphInfo.action?id=21048

OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to these graphs include

    series_reduced=>1
      A180567   Wiener index
      A178523   distance root to all vertices
      A178522   number of vertices at depth

    series_reduced=>1,leaf_reduced=>1
      A192019   Wiener index
      A002940   distance root to all vertices
      A023610     increment of that distance
      A242671   mean distance limit between vertices
                  as fraction of tree diameter, being (1+1/sqrt(5))/2
      A192018   count nodes at distance

SEE ALSO

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

Math::NumSeq::FibonacciWord

LICENSE

Copyright 2015, 2016, 2017 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/.