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 as a dense graph.
SparseRep: Bool Default: false
Construct the graph G with vertex set V = {@ v_1, v_2, ..., v_n @} (where v_i = 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 = { e_1, e_2, ..., e_q }. 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 {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 < v_i, N_i > 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 = { u_1, u_2, ..., u_r }, the edges {v_i, u_1}, ..., {v_i, u_r} will be added to G.
- (c)
- A sequence [ N_1, N_2, ..., 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 <= i <= n, u_i in N_i, are added to G.
- (d)
- An edge e of a graph or digraph 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 network of order n. Every edge e in E will be added to G.
- (f)
- A graph or a digraph 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 { v_i, v_j } of vertices in V.
- (ii)
- Tuples of the form < v_i, N_i > where N_i will be interpreted as a set of neighbours for the vertex v_i.
- (iii)
- Edges of a graph or digraph or network of order n.
- (iv)
- Graphs or digraphs or networks of order n.
- (j)
- A sequence of
- (i)
- Tuples of the form < v_i, N_i > where N_i will be interpreted as a set of neighbours for the vertex v_i.
Let A be a p x q (0, 1) matrix having exactly two 1s in each column. Then a (p, q) graph G 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 = {@ v_1, v_2, ..., v_n @} (where v_i = 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 = { e_1, e_2, ..., e_q }. 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 [ 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 < v_i, N_i > 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 = { u_1, u_2, ..., u_r }, the directed edges [v_i, u_1], ..., [v_i, u_r] will be added to G.
- (c)
- A sequence [ N_1, N_2, ..., 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 <= i <= n, u_i in N_i, are added to G.
- (d)
- An edge e of a graph or digraph 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 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 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 [v_i, v_j] of vertices in V.
- (ii)
- Tuples of the form < v_i, N_i > 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 network of order n.
- (iv)
- Graphs or digraphs or networks of order n.
- (j)
- A sequence of
- (i)
- Tuples of the form < v_i, N_i > where N_i will be interpreted as a set of out-neighbours for the vertex v_i.
Let A be a p x q 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 (p, q) digraph G 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.
> 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, that is, the vertex-set V of G is an indexed set identical to S but having type GrphSetVert. 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, ..., p @} if it was not given.
If G is a graph having p vertices and S is an indexed set of cardinality p, return a new graph H isomorphic to G whose support is S.
If G is a graph having p vertices and S is an indexed set of cardinality p, change the support of G to S.
The graph isomorphic to G defined on the standard support.
> 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, K_(m, n), with partite sets of cardinality m and n.
The complete graph K_p on p vertices.
SparseRep: Bool Default: false
The graph of the k-dimensional cube, Q_k. The graph can be created as a sparse graph if so requested.
Given a sequence Q of positive integers m_1, ..., m_r, construct the complete multipartite graph K_(m_1, ..., m_r).
SparseRep: Bool Default: false
The graph on p 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 p vertices, i.e. the graph on vertices v_1, ..., v_p, with v_i and v_j (1 <= i < j <= p) 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 p >= 3, define the polygon graph on p vertices, i.e. the graph on vertices v_1, ..., v_p, with v_i and v_j (1 <= i < j <= p) adjacent if and only if j = i + 1, or i = 1 and j = p. The graph can be created as a sparse graph if so requested.
SparseRep: Bool Default: false
A random graph on p 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 p 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 p vertices.
SparseRep: Bool Default: false
The null digraph on p vertices. It can be created as sparse if so requested.
SparseRep: Bool Default: false
A random digraph on p 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 ;