/ 
Graph-Maker-Other-19
River stage zero No dependents
/ Graph::Maker::ExcessConfigurations

NAME

Graph::Maker::ExcessConfigurations - create ExcessConfigurations graph

SYNOPSIS

use Graph::Maker::ExcessConfigurations;
$graph = Graph::Maker->new ('excess_configurations', N => 7);

DESCRIPTION

Graph::Maker::ExcessConfigurations creates Graph.pm graphs of the evolution of multigraph excess "configuration"s in the manner of

        /---> 0,1 --->  1,1          ( cross connections
0 ---> 1           X                       0,1 and 2
        \--->  2  --->  0,0,1           -> 1,1 and 0,0,1 )
                \
                 ---->  3

The "excess" of a connected component of a multigraph is

excess = number of edges - number of vertices
       = -1 for tree (acyclic), 0 for unicyclic, ...

Janson et al take the configuration of a multigraph to be the number of components of excess r = 1, 2, 3, etc.

[count r=1, count r=2, ...]      vertex name such as "1,0,2"

In the ExcessConfigurations graph, each vertex is such a configuration. An edge is to a new configuration obtained by adding one edge to the multigraph. Such an edge can increase the excess of an existing component, including raising an r=0 to a new r=1. Or it can join two components r,s together for new combined excess r+s+1. r=0 components doesn't appear in the configuration but are taken to be in unlimited supply.

Janson et al note this is a partial ordering of configurations since total excess increases by 1 each time. Total excess is total of the r>=0 components, so not including tree components.

total excess = r1 + 2*r2 + 3*r3 + ...

Parameter N here is how many evolution steps, so configurations of total excess 0 through N inclusive, and the edges between them. Total excess is sum of component excesses, so those component excesses are a partition of the total. The number of vertices is thus sum over t=total,

num vertices = sum(t=0,N, NumPartitions(t))
             = 1, 2, 4, 7, 12, 19, ...  (A000070)

Cycles

As a note on terminology, excess r=0 described above is a unicyclic component, meaning it has one cycle and possible acyclic branches hanging off.

Janson et al call r=1 bi-cyclic (and r=2 tri-cyclic, etc). The cases for r=1 are, up to paths or vertex insertions (so "reduced multigraphs"),

  _   _      __      __          __
 / \ / \    |  |    |  |        /  \         excess r=1
|   A   |   |  A----B  |       A----B      (Janson et al
 \_/ \_/    |__|    |__|        \__/       equation 9.15)      

     separate loops          three paths

The separate loops are clearly 2 cycles. The three paths case would be 3 cycles if all combinations were allowed. Excess r=1 as bi-cyclic is understood as successive cycles using at least one previously unused edge, the way edges are added to the multigraph in forming a cycle.

FUNCTIONS

$graph = Graph::Maker->new('excess_configurations', key => value, ...)

The key/value parameters are

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

Other parameters are passed to the constructor, either the graph_maker coderef or Graph->new().

If the graph is directed (the default) then edges are in the add-an-edge direction between configurations.

HOUSE OF GRAPHS

House of Graphs entries for the trees here include,

1310    N=0, singleton
19655   N=1, path-2
500     N=2, star-4 claw
33585   N=3
33587   N=4

OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to this tree include

A000070    num vertices, cumulative num partitions
A029859    num edges, partitions choose 0,1,2 terms
A000041    num successorless, partitions of N

SEE ALSO

Graph::Maker

HOME PAGE

http://user42.tuxfamily.org/graph-maker-other/index.html

LICENSE

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