/ 
Graph-Maker-Other-3
River stage zero No dependents
/ Graph::Maker::BinomialTree

NAME

Graph::Maker::BinomialTree - create binomial tree graph

SYNOPSIS

use Graph::Maker::BinomialTree;
$graph = Graph::Maker->new ('binomial_tree', N => 32);

DESCRIPTION

Graph::Maker::BinomialTree creates a Graph.pm graph of a Binomial tree with N vertices. Vertices are numbered from 0 at the root through to N-1.

The parent of a given vertex is its number n with the lowest 1-bit cleared to 0. Conversely the children of a vertex n=xx1000 are xx1001, xx1010, xx1100, so each trailing 0 bit changed to a 1 provided that does not exceed the maximum N-1. At the root the children are single bit powers-of-2 up to the high bit of the maximum N-1.

  __0___
 /  |   \        N => 8
1   2    4
    |   / \
    3  5   6
           |
           7

Order

The order parameter is another way to specify the number of vertices. A tree of order=k has N=2^k many vertices. Such a tree has depth levels 0 to k. The number of vertices at depth d is the binomial coefficient binom(k,d), hence the name of the tree.

The N=8 example above is order=3 and the number of vertices at each depth is 1,3,3,1 which are binomials (3,0) to (3,3).

As from the bit-definition above, an order k tree is two copies of k-1. One of them is at the root and the other is a child of that root. In the N=8 order=3 example above 0-3 is an order=2 and 4-7 is another, starting as a child of the root 0.

Binomial tree order=5 appears on the cover of Knuth "The Art of Computer Programming", volume 1, "Fundamental Algorithms", second edition.

FUNCTIONS

$graph = Graph::Maker->new('binomial_tree', key => value, ...)

The key/value parameters are

N          =>  integer
order      =>  integer

Other parameters are passed to Graph->new().

N is the number of vertices, 0 to N-1. Or instead order gives N=2^order many vertices.

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

The Wiener index of the binomial 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

For order k it is

            (k-1)*4^k + 2^k
Wiener(k) = ---------------  = 0, 1, 10, 68, 392, ...  (A192021)
                   2

The Weiner index is total distance between pairs of vertices, so the mean distance is, with binomial to choose 2 among the 2^k vertices,

                  Wiener(k)                k
MeanDist(k) = ---------------- =  k-1 + -------      for k>=1
              binomial(2^k, 2)          2^k - 1

The tree for k>=1 has diameter 2*k-1 between ends of the deepest and second-deepest subtrees of the root. The mean distance as a fraction of the diameter is then

MeanDist(k)    1       1              1
----------- = --- - ------- + -------------------
diameter(k)    2    4*k - 4   (2 - 1/k) * (2^k-1)

            -> 1/2  as k->infinity

OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to these graphs include

A192021   Wiener index

SEE ALSO

Graph::Maker, Graph::Maker::BalancedTree

LICENSE

Copyright 2015, 2016 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/.