Learn R Programming

Claddis (version 0.7.0)

permute_connected_graphs: Permute all connected graphs

Description

Given a vertex count, permutes all connected graphs.

Usage

permute_connected_graphs(n_vertices)

Value

A list of graphs (matrices of dummy labelled edges).

Arguments

n_vertices

The number of vertices to connect.

Author

Graeme T. Lloyd graemetlloyd@gmail.com

Details

For the two vertex case there is only a single connected graph:

A---B

(The labels A and B here simply indicate the two vertices and are not a true labelling.)

If we add a third vertex, there are two connected graphs:

A---B
 \ /
  C

And:

A---B---C

This function permutes all such connected graphs for a given vertex count.

Note that the output is in the form of a matrix of edges. For the three vertex case above these would be:

     [,1] [,2]
[1,] "A"  "B"
[2,] "A"  "C"
[3,] "B"  "C"

And:

     [,1] [,2]
[1,] "A"  "B"
[2,] "B"  "C"

Again, it is important to note that the labels A, B, and C here are purely "dummy" labels and should not be considered a graph labelling. To use the second graph as an example there are multiple labellings of this graph:

A---B---C

And:

B---A---C

And:

A---C---B

However, these are all isomorphisms of the same unlabelled graph. Only the unique graphs themselves are returned here.

Examples

Run this code

# Generate all connected graphs of four vertices:
permute_connected_graphs(n_vertices = 4)

Run the code above in your browser using DataLab