/ 
Graph-Maker-Other-2
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.

OEIS

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

A192021   Wiener index, being 1/2*((k-1)*4^k + 2^k)

SEE ALSO

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

K. Viswanathan Iyer and K. R. Udaya Kumar Reddy, "Wiener index of Binomial Trees and Fibonacci Trees", Int'l J Math Engg with Comp, 2009. arxiv:0910.4432

LICENSE

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