view release on metacpan or  search on metacpan

lib/Graph/Maker/FibonacciTree.pm  view on Meta::CPAN

=over

=item C<$graph = Graph::Maker-E<gt>new('fibonacci_tree', key =E<gt> 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 C<graph_maker> or
C<Graph-E<gt>new()>.

C<height> is how many rows of nodes.  So C<height =E<gt> 1> is a single row,
being the root node only.

If the graph is directed (the default) then edges are added as described in
L</Direction Type> above.  Option C<undirected =E<gt> 1> is an undirected
graph and for it there is always a single edge between parent and child.

=back

=head1 FORMULAS

=head2 Wiener Index - Series and Leaf Reduced

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

=over

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

=back

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)

=cut

# GP-DEFINE  DTb(k) = 1/5*(k-3)*F(k+3) + 2/5*(k-2)*F(k+2) + 2;
# GP-Test  my(v=[0,0,1,4,11,26,56,114,223,424,789,1444,2608,4660,8253,14508]); vector(#v,k,k--; DTb(k))==v

# Iyer and Reddy preprint
#      WTb(k-1) + WTb(k-2)  + F(k+1) * DTb(k-2)     <-- same
#                           + (F(k)-1) * DTb(k-1)   \ different
#          + F(k+1) * (F(k) - 1)                    /

=pod

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

=cut

# GP-DEFINE  WTb_by_recurrence(k) = {
# GP-DEFINE    if(k==0,0, k==1,0,
# GP-DEFINE       WTb(k-1) + WTb(k-2) + F(k+1)*DTb(k-2) + F(k)*DTb(k-1)
# GP-DEFINE       + 2*F(k+1)*F(k) - F(k+2) );
# GP-DEFINE  }

=pod

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)

=cut

# GP-DEFINE  WTb(k) = 1/10 * ( (2*k+13) * (F(k+2) + 1)*(F(k+2) + F(k+4)) \
# GP-DEFINE                    - F(k+2)*(29*F(k+4) - 10)  - 9*F(k+4) )
# GP-Test  my(v=[0,0,1,10,50,214,802,2802,9275,29580,91668,277924,828092,2433140]); vector(#v,k,k--; WTb(k))==v
# GP-Test  vector(100,k,k--; WTb_by_recurrence(k))==vector(100,k,k--; WTb(k))

=pod

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) -E<gt> phi^n, where phi=(1+sqrt5)/2, the X<Golden ratio>Golden
ratio.

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

                = 0.723606...   (A242671)

=cut

# GP-DEFINE  sqrt5 = quadgen(20);
# GP-Test  sqrt5^2 == 5
# GP-DEFINE  phi = (1+sqrt5)/2;
# GP-DEFINE  MeanDist_limit = (1 + phi^2)/5;
# GP-Test  MeanDist_limit == (2 + phi)/5