GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/NonIsomorphicGraphs

GraphTheory

  

NonIsomorphicGraphs

  

isomorphic graph classes by vertices and edges

 

Calling Sequence

Parameters

Description

Examples

Calling Sequence

NonIsomorphicGraphs(v)

NonIsomorphicGraphs(v,e)

NonIsomorphicGraphs(v,options)

NonIsomorphicGraphs(v,e,options)

Parameters

v

-

positive integer specifying the number of vertices in the graphs

e

-

nonnegative integer or positive range of nonnegative integers specifying the number of edges in the graphs

options

-

Options used to control the behavior of the command

Description

• 

The NonIsomorphicGraphs command allows for operations to be performed for one member of each isomorphic class of undirected, unweighted graphs for a fixed number of vertices having a specified number of edges or range of edges.  Use the options to return a count on the number of isomorphic classes or a representative graph from each class.

• 

As quick examples, one can obtain a count of the number of isomorphic classes of 4-vertex graphs:

with(GraphTheory):

NonIsomorphicGraphs(4,output=count);

11

(1)

or get further detail by counting the isomorphic classes by edges:

[NonIsomorphicGraphs(4,output=countbyedges)];

0=1,1=1,2=2,3=3,4=2,5=1,6=1

(2)

and further restrict to graphs with 2-4 edges:

[NonIsomorphicGraphs(4,2..4,output=countbyedges)];

2=2,3=3,4=2

(3)

or just obtain a count of the number of isomorphic classes for graphs with 4 vertices and 3 edges:

NonIsomorphicGraphs(4,3,output=count);

3

(4)
• 

One can obtain representations for a member of each distinct isomorphic class of graphs, restricting based on built-in criteria and/or procedure-defined criteria, with output either as a (possibly very large) sequence of graph representations, or an iterator that can be used to output the sequence one graph at a time.

The following options control the behavior of NonIsomorphicGraphs.

• 

output = count, countbyedges, graphs, or iterator

  

For output=count, the number of unique isomorphic graphs matching all criteria is output.

  

For output=countbyedges, a sequence of the form e1=c1, e2=c2, ... is returned, where ei is the number of edges, and ci is the graph count for those edges.

  

For output=graphs, a sequence of representations for all graphs is returned.

  

For output=iterator a module is returned. When called as a procedure, it outputs the next graph in the sequence. The iterator output is similar to the graphs output, but the complete sequence of graphs is never actually formed, which makes this most useful when dealing with a large number of graphs.

  

The iterator will start with the first graph that would be output for the graphs output form, then the next in the sequence with each call, and after the last graph has been output, the return will be FAIL, which indicates that the procedure has already returned all graphs. Calling the procedure with the optional argument reset will restart the iteration from the beginning, as demonstrated in the examples.

• 

outputform = graph, adjacency, or bits

  

The outputform option specifies the form used to represent output graphs. This option is only valid for output = graphs or output = iterator. When outputform=bits (the default) the graph is output as an integer such that the adjacency matrix for the graph can be constructed by the bits set in the output integer. Specifically the integer is the one formed by examining the upper triangular portion of the symmetric adjacency Matrix, excluding the diagonal, and building up, from least to most significant bit order, the entries, moving left to right, then down, by using a 1 digit if the edge is present, and a 0 digit otherwise. There is an example that constructs the adjacency matrix from the bits representation in the examples section below. When outputform=adjacency, the adjacency Matrix of the graph is constructed as a v x v integer[1] Matrix. When outputform=graph, Graph structures are constructed.

• 

restrictto = none (default), connected, regular, regular[n]

  

The restrictto option specifies that the graphs either returned or iterated over should satisfy the specified criteria, otherwise they should be skipped. Specifically, when restrictto=connected is used, only connected graphs are counted or returned, when restrictto=regular, only regular graphs are counted or returned, and when restrictto=regular[n], only n-regular graphs are counted or returned.

• 

select=procedure

  

This allows specification of a procedure to control whether a graph should be included in the output. This provides similar functionality as restrictto but allows for implementation of more complex criteria. Note that this option can be used in combination with restrictto, and only the graphs that satisfy the restrictto criteria will be passed to the select procedure.

• 

selectform = graph, adjacency, or bits

  

This specifies the form used for a graph when it is being passed to the select procedure. The forms are identical to those for outputform, but note that adjacency and bits are the most efficient forms, while graph is only reasonable for a relatively small number of comparison operations (1000 or less), as it needs to form a Graph for every comparison. Note also that when selectform=adjacency the same read-only Matrix is internally used to pass the data for every call to reduce overhead. This is not possible with a Graph structure.

Examples

withGraphTheory:

Count the number of isomorphically unique graphs and connected graphs on 8 vertices.

NonIsomorphicGraphs8,NonIsomorphicGraphs8,restrictto=connected

12346,11117

(5)

Output all 2-regular graphs on 8 vertices in bits form

NonIsomorphicGraphs8,output=graphs,restrictto=regular2

210256131,213917955,210501763

(6)

Manually construct the adjacency Matrix for the first output

bitVectorrowBits:-Split210256131,bits=8812:

MMatrix8,8,shape=symmetric,datatype=integer1:

M1,2..8bit1..7:M2,3..8bit8..13:M3,4..8bit14..18:

M4,5..8bit19..22:M5,6..8bit23..25:M6,7..8bit26..27:

M7,8..8bit28..28:

M

0110000010010000100010000100010000100010000100010000100100000110

(7)

Output all 2-regular graphs on 8 vertices in adjacency Matrix form (and note that the first answer is identical to the one above that we obtained from bit form).

NonIsomorphicGraphs8,output=graphs,outputform=adjacency,restrictto=regular2

0110000010010000100010000100010000100010000100010000100100000110,0110000010010000100100000110000000000110000010010000100100000110,0110000010100000110000000000110000010010000100010000100100000110

(8)

Using iterator form for the same problem

prcNonIsomorphicGraphs8,output=iterator,outputform=adjacency,restrictto=regular2

prc:=modulelocalcdata,atend,ModuleApply;end module

(9)

prc,prc,prc

0110000010010000100010000100010000100010000100010000100100000110,0110000010010000100100000110000000000110000010010000100100000110,0110000010100000110000000000110000010010000100010000100100000110

(10)

At the end, returns FAIL

prc

FAIL

(11)

Restart the iteration

prcreset

prc

0110000010010000100010000100010000100010000100010000100100000110

(12)

See Also

GraphTheory

GraphTheory[Graph]