view release on metacpan or  search on metacpan

devel/lib/Graph/Maker/SierpinskiTriangles.pm  view on Meta::CPAN

This vertex merging, and edges tripling with no merging, means

    NumVertices(N) = 3*NumVertices(N-1) - 3
                   = (3^N + 1) * 3/2
                   = 3, 6, 15, 42, 123, 366, ...   (A067771)

    NumEdges(N)    = 3^(N+1)
                   = 3, 9, 27, 81, 243, 729, ...   (A000244)

=cut

# GP-DEFINE  NumVertices(N) = {
# GP-DEFINE    N>=0 || error();
# GP-DEFINE    (3^N+1)*3/2;
# GP-DEFINE  }
# GP-Test  vector(6,N,N--; NumVertices(N)) == [3, 6, 15, 42, 123, 366]
# GP-Test  vector(100,N, NumVertices(N)) == \
# GP-Test  vector(100,N, 3*NumVertices(N-1) - 3)
#
# GP-DEFINE  NumEdges(N) = {
# GP-DEFINE    N>=0 || error();
# GP-DEFINE    3^(N+1);
# GP-DEFINE  }
# GP-Test  vector(6,N,N--; NumEdges(N)) == [3, 9, 27, 81, 243, 729]

=pod

An equivalent bottom-up definition is to take each vertical unit triangle
(horizontal base, peak upwards), insert a new vertex into each edge, and add
a cycle of edges around them, in the manner of N=0 becoming N=1.

                 *              *
      unit      / \            / \       new vertices "@"
    triangle   /   \    =>    @---@      subdividing edges,
              /     \        / \ / \     new cycle around them
             *-------*      *---@---*

The number of such unit triangles is 3^N just by the replications (top-down
or bottom-up).

=cut

# GP-DEFINE  NumUnit(N) = 3^N;
# GP-Test  vector(100,N, NumVertices(N)) == \
# GP-Test  vector(100,N, NumVertices(N-1) + 3*NumUnit(N-1))

# GP-Test  vector(100,N, NumEdges(N)) == \
# GP-Test  vector(100,N, 3*NumEdges(N-1))

=pod

There are various enclosed regions other than such upwards unit triangles.
Total number of interior regions follows from the top-down replications by 3
copies and a new middle,

    NumRegions(N) = 3*NumRegions(N) + 1
                  = (3^(N+1) - 1)/2
                  = 1, 4, 13, 40, 121, 364, ...       (A003462)

The graph is planar by its construction, so the combination of vertices,
edges and interior regions satisfy Euler's formula

    NumVertices(N) + NumRegions(N) = NumEdges(N) + 1

=cut

# GP-DEFINE  NumRegions(N) = {
# GP-DEFINE    N>=0 || error();
# GP-DEFINE    (3^(N+1) - 1)/2;
# GP-DEFINE  }
# GP-Test  NumRegions(0) == 1
# GP-Test  NumRegions(1) == 4
# GP-Test  vector(6,N,N--; NumRegions(N)) == [1, 4, 13, 40, 121, 364]
# GP-Test  vector(100,N, NumVertices(N) + NumRegions(N)) == \
# GP-Test  vector(100,N, NumEdges(N) + 1)

=pod

The towers of Hanoi state graph (L<Graph::Maker::Hanoi>) is related to the
graph here by taking the inside of each upward unit triangle as a vertex,
and put edges between those unit triangles which touch at corners.

=head1 FUNCTIONS

=over

=item C<$graph = Graph::Maker-E<gt>new('Sierpinski_triangles', key =E<gt> value, ...)>

The key/value parameters are

    N           => integer
    graph_maker => subr(key=>value) constructor, default Graph->new

Other parameters are passed to the constructor, either C<graph_maker> or
C<Graph-E<gt>new()>.

If the graph is directed (the default) then edges are added both ways
between vertices.  Option C<undirected =E<gt> 1> creates an undirected graph
and for it there is a single edge between vertices.

=back

=head1 FORMULAS

=head2 Wiener Index

=head1 HOUSE OF GRAPHS

House of Graphs entries for the folded hypercubes here include

=over

L<https://hog.grinvin.org/ViewGraphInfo.action?id=1310> (etc)

=back

     1374   N=0   3-cycle
    36261   N=1

=head1 OEIS