Construct the graph G with vertex set V = { v_1, v_2, ..., v_p } and edge set E = { e_1, e_2, ..., e_q }. The elements of the edge set 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 {i, j}, where i and j are distinct integers lying in the range [1, ..., p]. The edge { v_i, v_j } 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 integers lying in the range [1, ..., p]. If N_i = { u_1, u_2, ..., u_r }, then edges { v_i, u_1 }, ..., { v_i, u_r } will be added to G. Note that the set N_i may not contain the integer i.
- 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 for G; and
- The edge-set E for 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.
> K5 := CompleteGraph( 5 );We construct the Petersen graph first 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 now construct the same 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 same 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] >; > print P;Construction of Tutte's 8-cage using the technique described in P. Lorimer, J. of Graph Theory, 13, 5 (1989), 553--557.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 ;
> G5<a,h,p,q,r,s> := Group< a, h, p, q, r, s | a ^ 2, h ^ 3, p ^ 2,
> q ^ 2, r ^ 2, s ^ 2, (p,h), p ^ a*q, q ^ h*r, r ^ a*s,
> h ^ s*h, r ^ h*r*q*p, (p,q), (p,r), (q,r), (p,s), (q,s), p*q*r*s*r*s >;
>
> Sub10 := LowIndexSubgroups(G5, <10, 10>);
> f, im, ker := CosetAction(G5, Sub10[1]);
> IU := CosetImage(im, sub< im | h@f, p@f, q@f, r@f, s@f > );
> // The vertices of the graph correspond to the cosets of the stabilizer of 1
> // in im. We find the neighbours of vertex 1 by looking for the length-3 orbit
> // of the stabilizer of 1.
> stab := Stabilizer( IU, 1 );
> orbs := Orbits( stab );
> nhb1 := rep{ o : o in orbs | #o eq 3 };
> // We get the remaining edges of the graph by taking the images of the
> // edges joining 1 to its neighbours under the action of a representative
> // for each coset of stab in im.
> tutte := Graph< 30 | { { 1 ^ x, y ^ x } : y in nhb1,
> x in Transversal(IU, stab) } >;
Construct the digraph G with vertex set V = { v_1, v_2, ..., v_p } and edge set E = { e_1, e_2, ..., e_q }. The elements of the edge set 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 [i, j], where i and j are integers lying in the range [1, ..., p] . The edge (v_i, v_j), that is, an edge directed from v_i to v_j, 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 integers lying in the range [1, ..., p]. 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 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 for G; and
- The edge-set E for G.
Let A be a p x q matrix such that each column contains exactly one entry equal to +1 and 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.
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 null graph on p vertices.
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].[Next] [Prev] [Right] [Left] [Up] [Index] [Root]