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.
Construct the graph G with vertex set V = {@ v_1, v_2, ..., v_p @} (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 }. The elements of E are specified by the list edges, where the items of edges may be objects of the following types:The graph G produced by this constructor will be the edge-union of the graphs specified in the list edges. The function returns three values:
- A set {u, v}, where u and v are distinct vertices in V. The edge { u, v } will be added to the edge set for G.
- A set S each of whose terms are two-element sets of type (a). The elements of S define a collection of edges for the graph G.
- A sequence [ N_1, N_2, ..., N_p ] of p sets, where N_i is 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 }, then edges { v_i, u_1 }, ..., { v_i, u_r } will be added to G.
- A tuple or set or sequence of tuples of the form < v_i, N_i > where N_i is as above.
- A graph H on p vertices. The vertices of H will be identified with those of G in the obvious way. The edges of H will be included among the edges of G.
- A set S of graphs on p vertices. The vertices of each graph H of S will be identified with those of G in the obvious way. The edges of H will be included among the edges of G.
- An edge, set of edges, or edge-set of a graph H on p vertices. These edges will be included among the edges of G.
- A p x p symmetric (0, 1)-matrix A, where A may be over any coefficient ring. The matrix A will be interpreted as the adjacency matrix for a graph H on p vertices and the edges of H will be included among the edges of G.
- The graph G;
- The vertex-set V of G; and
- The edge-set E of G.
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 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 >;
Construct the digraph G with vertex set V = {@ v_1, v_2, ..., v_p @} (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 }. The elements of E are specified by the list edges, where the items of edges may be objects of the following types:The digraph G produced by this constructor will be the edge-union of the graphs specified in the list L. The function returns three values:
- A pair [u, v] of vertices in V. The directed edge (u, v) from u to v, will be added to the edge set for G;
- A set S each of whose terms are pairs of type (a). The elements of S define a collection of edges for the graph G.
- A sequence [ N_1, N_2, ..., N_p ] of p sets, 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 edges (v_i, u_1), ..., (v_i, u_r) will be added to G;
- A tuple or set or sequence of tuples of the form < v_i, N_i > where N_i is as above.
- A digraph H on p vertices. The edges of H will be included among the edges of G.
- A set S of digraphs each on p vertices. The edges of each graph H of S will be included among the edges of G.
- An edge, set of edges, or edge-set of a digraph H on p vertices. These edges will be included among the edges of G.
- A p x p (0, 1)-matrix A. The matrix A will be interpreted as the adjacency matrix for a digraph H on p vertices and the edges of H will be included among the edges of G.
- The digraph G;
- The vertex-set V of G; and
- The edge-set E of G.
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 NeighboursWe next construct the digraph by giving its adjacency matrix:1 2 3 4 ; 2 ; 3 2 ; 4 3 ; 5 ;
> 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.
Support(G) : Grph -> SetIndx
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 @}
The complete bipartite graph, K_(m, n), with partite sets of cardinality m and n.
The complete graph K_p on p vertices.
The graph of the k-dimensional cube, Q_k.
Given a sequence Q of positive integers m_1, ..., m_r, construct the complete multipartite graph K_(m_1, ..., m_r).
The graph on p vertices with no edges.
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.
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.
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].
A random tree on p vertices.
The complete symmetric digraph on p vertices.
The null digraph on p vertices.
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].
> kd5 := CompleteDigraph(5); > kd5; Digraph Vertex NeighboursWe 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.
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 ;
> 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 ;