Construction of Graphs and Digraphs#
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.
Bounds on the Graph Order#
Memory allocation for any elementary object (that is, accessed via a single pointer) cannot exceed \(2^{32}\) 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 \leq 65535\),
- for the sparse representation, \(n \leq 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.
- GraphSizeInBytes(n, m : parameters): RngIntElt, RngIntElt -> RngIntElt#
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.
- Example: Grph Size (ex-1d9be6)#
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); 2097580
However, 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 \(2^{32}\):
> m := 33538101; > assert GraphSizeInBytes(n, m : SparseRep := true) gt 2^32;
Construction of a General Graph#
- Graph< n | edges : parameters>: RngIntElt, List -> GrphUnd, GrphVertSet, GrphEdgeSet#
- Graph< S | edges : parameters >: SetEnum, List -> GrphUnd, GrphVertSet, GrphEdgeSet#
- Graph< S | edges : parameters>: SetIndx, List -> GrphUnd, GrphVertSet, GrphEdgeSet#
SparseRep: Bool Default: false
Construct the graph \(G\) with vertex-set \(V = \lbrace @ v_1, v_2, \ldots, v_n @ \rbrace\) (where \(v_i = i\) for each \(i\) if the first form of the constructor is used, or the \(i\)th element of the enumerated or indexed set \(S\) otherwise), and edge-set \(E = \lbrace e_1, e_2, \ldots, e_q \rbrace\). This function returns three values: The graph \(G\), the vertex-set \(V\) of \(G\); and the edge-set \(E\) of \(G\). If SparseRep is
truethen the resulting graph will have a sparse representation.The elements of \(E\) are specified by the list
edges, where the items ofedgesmay be objects of the following types:- (a)
A pair \(\{ v_i, v_j \}\) of vertices in \(V\). The edge from \(v_i\) to \(v_j\) will be added to the edge-set for \(G\).
- (b)
A tuple of the form \(\langle v_i, N_i \rangle\) where \(N_i\) will be interpreted as a set of neighbours for the vertex \(v_i\). The elements of the sets \(N_i\) must be elements of \(V\). If \(N_i = \lbrace u_1, u_2, \ldots, u_r \rbrace\), the edges \(\{ v_i, u_1 \}, \ldots, \{ v_i, u_r \}\) will be added to \(G\).
- (c)
A sequence \([ N_1, N_2, \ldots, N_n ]\) of \(n\) sets, where \(N_i\) will be interpreted as a set of neighbours for the vertex \(v_i\). The edges \(\{ v_i, u_i \}\), \(1 \leq i \leq n\), \(u_i \in N_i\), are added to \(G\).
In addition to these three basic ways of specifying the \(edges\) list, the items in \(edges\) may also be:
- (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\times 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 \(\{ v_i, v_j \}\) of vertices in \(V\).
- (ii)
Tuples of the form \(\langle v_i, N_i \rangle\) where \(N_i\) will be interpreted as a set of neighbours for the vertex \(v_i\).
- (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 \(\langle v_i, N_i \rangle\) where \(N_i\) will be interpreted as a set of neighbours for the vertex \(v_i\).
- IncidenceGraph(A): ModMatRngElt -> GrphUnd#
Let \(A\) be a \(n \times 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.
- Example: Constructors (ex-f07f4d)#
The Petersen graph will be constructed in various different ways to illustrate the use of the constructor. Firstly, it will be constructed by listing 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 ;
- Example: Tutte Cage (ex-d2036c)#
A more sophisticated example is the construction of Tutte’s \(8\)-cage using the technique described in P. Lorimer [Lorimer, 1989]. The graph is constructed so that it has \(G = P{\operatorname{\Gamma L}}(2,9)\) in its representation of degree \(30\) as its automorphism group. The vertices of the graph correspond to the points on which \(G\) acts. The neighbours of vertex \(1\) are the points lying in the unique orbit \(N_{1}\) of length \(3\) of the stabilizer of \(1\). The edges for vertex \(i\) are precisely the points \(N_{1}^g\) where \(g\) is an element of \(G\) such that \(1^g = i\).
> 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 >;
Construction of a General Digraph#
- Digraph< n | edges : parameters>: RngIntElt, List -> GrphDir#
- Digraph< S | edges : parameters>: SetEnum, List -> GrphDir#
- Digraph< S | edges : parameters>: SetIndx, List -> GrphDir#
SparseRep: Bool Default: false
Construct the digraph \(G\) with vertex-set \(V = \lbrace @ v_1, v_2, \ldots, v_n @ \rbrace\) (where \(v_i = i\) for each \(i\) if the first form of the constructor is used, or the \(i\)th element of the enumerated or indexed set \(S\) otherwise), and edge-set \(E = \lbrace e_1, e_2, \ldots, e_q \rbrace\). This function returns three values: The graph \(G\), the vertex-set \(V\) of \(G\); and the edge-set \(E\) of \(G\). If SparseRep is
truethen the resulting graph will have a sparse representation.The elements of \(E\) are specified by the list
edges, where the items ofedgesmay be objects of the following types:- (a)
A pair \([ v_i, v_j ]\) of vertices in \(V\). The directed edge from \(v_i\) to \(v_j\) will be added to the edge-set for \(G\).
- (b)
A tuple of the form \(\langle v_i, N_i \rangle\) where \(N_i\) will be interpreted as a set of out-neighbours for the vertex \(v_i\). The elements of the sets \(N_i\) must be elements of \(V\). If \(N_i = \lbrace u_1, u_2, \ldots, u_r \rbrace\), the directed edges \([ v_i, u_1 ], \ldots, [ v_i, u_r ]\) will be added to \(G\).
- (c)
A sequence \([ N_1, N_2, \ldots, N_n ]\) of \(n\) sets, where \(N_i\) will be interpreted as a set of neighbours for the vertex \(v_i\). The directed edges \([ v_i, u_i ]\), \(1 \leq i \leq n\), \(u_i \in N_i\), are added to \(G\).
In addition to these three basic ways of specifying the \(edges\) list, the items in \(edges\) may also be:
- (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\times 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 \([ v_i, v_j ]\) of vertices in \(V\).
- (ii)
Tuples of the form \(\langle v_i, N_i \rangle\) where \(N_i\) will be interpreted as a set of out-neighbours for the vertex \(v_i\).
- (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 \(\langle v_i, N_i \rangle\) where \(N_i\) will be interpreted as a set of out-neighbours for the vertex \(v_i\).
- IncidenceDigraph(A): ModMatRngElt -> GrphDir#
Let \(A\) be a \(n \times 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 \(v_iv_j\) will be included in \(G\). If only row \(i\) has a non-zero entry (either \(1\) or \(-1\)), then the loop \(v_iv_i\) will be included in \(G\).
- Example: Constructors (ex-fe5c22)#
The digraph \(D\) with vertices \(\lbrace v_1, v_2, v_3, v_4, v_5 \rbrace\) and edges \((v_1, v_2), (v_1, v_3), (v_1, v_4), (v_3, v_2)\), and \((v_4, v_3)\) will be constructed, firstly by listing its edges and secondly by giving its adjacency matrix.
> 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
Operations on the Support#
Let \(S\) be the set over which the graph \(G\) is defined. The set \(S\) is referred to as the support of \(G\).
- Support(G): Grph -> SetIndx#
- Support(V): GrphVertSet -> SetIndx#
The indexed set used in the construction of \(G\) (or the graph for which \(V\) is the vertex-set), or the standard set \(\lbrace @ 1, \ldots, n @ \rbrace\) if it was not given.
- ChangeSupport(G, S): Grph, SetIndx -> Grph, GrphVertSet, GrphEdgeSet#
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\).
- ChangeSupport(~G, S): Grph, SetIndx#
The procedural version of the above function.
- StandardGraph(G): Grph -> Grph#
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\).
- Example: Constructors (ex-ec4c86)#
The Odd Graph, \(O_n\), has as vertices all \(n\)-subsets of a \(2n-1\) set with two vertices adjacent if and only if they are disjoint. We construct \(O_3\) and then form its standard graph.
> 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 @}
Construction of a Standard Graph#
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.
- BipartiteGraph(m, n): RngIntElt, RngIntElt -> GrphUnd#
The complete bipartite graph, \(K_{m, n}\), with partite sets of cardinality \(m\) and \(n\).
- CompleteGraph(n): RngIntElt -> GrphUnd#
The complete graph \(K_n\) on \(n\) vertices.
- KCubeGraph(n : parameters): RngIntElt -> GrphUnd#
SparseRep: Bool Default: false
The graph of the \(n\)-dimensional cube, \(Q_n\). The graph can be created as a sparse graph if so requested.
- MultipartiteGraph(Q): [RngIntElt] -> GrphUnd#
Given a sequence \(Q\) of positive integers \(m_1,\ldots, m_r\), construct the complete multipartite graph \(K_{m_1, \ldots, m_r}\).
- EmptyGraph(n : parameters): RngIntElt -> GrphUnd#
SparseRep: Bool Default: false
The graph on \(n\) vertices with no edges. It can be created as a sparse graph if so requested.
- NullGraph(: parameters) -> GrphUnd#
SparseRep: Bool Default: false
The graph with no vertices and no edges. It can be created as a sparse graph if so requested.
- PathGraph(n : parameters): RngIntElt -> GrphUnd#
SparseRep: Bool Default: false
The path graph on \(n\) vertices, i.e. the graph on vertices \(v_1,\ldots, v_n\), with \(v_i\) and \(v_j\) (\(1 \leq i < j \leq n\)) adjacent if and only if \(j = i + 1\). The graph can be created as a sparse graph if so requested.
- PolygonGraph(n : parameters): RngIntElt -> GrphUnd#
SparseRep: Bool Default: false
Given an integer \(n \geq 3\), define the polygon graph on \(n\) vertices, i.e. the graph on vertices \(v_1, \ldots, v_n\), with \(v_i\) and \(v_j\) (\(1 \leq i < j \leq 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.
- RandomGraph(n, r : parameters): RngIntElt, FldReElt -> GrphUnd#
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.
- RandomTree(n : parameters): RngIntElt -> GrphUnd#
SparseRep: Bool Default: false
A random tree on \(n\) vertices. It can be created as a sparse graph if so requested.
Construction of a Standard Digraph#
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.
- CompleteDigraph(n): RngIntElt -> GrphDir#
The complete symmetric digraph on \(n\) vertices.
- EmptyDigraph(n : parameters): RngIntElt -> GrphDir#
SparseRep: Bool Default: false
The null digraph on \(n\) vertices. It can be created as sparse if so requested.
- RandomDigraph(n, r : parameters): RngIntElt, FldReElt -> GrphDir#
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.
- Example: Constructors (ex-d57426)#
The complete symmetric digraph on \(5\) vertices is created as follows:
> 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 ;