Any enumerated or indexed set S may be given as the vertex-set of a graph. The graph constructor will take a copy V of S, convert V into an indexed set if necessary, and flag its type as GrphVertSet. A graph may be specifically created as a sparse graph. If no indication is given then the graph is always created with the dense representation, that is, as an adjacency matrix.
Memory allocation for any elementary object (that is, accessed via a single pointer) cannot exceed 232 bytes. For this reason there is a bound on the graph order. This bound is dependent upon the (internal) graph representation chosen at creation: the dense representation (as a packed adjacency matrix), or the sparse representation (as an adjacency list). The former is quadratic in the number of vertices of the graph, the latter is linear in the number of the edges. Thus a large graph with a low edge density will require less memory space than the same graph with a dense representation.
The bounds on the graph order n are as follows:
- for the dense representation, n ≤65535,
- for the sparse representation, n ≤134217722.
These bounds are maximal, that is, they assume --- for the sparse representation --- that the number of edges is zero. To help users determine the likely size of the graph they want to construct, we provide the following function.
IsDigraph: Bool Default: false
SparseRep: Bool Default: false
Computes the memory requirement in bytes of a graph of order n and size m. By default it is assumed that the graph is undirected and has a dense representation.
One may verify that the dense representation cannot be used for a value of n (graph order) larger than 65535.
> n := 65536; > m := 0; > assert GraphSizeInBytes(n, m) gt 2^32;It is possible to construct such a graph with a sparse representation:
> GraphSizeInBytes(n, m : SparseRep := true); 2097580However, assuming that the graph of order n = 65535 has a size of m = 33538101 we see that such a graph cannot be constructed as its total memory requirement is again larger than 232:
> m := 33538101; > assert GraphSizeInBytes(n, m : SparseRep := true) gt 2^32;
SparseRep: Bool Default: false
Construct the graph G with vertex-set V = {@ v1, v2, ..., vn @} (where vi = i for each i if the first form of the constructor is used, or the ith element of the enumerated or indexed set S otherwise), and edge-set E = { e1, e2, ..., eq }. This function returns three values: The graph G, the vertex-set V of G; and the edge-set E of G. If SparseRep is true then the resulting graph will have a sparse representation.The elements of E are specified by the list edges, where the items of edges may be objects of the following types:
In addition to these three basic ways of specifying the edges list, the items in edges may also be:
- (a)
- A pair { vi, vj } of vertices in V. The edge from vi to vj will be added to the edge-set for G.
- (b)
- A tuple of the form < vi, Ni > where Ni will be interpreted as a set of neighbours for the vertex vi. The elements of the sets Ni must be elements of V. If Ni = { u1, u2, ..., ur }, the edges { vi, u1 }, ..., { vi, ur } will be added to G.
- (c)
- A sequence [ N1, N2, ..., Nn ] of n sets, where Ni will be interpreted as a set of neighbours for the vertex vi. The edges { vi, ui }, 1 ≤i ≤n, ui ∈Ni, are added to G.
- (d)
- An edge e of a graph or digraph or multigraph or multidigraph or network of order n. If e is an edge from u to v in a directed graph H, then the undirected edge { u, v } will be added to G.
- (e)
- An edge-set E of a graph or digraph or multigraph or multidigraph or network of order n. Every edge e in E will be added to G.
- (f)
- A graph or a digraph or a multigraph or a multidigraph or a network H of order n. Every edge e in H's edge-set is added to G.
- (g)
- A n x n symmetric (0, 1)-matrix A. The matrix A will be interpreted as the adjacency matrix for a graph H on n vertices and the edges of H will be added will be added to G.
- (h)
- A set of
- (i)
- Pairs of the form { vi, vj } of vertices in V.
- (ii)
- Tuples of the form < vi, Ni > where Ni will be interpreted as a set of neighbours for the vertex vi.
- (iii)
- Edges of a graph or digraph or multigraph or multidigraph or network of order n.
- (iv)
- Graphs or digraphs or multigraphs or multidigraphs or networks of order n.
- (j)
- A sequence of
- (i)
- Tuples of the form < vi, Ni > where Ni will be interpreted as a set of neighbours for the vertex vi.
Let A be a n x m (0, 1) matrix having exactly two 1s in each column. Then a graph G of order n and size m having A as its incidence matrix will be constructed. The rows of A will correspond to the vertices of G while the columns will correspond to the edges.
> P := Graph< 10 | { 1, 2 }, { 1, 5 }, { 1, 6 }, { 2, 3 }, { 2, 7 },
> { 3, 4 }, { 3, 8 }, { 4, 5 }, { 4, 9 }, { 5, 10 },
> { 6, 8 }, { 6, 9 }, { 7, 9 }, { 7, 10 }, { 8, 10 } >;
We next construct the Petersen graph by listing the neighbours of each vertex:
> P := Graph< 10 | [ { 2, 5, 6 }, { 1, 3, 7 }, { 2, 4, 8 }, { 3, 5, 9 },
> { 1, 4, 10 }, { 1, 8, 9 }, { 2, 9, 10 }, { 3, 6, 10 },
> { 4, 6, 7 }, { 5, 7, 8 } ] >;
We repeat the above construction but now the graph is created as
a sparse graph:
> PS := Graph< 10 | [ { 2, 5, 6 }, { 1, 3, 7 }, { 2, 4, 8 }, { 3, 5, 9 },
> { 1, 4, 10 }, { 1, 8, 9 }, { 2, 9, 10 }, { 3, 6, 10 },
> { 4, 6, 7 }, { 5, 7, 8 } ] : SparseRep := true >;
> assert PS eq P;
Here is yet another way of constructing the sparse graph, from
the dense graph:
> PS := Graph< 10 | P : SparseRep := true >; > assert PS eq P;We finally construct the graph in terms of an adjacency matrix:
> M := MatrixRing( Integers(), 10 );
> P := Graph< 10 | M![ 0,1,0,0,1,1,0,0,0,0,
> 1,0,1,0,0,0,1,0,0,0,
> 0,1,0,1,0,0,0,1,0,0,
> 0,0,1,0,1,0,0,0,1,0,
> 1,0,0,1,0,0,0,0,0,1,
> 1,0,0,0,0,0,0,1,1,0,
> 0,1,0,0,0,0,0,0,1,1,
> 0,0,1,0,0,1,0,0,0,1,
> 0,0,0,1,0,1,1,0,0,0,
> 0,0,0,0,1,0,1,1,0,0] >;
> P;
Graph
Vertex Neighbours
1 2 5 6 ;
2 1 3 7 ;
3 2 4 8 ;
4 3 5 9 ;
5 1 4 10 ;
6 1 8 9 ;
7 2 9 10 ;
8 3 6 10 ;
9 4 6 7 ;
10 5 7 8 ;
> G := PermutationGroup< 30 |
> (1, 2)(3, 4)(5, 7)(6, 8)(9, 13)(10, 12)(11, 15)(14, 19) (16, 23)
> (17, 22)(18, 21)(20, 27)(24, 29)(25, 28)(26, 30),
> (1, 24, 28, 8)(2, 9, 17, 22)(3, 29, 19, 15)(4, 5, 21, 25)
> (6, 18, 7, 16)(10, 13, 30, 11)(12, 14)(20, 23)(26, 27) >;
> N1 := rep{ o : o in Orbits(Stabilizer(G, 1)) | #o eq 3 };
> tutte := Graph< 30 | <1, N1>^G >;
SparseRep: Bool Default: false
Construct the digraph G with vertex-set V = {@ v1, v2, ..., vn @} (where vi = i for each i if the first form of the constructor is used, or the ith element of the enumerated or indexed set S otherwise), and edge-set E = { e1, e2, ..., eq }. This function returns three values: The graph G, the vertex-set V of G; and the edge-set E of G. If SparseRep is true then the resulting graph will have a sparse representation.The elements of E are specified by the list edges, where the items of edges may be objects of the following types:
In addition to these three basic ways of specifying the edges list, the items in edges may also be:
- (a)
- A pair [ vi, vj ] of vertices in V. The directed edge from vi to vj will be added to the edge-set for G.
- (b)
- A tuple of the form < vi, Ni > where Ni will be interpreted as a set of out-neighbours for the vertex vi. The elements of the sets Ni must be elements of V. If Ni = { u1, u2, ..., ur }, the directed edges [ vi, u1 ], ..., [ vi, ur ] will be added to G.
- (c)
- A sequence [ N1, N2, ..., Nn ] of n sets, where Ni will be interpreted as a set of neighbours for the vertex vi. The directed edges [ vi, ui ], 1 ≤i ≤n, ui ∈Ni, are added to G.
- (d)
- An edge e of a graph or digraph or multigraph or multidigraph or network of order n. If e is an edge { u, v } in an undirected graph then both directed edges [ u, v ] and [ v, u ] are added to G.
- (e)
- An edge-set E of a graph or digraph or multigraph or multidigraph or network of order n. Every edge e in E will be added to G according to the rule set out for a single edge.
- (f)
- A graph or a digraph or a multigraph or a multidigraph or a network H of order n. Every edge e in H's edge-set is added to G according to the rule set out for a single edge.
- (g)
- A n x n (0, 1)-matrix A. The matrix A will be interpreted as the adjacency matrix for a digraph H on n vertices and the edges of H will be added will be added to G.
- (h)
- A set of
- (i)
- Pairs of the form [ vi, vj ] of vertices in V.
- (ii)
- Tuples of the form < vi, Ni > where Ni will be interpreted as a set of out-neighbours for the vertex vi.
- (iii)
- Edges of a graph or digraph or multigraph or multidigraph or network of order n.
- (iv)
- Graphs or digraphs or multigraphs or multidigraphs or networks of order n.
- (j)
- A sequence of
- (i)
- Tuples of the form < vi, Ni > where Ni will be interpreted as a set of out-neighbours for the vertex vi.
Let A be a n x m matrix such that each column contains at most one entry equal to +1 and at most one entry equal to -1 (all others being zero). Then a digraph G of order n and size m having A as its incidence matrix will be constructed. The rows of A will correspond to the vertices of G while the columns will correspond to the edges. If column k of A contains +1 in row i and -1 in row j, the directed edge vivj will be included in G. If only row i has a non-zero entry (either 1 or -1), then the loop vivi will be included in G.
> D1 := Digraph< 5 | [1, 2], [1, 3], [1, 4], > [3, 2], [4, 3] >; > D1; Digraph Vertex Neighbours 1 2 3 4 ; 2 ; 3 2 ; 4 3 ; 5 ;The same digraph with a sparse representation:
> D1 := Digraph< 5 | [1, 2], [1, 3], [1, 4], > [3, 2], [4, 3] : SparseRep := true>;We next construct the digraph by giving its adjacency matrix:
> M := MatrixRing(Integers(), 5); > D2 := Digraph< 5 | > M![ 0,1,1,1,0, > 0,0,0,0,0, > 0,1,0,0,0, > 0,0,1,0,0, > 0,0,0,0,0 ] >; > IsIsomorphic(D1, D2); true
Let S be the set over which the graph G is defined. The set S is referred to as the support of G.
The indexed set used in the construction of G (or the graph for which V is the vertex-set), or the standard set {@ 1, ..., n @} if it was not given.
If G is a graph having n vertices and S is an indexed set of cardinality n, return a new graph H equal to G but whose support is S. That is, H is structurally equal to G and its vertex and edge decorations are the same as those for G.
The procedural version of the above function.
The graph H equal to G but defined on the standard support. That is, H is structurally equal to G and its vertex and edge decorations are the same as those for G.
> V := Subsets({1..5}, 2);
> O3 := Graph< V | { {u,v} : u,v in V | IsDisjoint(u, v) } >;
> O3;
Graph
Vertex Neighbours
{ 1, 5 } { 2, 4 } { 2, 3 } { 3, 4 } ;
{ 2, 5 } { 1, 3 } { 1, 4 } { 3, 4 } ;
{ 1, 3 } { 2, 5 } { 2, 4 } { 4, 5 } ;
{ 1, 4 } { 2, 5 } { 3, 5 } { 2, 3 } ;
{ 2, 4 } { 1, 5 } { 1, 3 } { 3, 5 } ;
{ 3, 5 } { 1, 4 } { 2, 4 } { 1, 2 } ;
{ 2, 3 } { 1, 5 } { 1, 4 } { 4, 5 } ;
{ 1, 2 } { 3, 5 } { 3, 4 } { 4, 5 } ;
{ 3, 4 } { 1, 5 } { 2, 5 } { 1, 2 } ;
{ 4, 5 } { 1, 3 } { 2, 3 } { 1, 2 } ;
> Support(O3);
{@
{ 1, 5 },
{ 2, 5 },
{ 1, 3 },
{ 1, 4 },
{ 2, 4 },
{ 3, 5 },
{ 2, 3 },
{ 1, 2 },
{ 3, 4 },
{ 4, 5 }
@}
> SO3 := StandardGraph(O3);
> SO3;
Graph
Vertex Neighbours
1 5 7 9 ;
2 3 4 9 ;
3 2 5 10 ;
4 2 6 7 ;
5 1 3 6 ;
6 4 5 8 ;
7 1 4 10 ;
8 6 9 10 ;
9 1 2 8 ;
10 3 7 8 ;
> Support(SO3);
{@ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 @}
Some of the construction functions listed below can also be used to create a graph with a sparse representation. Are concerned only those functions creating relatively sparse graphs.
The complete bipartite graph, Km, n, with partite sets of cardinality m and n.
The complete graph Kn on n vertices.
SparseRep: Bool Default: false
The graph of the n-dimensional cube, Qn. The graph can be created as a sparse graph if so requested.
Given a sequence Q of positive integers m1, ..., mr, construct the complete multipartite graph Km1, ..., mr.
SparseRep: Bool Default: false
The graph on n vertices with no edges. It can be created as a sparse graph if so requested.
SparseRep: Bool Default: false
The graph with no vertices and no edges. It can be created as a sparse graph if so requested.
SparseRep: Bool Default: false
The path graph on n vertices, i.e. the graph on vertices v1, ..., vn, with vi and vj (1 ≤i < j ≤n) adjacent if and only if j = i + 1. The graph can be created as a sparse graph if so requested.
SparseRep: Bool Default: false
Given an integer n ≥3, define the polygon graph on n vertices, i.e. the graph on vertices v1, ..., vn, with vi and vj (1 ≤i < j ≤n) adjacent if and only if j = i + 1, or i = 1 and j = n. The graph can be created as a sparse graph if so requested.
SparseRep: Bool Default: false
A random graph on n vertices such that the probability that an arbitrary pair of vertices is adjacent is given by the real number r, where r lies in the interval [0, 1]. The graph can be created as a sparse graph if so requested.
SparseRep: Bool Default: false
A random tree on n vertices. It can be created as a sparse graph if so requested.
As for standard graphs (Subsection Construction of a Standard Graph) some of the construction functions listed below can be used to create digraphs with a sparse representation.
The complete symmetric digraph on n vertices.
SparseRep: Bool Default: false
The null digraph on n vertices. It can be created as sparse if so requested.
SparseRep: Bool Default: false
A random digraph on n vertices such that the probability that there exists an edge directed from vertex u to vertex v, where u and v arbitrary vertices, is given by the real number r, where r lies in the interval [0, 1]. The digraph can be created as sparse if so requested.
> kd5 := CompleteDigraph(5); > kd5; Digraph Vertex Neighbours 1 2 3 4 5 ; 2 1 3 4 5 ; 3 1 2 4 5 ; 4 1 2 3 5 ; 5 1 2 3 4 ;We next construct a random digraph on 5 vertices such that the probability that there is an edge directed from an arbitrary vertex to any other arbitrary vertex is 0.75.
> rd5 := RandomDigraph(5, 0.75); > rd5; Digraph Vertex Neighbours 1 2 5 ; 2 2 3 4 5 ; 3 2 3 4 5 ; 4 1 2 3 5 ; 5 2 3 4 ;