Graph::Maker::ExcessConfigurations - create ExcessConfigurations graph
use Graph::Maker::ExcessConfigurations; $graph = Graph::Maker->new ('excess_configurations', N => 7);
Graph.pm graphs of the evolution of multigraph excess "configuration"s in the manner of
Svante Janson, Donald E. Knuth, Tomasz Luczak, Boris Pittel, "Birth of the Giant Component", Random Structures and Algorithms, volume 4, 1993, pages 233-358. https://arxiv.org/abs/math/9310236, https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.3240040303
/---> 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)
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.
$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
If the graph is directed (the default) then edges are in the add-an-edge direction between configurations.
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
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
Copyright 2018, 2019 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/.