The two main ways in which to construct a new graph from an old one are either by taking a subgraph of or by modifying the original graph. Another method is to take the quotient graph. When the first two methods are employed, the support set and vertex and edge decorations are retained in the resulting graph.
Construct the graph H as a subgraph of G. The function returns three values: The graph H, the vertex-set V of H; and the edge-set E of H. If G has a support set and/or if G has vertex/edge decorations, then these attributes are transferred to the subgraph H.The elements of V and of E are specified by the list list whose items can be objects of the following types:
It is easy to recover the map that maps the vertices of the subgraph to the vertices of the supergraph and vice-versa. We give an example below.
- (a)
- A vertex of G. The resulting subgraph will be the subgraph induced on the subset of VertexSet(G) defined by the vertices in list.
- (b)
- An edge of G. The resulting subgraph will be the subgraph with vertex-set VertexSet(G) whose edge-set consists of the edges in list.
- (c)
- A set of
- (i)
- Vertices of G.
- (ii)
- Edges of G.
Given a graph G and a partition P of the vertex-set V(G) of G, construct the quotient graph Q of G defined by P. The partition is given as a set of subsets of V(G). Suppose the cells of the partition P are P1, ..., Pr. The vertices of Q correspond to the cells Pi. Vertices vi and vj of Q are adjacent if and only if there is an edge in G joining a vertex in Pi with a vertex in Pj.
> K5, V := CompleteGraph(5);
> K3, V1 := sub< K5 | { V | 3, 4, 5 } >;
> IsSubgraph(K5, K3);
true
>
> V!V1!1;
3
>
> V1!V!4;
2
>
> V1!V!1;
>> V1!V!1;
^
Runtime error in '!': Illegal coercion
LHS: GrphVertSet
RHS: GrphVert
A 1-factor of a graph G is a set of disjoint edges which form a spanning forest for G. In the following example, we construct the graph that corresponds to K6 with a 1-factor removed.
> K6, V, E := CompleteGraph(6);
> K6;
Graph
Vertex Neighbours
1 2 3 4 5 6 ;
2 1 3 4 5 6 ;
3 1 2 4 5 6 ;
4 1 2 3 5 6 ;
5 1 2 3 4 6 ;
6 1 2 3 4 5 ;
> F1 := { E | {1,2}, {3, 4}, {5, 6} };
> G1, V1, E1 := K6 - F1;
> G1;
Graph
Vertex Neighbours
1 3 4 5 6 ;
2 3 4 5 6 ;
3 1 2 5 6 ;
4 1 2 5 6 ;
5 1 2 3 4 ;
6 1 2 3 4 ;
> K9, V, E := CompleteGraph(9);
> P := { { V | 1, 2, 3}, { V | 4, 5, 6}, { V | 7, 8, 9} };
> Q := quo< K9 | P >;
> Q;
Graph
Vertex Neighbours
1 2 3 ;
2 1 3 ;
3 1 2 ;
Unless otherwise specified, each of the functions described in this section returns three values:
Given a graph G and a non-negative integer n, adds n new vertices to G. The existing vertex and edge decorations are retained, but the support will become the standard support.
The procedural version of the previous function. AddVertex adds one vertex only to G.
Given a graph G and a label l, adds a new vertex with label l to G. The existing vertex and edge decorations are retained, but the support will become the standard support.
Given a graph G and a non-negative integer n, and a sequence of n labels, adds n new vertices to G with labels from L. The existing vertex and edge decorations are retained, but the support will become the standard support.
Given a graph G and a vertex v or a set of vertices U of G, removes v or the vertices in U from G. The support and vertex and edge decorations are retained.
The procedural versions of the previous functions.
Given a graph G and a pair of vertices of G, add the edge to G described by this pair. If G is undirected then the edge must be given as a set of (two) vertices, if G is directed the edge is given as a sequence of (two) vertices. The support and existing vertex and edge decorations are retained. This set of functions has two return values: The first is the modified graph and the second is the newly created edge.
Given a graph G and a set of pairs of vertices of G, add the edges to G described by these pairs. If G is undirected then edges must be given as a set of (two) vertices, if G is directed edges are given as a sequence of (two) vertices. The support and existing vertex and edge decorations are retained.
The procedural versions of the previous four functions.
Given a graph G, two vertices of G u and v, returns a new edge between u and v. The support and existing vertex and edge decorations are retained. This function has two return values: The first is the modified graph and the second is the newly created edge.
Given a graph G, two vertices of G u and v, and a label l, adds a new edge with label l between u and v. The support and existing vertex and edge decorations are retained. This function has two return values: The first is the modified graph and the second is the newly created edge.
Procedural versions of previous functions adding edges to a graph.
Given a graph G, a set S of pairs of vertices of G, adds the edges specified in S. The elements of S must be sets or sequences of two vertices of G, depending on whether G is undirected or directed respectively. The support and existing vertex and edge decorations are retained.
Given a graph G, a sequence S of pairs of vertices of G, and a sequence L of labels of same length, adds the edges specified in S with its corresponding label in L. The elements of S must be sets or sequences of two vertices of G, depending on whether G is undirected or directed respectively. The support and existing vertex and edge decorations are retained.
Procedural versions of previous functions adding edges to a graph.
Given a graph G and an edge e or a set S of edges of G, removes e or the edges in S from G. The resulting graph will have vertex-set V(G) and edge-set E(G) - { e } or E(G) - S. The support and existing vertex and edge decorations are retained.
Given a graph G and a set S of pairs { u, v } or [u, v], u, v vertices of G, form the graph having vertex-set V(G) and edge-set E(G) minus the edges from u to v for all pairs in S. An edge is represented as a set if G is undirected, as a set otherwise. The support and existing vertex and edge decorations are retained.
The procedural versions of the previous functions.
Unless otherwise stated, each of the functions described here apply to both graphs and digraphs. Further, each of the functions returns three values:
The complement of the graph G.
Given an edge e = {u, v} of the graph G, form the graph obtained by identifying the vertices u and v, and removing any multiple edges (and loops if the graph is undirected) from the resulting graph. The graph's support and vertex/edges decorations are retained.
Given vertices u and v belonging to the graph G, return the graph obtained by identifying the vertices u and v, and removing any multiple edges (and loops if the graph is undirected) from the resulting graph. The graph's support and vertex/edges decorations are retained.
Given a set S of vertices belonging to the graph G, return the graph obtained by identifying all of the vertices in S, and removing any multiple edges (and loops if the graph is undirected) from the resulting graph. The graph's support and vertex/edges decorations are retained.
Given an edge e in the graph G, insert a new vertex of degree 2 in e. If applicable, the two new edges thus created that replace e will have the same capacity and weight as e. They will be unlabelled. The vertex labels and the edge decorations of G are retained, but the resulting graph will have standard support.
Given an a set T of edges belonging to the graph G, insert a vertex of degree 2 in each edge belonging to the set T. Vertex and edge decorations are handled as in the single edge case.
The line graph of the non-empty graph G.
Given a vertex u in an undirected graph G, construct an undirected graph H from G, where H has the same vertex-set as G and the same edge-set, except that the vertices that were the neighbours of u in G become the non-neighbours of u in H, and the vertices that were non-neighbours of u in G become the neighbours of u in H. The support and vertex labels are not retained in the resulting graph.
Given a set S of vertices belonging to the undirected graph G, apply the function Switch(u), to each vertex of S in turn. The support and vertex labels are not retained in the resulting graph.
> G := CompleteGraph(5);
> E := EdgeSet(G);
> H := InsertVertex({ E | { 1, 3 }, { 1, 4 }, { 2, 4 }, { 2, 5 }, { 3, 5 } } );
> L := Union(H, CompleteGraph(1));
> V := VertexSet(L);
> L := L + { { V.11, V.6 }, { V.11, V.7 }, { V.11, V.8 }, { V.11, V.9 },
> { V.11, V.10 } };
> L;
Graph
Vertex Neighbours
1 2 5 6 7 ;
2 1 3 8 10 ;
3 2 4 6 9 ;
4 3 5 7 8 ;
5 1 4 9 10 ;
6 1 3 11 ;
7 1 4 11 ;
8 2 4 11 ;
9 3 5 11 ;
10 2 5 11 ;
11 6 7 8 9 10 ;