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

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

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

By construction, the tree is labelled in pre-order since a vertex xx1000 has below it all xx1yyy.

Order

Option order => k 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 inclusive. 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) through (3,3).

A top-down definition is order k tree as two copies of k-1, one at the root and the other a child of that root. In the N=8 order=3 example above, 0-3 is an order=2 and 4-7 is another order=2, with 4 starting as a child of the root 0.

A bottom-up definition is order k tree as order k-1 with a new leaf vertex added to each existing vertex. The vertices of k-1 with extra low 0-bit become the even vertices of k. An extra low 1-bit is the new leaves.

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
graph_maker => subr(key=>value) constructor, default Graph->new

Other parameters are passed to the constructor, either graph_maker or 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, https://arxiv.org/abs/0910.4432

Order k is

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

The Wiener index is total distance between pairs of vertices, so the mean distance is, with binomial to choose 2 of 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 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

Balanced Binary

An ordered tree can be coded as pre-order balanced binary by writing at each vertex

1,  balanced binaries of children,  0

The bottom-up definition above is a new leaf as new first child of each vertex. That means the initial 1 becomes 110, so starting 10 for single vertex get repeated substitutions

10, 1100, 11011000, ...   (A210995)

The top-down definition above is a copy of the tree as new last child, so one copy at *2 and one at *2^2^k, giving

k-1:   1, tree k-1, 0
k:     1, tree k-1, 1, tree k-1, 0, 0

b(k) = (2^(2^k)+2) * b(k-1), starting b(0)=2
     = 2*prod(i=1,k, 2^(2^i)+2)
     = 2, 12, 216, 55728, 3652301664, ...  (A092124)

The tree is already labelled in pre-order so balanced binary follows from the parent rule. The balanced binary coding is 1 at a vertex and later 0 when pre-order skips up past it. A vertex with L many low 1-bits skips up past L many (including itself).

vertex n:  1, 0 x L     where L=CountLowOnes(n)

The last L goes up only to the depth of the next vertex. The balance can be completed by extending to total length 2N for N vertices. The tree continued infinitely is

1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, ...   (A079559)
^  ^     ^  ^        ^  ^     ^  ^
0  1     2  3        4  5     6  7

Independence and Domination

From the bottom-up definition above, a tree of even N has a perfect matching, being each odd n which is a leaf and its even attachment. An odd N has a near-perfect matching (one vertex left over).

Like all trees with a perfect matching, the independence number is then half the vertices, and when N odd can include the unpaired and work outwards from there by matched pairs so indnum = ceil(N/2).

The domination number is found by starting each leaf not in the dominating set and its attachment vertex in the set. This is all vertices so domnum = floor(N/2) except N=1 domination number 1.

HOUSE OF GRAPHS

House of Graphs entries for the trees here include

n=1 (order=0), https://hog.grinvin.org/ViewGraphInfo.action?id=1310 single vertex
n=2 (order=1), https://hog.grinvin.org/ViewGraphInfo.action?id=19655 path-2
n=4 (order=2), https://hog.grinvin.org/ViewGraphInfo.action?id=594 path-4
n=5 https://hog.grinvin.org/ViewGraphInfo.action?id=30 fork
n=6 https://hog.grinvin.org/ViewGraphInfo.action?id=496 E graph
n=7 https://hog.grinvin.org/ViewGraphInfo.action?id=714
n=8 (order=3), https://hog.grinvin.org/ViewGraphInfo.action?id=700
n=16 (order=4), https://hog.grinvin.org/ViewGraphInfo.action?id=28507
n=32 (order=5), https://hog.grinvin.org/ViewGraphInfo.action?id=21088
n=64 (order=6), https://hog.grinvin.org/ViewGraphInfo.action?id=33543
n=128 (order=6), https://hog.grinvin.org/ViewGraphInfo.action?id=33545

OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to the binomial tree include

A192021   Wiener index
A092124   pre-order balanced binary coding, decimal
A210995     binary
A079559     binary sequence of 0s and 1s

SEE ALSO

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

LICENSE

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