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

NAME

Graph::Maker::PartitionSum - create partition sum graphs

SYNOPSIS

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

DESCRIPTION

Graph::Maker::PartitionSum creates Graph.pm graphs of partitions stepped by summing terms.

                      1,1,3 --> 1,4
                      ^    \   ^   \
                     /      \ /     v         N => 5
1,1,1,1,1 --> 1,1,1,2        X       5
                     \      / \     ^
                      v    /   v   /
                      1,2,2 --> 2,3

Each vertex is a partition of integer N, meaning a set of integers which sum to N. Vertex names are the terms in ascending order, separated by commas.

Edges are by summing two terms in the partition to reach another. The number of edges is all the ways to choose two terms.

num vertices = partitions of N
             = 1, 1, 2, 3, 5, 7, 11, 15, ... (A000041)

num edges    = choose 2 terms in partitions
             = 0, 0, 1, 2, 5, 9, 17, 28, ... (A000097)

N=0 is reckoned as a single vertex which is the empty partition. N=1 is single vertex 1.

Each sum reduces the number of terms by 1, so the steps are a partial ordering of the partitions.

Steps can also be thought of the other direction, taking a partition term and split it into two. (The current implementation forms edges that way.)

FUNCTIONS

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

The key/value parameters are

N           =>  integer, to partition
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 added just in the sum direction. Option undirected => 1 creates an undirected graph.

HOUSE OF GRAPHS

House of Graphs entries for the graphs here include

N=0,1, https://hog.grinvin.org/ViewGraphInfo.action?id=1310 singleton
N=2, https://hog.grinvin.org/ViewGraphInfo.action?id=19655 path-2
N=3, https://hog.grinvin.org/ViewGraphInfo.action?id=32234 path-3
N=4, https://hog.grinvin.org/ViewGraphInfo.action?id=206 4-cycle and leaf
N=5, https://hog.grinvin.org/ViewGraphInfo.action?id=864

OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to these graphs include

http://oeis.org/A000041 (etc)

A000041    num vertices = num partitions
A000097    num edges, partitions choose two terms

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