- HOUSE OF GRAPHS
- SEE ALSO
Graph::Maker::FibonacciTree - create Fibonacci tree graph
use Graph::Maker::FibonacciTree; $graph = Graph::Maker->new ('fibonacci_tree', height => 4);
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.
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 => 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_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
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 => 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.
$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
heightis how many rows of nodes. So
height => 1is a single row, being the root node only.
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 => 1creates an undirected graph and for it there is a single edge from parent to child.
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)*(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)
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)
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 entries for graphs here include
- height=1, https://hog.grinvin.org/ViewGraphInfo.action?id=1310 (single vertex)
- height=3, https://hog.grinvin.org/ViewGraphInfo.action?id=288
- height=5, https://hog.grinvin.org/ViewGraphInfo.action?id=21059
- height=4, series reduced, https://hog.grinvin.org/ViewGraphInfo.action?id=25131
- height=6, series reduced, https://hog.grinvin.org/ViewGraphInfo.action?id=21048
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
Copyright 2015, 2016, 2017, 2018, 2019 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/.