Graph::Maker::BinomialTree - create binomial tree graph
use Graph::Maker::BinomialTree; $graph = Graph::Maker->new ('binomial_tree', N => 32);
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.
Graph::Maker::BinomialTree
Graph.pm
__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.
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.
order => k
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.
$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().
graph_maker
Graph->new()
N is the number of vertices, 0 to N-1. Or instead order gives N=2^order many vertices.
N
order
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.
Graph::Maker::BalancedTree
undirected => 1
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
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
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 entries for the trees here include
Entries in Sloane's Online Encyclopedia of Integer Sequences related to the binomial tree include
http://oeis.org/A192021 (etc)
A192021 Wiener index A092124 pre-order balanced binary coding, decimal A210995 binary A079559 binary sequence of 0s and 1s
Graph::Maker, Graph::Maker::BalancedTree, Graph::Maker::BinaryBeanstalk
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/.
To install Graph::Maker::Other, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Graph::Maker::Other
CPAN shell
perl -MCPAN -e shell install Graph::Maker::Other
For more information on module installation, please visit the detailed CPAN module installation guide.