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
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, 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
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.
order
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).
A top-down definition is order k tree is 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, 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 an extra low 0-bit become the evens 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
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. arxiv:0910.4432
For order k it 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 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
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).
The independence number is found by starting with each leaf in an independent set and its attachment vertex not. Per the bottom-up definition this is all vertices. If N odd then the unpaired existing even vertex can be included too, for independence number ceil(N/2).
The domination number similarly, by starting each leaf not in the dominating set and its attachment vertex in the set. Again this is all vertices so domination number 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 these graphs include
http://oeis.org/A192021 (etc)
A192021 Wiener index
Graph::Maker, Graph::Maker::BalancedTree
Copyright 2015, 2016, 2017 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.