The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Graph-Maker-Other-19
River stage zero No dependents
1 ++
/ 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 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
             |
             7

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

If the graph is directed (the default) then edges are added as described in "Direction Type" above. Option undirected => 1 is 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)
                       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 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

My 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,  0

The 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  7

Independence 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 perfect

Like 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)   otherwise

HOUSE 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

    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 1s

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