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 the binomial tree of N vertices. Vertices are numbered from 0 at the root through to N-1.
0---
| \ \ N => 8
1 2 4
| | \
3 5 6
|
7The parent of vertex v is v with its lowest 1-bit cleared to 0. Conversely, the children of a vertex v are to take its low 0-bits and change any one to a 1-bit, provided the result is < N. For example v=1000 has children 1001, 1010, 1100. At the root, the children are single bit powers 2^j up to the high bit of the maximum vertex N-1.
By construction, the tree is labelled in pre-order since a vertex ...1000 has below it all ...1xxx.
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 the end-most child of that root.
k-1---
|..\ \ order k as two order k-1
k-1
|..\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 childless vertex added as a new first child of each existing vertex. The vertices of k-1 with extra low 0-bit are the even vertices of k. The vertices of k-1 with extra low 1-bit are the new childless vertices.
Binomial tree order=5 appears as the frontispiece (and the paperback cover) in Knuth "The Art of Computer Programming", volume 1, "Fundamental Algorithms", second and subsequent editions. Vertex labels there are binary dots coding each v.
Direction Type
The default is a directed graph with edges both ways between vertices (like most Graph::Maker directed graphs). This is parameter direction_type => 'both'.
Optional direction_type => 'bigger' or 'child' gives edges directed to the bigger vertex number, so from smaller to bigger. This means parent down to child.
Option direction_type => 'smaller' or 'parent' gives edges directed to the smaller vertex number, so from bigger to smaller. This means child up to parent.
Coordinates
There's a secret undocumented coordinates option which sets vertex attributes for a south-west flow similar to the N=>8 shown above. Don't rely on this yet as it might change or be removed.
The coordinate pattern is vertex v at
x = floor(v/2) y = count1bits(v)The floor gives two vertices as a vertical pair (eg. 4 and 5). Spreading x by this much suffices for no vertex overlapping. Many other layouts are be possible of course, though it's attractive to have the two halves of the "top down" definition above in the same layout.
FUNCTIONS
$graph = Graph::Maker->new('binomial_tree', key => value, ...)-
The key/value parameters are
N => integer >=0 order => integer >=0 direction_type => string, "both" (default), "bigger", "smaller", "parent, "child" graph_maker => subr(key=>value) constructor, default Graph->newOther parameters are passed to the constructor, either
graph_makerorGraph->new().Nis the number of vertices (0 to N-1). Or insteadordergives N=2^order many vertices.If the graph is directed (the default) then edges are added as described in "Direction Type" above. Option
undirected => 1is an undirected graph and for it there is always a single edge between parent and child.
FORMULAS
Wiener Index
The Wiener index of binomial tree order k 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
(k-1)*4^k + 2^k
Wiener(k) = --------------- = 0, 1, 10, 68, 392, ... (A192021)
2The 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 - 1The 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->infinityMy vpar includes an examples/binomial-tree-W.gp with Wiener index formulas for any N vertices
Balanced Binary
An ordered tree can be coded as pre-order balanced binary by writing at each vertex
1, balanced binaries of children, 0The bottom-up definition above is a new leaf as new first child of each vertex. That means the initial 1 becomes 110. Starting from 10 for single vertex, repeated substitutions are
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 L many (including itself).
vertex n: 1, 0 x L where L=CountLowOnes(n)The last L in an arbitrary N vertices goes up only to the depth of the next vertex. The balanced binary 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 7Independence and Domination
From the bottom-up definition above, a binomial tree of even N vertices has a perfect matching, being each odd v which is a leaf and its even parent. An odd N has a near-perfect matching (one vertex left over).
matchnum(N) = floor(N/2) perfect and near perfectLike all trees with a perfect matching, the independence number is then half the vertices, and when N odd it can include the unpaired and work outwards from there by matched pairs so
indnum(N) = 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 = / 1 if N=1
\ floor(N/2) otherwiseHOUSE OF GRAPHS
House of Graphs entries for the trees here include
1310 N=1 (order=0), single vertex
19655 N=2 (order=1), path-2
32234 N=3, path-3
594 N=4 (order=2), path-4
30 N=5, fork
496 N=6, E graph
714 N=7
700 N=8 (order=3)
34546, 34548, 34550, 34552 N=9 to N=12
34554, 34556, 34558 N=13 to N=15
28507 N=16 (order=4)
21088 N=32 (order=5)
33543 N=64 (order=6)
33545 N=128 (order=7)OEIS
Entries in Sloane's Online Encyclopedia of Integer Sequences related to the binomial tree include
http://oeis.org/A192021 (etc)
by N vertices
A129760 parent vertex number, clear lowest 1-bit
A000523 height, floor(log2(N))
A090996 number of vertices at height, num high 1-bits
by order
A192021 Wiener index
A092124 pre-order balanced binary coding, decimal
A210995 binary
infinite
A079559 balanced binary sequence 0s and 1sSEE ALSO
Graph::Maker, Graph::Maker::BalancedTree, Graph::Maker::BinaryBeanstalk
HOME PAGE
http://user42.tuxfamily.org/graph-maker-other/index.html
LICENSE
Copyright 2015, 2016, 2017, 2018, 2019, 2020, 2021 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/.