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 yearbyyear 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(k1) and T(k2). 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 subtree of height H1 but the right delays by one level and under there is a tree height H2.
tree(H)
/ \ tree of height H
tree(H1) node
/ \ 
tree(H2) node tree(H2)
/ \  / \
... ... ... ... ...
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 nonleaf 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 subtrees order k1 and right subtree k2, starting from orders 0 and 1 both a single node.
root tree of order k
/ \ starting order 0 or 1 = single node
order(k1) order(k2)
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 subtrees of order k1 and k2, 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 k1 order k2 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(H1), or 0 when H=0
2 children F(H)  1, or 0 when H=0
total nodes F(H+2)1
The 1child 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 subtrees with height differing by at most 1. This Fibonacci tree has every node with left and right subtree 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
orGraph>new()
.height
is how many rows of nodes. Soheight => 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. Optionundirected => 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 subtrees 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*(k3)*F(k+3) + 2/5*(k2)*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(k1) + WTb(k2) + F(k+1)*DTb(k2) + F(k)*DTb(k1)
+ 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*k3 which is attained between the deepest vertices of the left and right subtrees. 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*k2)*F(k+1) + 1/5*(2*k8)*F(k+2) + 2
= 0, 0, 2, 6, 16, 36, 76, 152, 294, ... (A178523)
WS(k) = 1/5*( (2*k18)* (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*k3 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*k1)*( 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*k2 (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*k1)*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
http://oeis.org/A180567 (etc)
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
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/.