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

# 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)*(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

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

# 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``````