Graph::Maker::ExcessConfigurations - create ExcessConfigurations graph
use Graph::Maker::ExcessConfigurations; $graph = Graph::Maker->new ('excess_configurations', N => 7);
Graph::Maker::ExcessConfigurations creates Graph.pm graphs of the evolution of multigraph excess "configuration"s in the manner of
Graph::Maker::ExcessConfigurations
Graph.pm
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 graph_maker coderef or Graph->new().
graph_maker
Graph->new()
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,
https://hog.grinvin.org/ViewGraphInfo.action?id=1310 etc
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
http://oeis.org/A000070 (etc)
A000070 num vertices, cumulative num partitions A029859 num edges, partitions choose 0,1,2 terms A000041 num successorless, partitions of N
Graph::Maker
http://user42.tuxfamily.org/graph-maker-other/index.html
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/.
To install Graph::Maker::Other, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Graph::Maker::Other
CPAN shell
perl -MCPAN -e shell install Graph::Maker::Other
For more information on module installation, please visit the detailed CPAN module installation guide.