view release on metacpan or  search on metacpan

lib/Graph/Maker/BinomialTree.pm  view on Meta::CPAN

#     /  |
#    1   2
#        |
#        3
#
# GP-DEFINE  Wiener(k) = ( (k-1)*4^k + 2^k ) /2;
# GP-Test  Wiener(0) == 0
# GP-Test  Wiener(1) == 1    \\ 2 vertices, path=1
# GP-Test  Wiener(2) == 10
# GP-Test  Wiener(3) == 68
# GP-Test  Wiener(4) == 392

=pod

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

=cut

# GP-DEFINE  num_vertices(k) = 2^k;
# GP-Test  num_vertices(0) == 1
# GP-Test  num_vertices(2) == 4
#
# GP-DEFINE  MeanDist(k) = Wiener(k) / binomial(num_vertices(k),2);
# GP-Test  vector(100,k, MeanDist(k)) == \
# GP-Test  vector(100,k, k-1 + k / (2^k-1))  /* k>=1 */

=pod

The tree for kE<gt>=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

=cut

# GP-DEFINE  diameter(k) = 2*k-1;
# GP-Test  diameter(2) == 3
# GP-Test  diameter(3) == 5
#
# GP-DEFINE  MeanDist_over_diameter(k) = MeanDist(k) / diameter(k);
# GP-DEFINE  MeanDist_over_diameter_simplified(k) = \
# GP-DEFINE    1/2 - 1/(4*k - 2) + 1 /( (2 - 1/k) * (2^k-1) );
# GP-Test  vector(100,k, MeanDist_over_diameter_simplified(k)) == \
# GP-Test  vector(100,k, MeanDist_over_diameter(k))
# GP-Test  my(k=100000); abs(MeanDist_over_diameter(k) - 1/2) < 1e-5
# binomial_mean -> 1/2

=pod

My C<vpar> includes an F<examples/binomial-tree-W.gp> with Wiener index
formulas for any N vertices

=over

L<http://user42.tuxfamily.org/pari-vpar/index.html>

=back

=head2 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)

=cut

# GP-DEFINE  b(k) = if(k==0,2, (2^(2^k)+2) * b(k-1));
# vector(10,k, vpar_to_balanced_binary(vpar_make_binomial_tree(2^k))) == \
# vector(10,k, b(k))
# GP-Test  vector(9,k, b(k)) == \
# GP-Test  vector(9,k, (2^(2^k)+2) * b(k-1))  /* recurrence */
# GP-Test  vector(10,k,k--; b(k)) == \
# GP-Test  vector(10,k,k--; 2*prod(i=1,k, 2^(2^i)+2))  /* product */
# GP-Test  vector(5,k,k--; b(k)) == \
# GP-Test    [2, 12, 216, 55728, 3652301664]  /* samples */

=pod

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

=head2 Independence and Domination