/ 
Graph-Maker-Other-19
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.

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. the last row is a single child under each node of the second last.

Direction Type

The default is a directed graph with edges both ways between vertices (like most Graph::Maker directed graphs). This is parameter direction_type => 'both'.

Optional direction_type => 'bigger' or 'child' gives edges directed to the bigger vertex number, so from smaller to bigger. This means parent down to child.

Option direction_type => 'smaller' or 'parent' gives edges directed to the smaller vertex number, so from bigger to smaller. This is from child up to parent.

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)
direction_type => string, "both" (default), 
                    "bigger", "smaller", "parent, "child"
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.

If the graph is directed (the default) then edges are added as described in "Direction Type" above. Option undirected => 1 is an undirected graph and for it there is always a single edge between parent and 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?)

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)*(29*F(k+4) - 10)  - 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, 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)*( F(k+4) - 6*F(k+3) + 18 )
                    - 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

all
  1310    height=1, singleton

default
  32234   height=2, path-3
  288     height=3
  21059   height=5

series_reduced=1
  32234   height=2, path-3
  30      height=3
  25131   height=4
  21048   height=6

leaf_reduced=1
  19655   height=2, path-2
  286     height=3, path-5

series_reduced=1, leaf_reduced=1
  19655   height=2, path-2
  594     height=3, path-4
  934     height=4

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

HOME PAGE

http://user42.tuxfamily.org/graph-maker-other/index.html

LICENSE

Copyright 2015, 2016, 2017, 2018, 2019, 2020, 2021 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/.