|
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:
- (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.
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.
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.
We start with a simple example which demonstrates how to map
the vertices of a subgraph onto the vertices of the supergraph
and vice-versa: This is achieved by simple coercion
into the appropriate vertex-set.
> 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 ;
Taking the complete graph K 9, we form its quotient with respect
to the partition of the vertex-set into three 3-sets.
> 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:
- (i)
- The graph G;
- (ii)
- The vertex-set V of G;
- (iii)
- The edge-set E of G.
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.
AddVertex(~G) : Grph ->
AddVertices(~G, n) : Grph, RngIntElt ->
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.
G - U : Grph, { GrphVert } -> Grph
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.
G -:= U : Grph, { GrphVert } ->
RemoveVertex(~G, v) : Grph, GrphVert ->
RemoveVertices(~G, U) : Grph, { GrphVert } ->
The procedural versions of the previous functions.
G + [ u, v ] : GrphDir, [ GrphVert, GrphVert ] -> GrphDir, GrphEdge
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.
G + { [ u, v ] } : GrphDir, { [ GrphVert, GrphVert ] } -> GrphDir
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.
G +:= [ u, v ] : GrphDir, [ GrphVert, GrphVert ] ->
G +:= { { u, v } }: GrphUnd, { { GrphVert, GrphVert } }->
G +:= { [ u, v ] } : GrphDir, { [ GrphVert, GrphVert] } ->
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.
AddEdge(~G, u, v, l) : Grph, GrphVert, GrphVert, . ->
Procedural versions of previous functions adding edges to a graph.
AddEdges(G, S) : GrphDir, { [ GrphVert, GrphVert ] } -> GrphDir
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.
AddEdges(~G, S) : GrphDir, { [ GrphVert, GrphVert ] } ->
AddEdges(~G, S, L) : Grph, SeqEnum, SeqEnum ->
Procedural versions of previous functions adding edges to a graph.
G - { e } : Grph, { GrphEdge } -> Grph
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.
G - { [u, v] } : GrphDir, { [ GrphVert, GrphVert ] } -> GrphDir
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.
G -:= { e } : Grph, { GrphEdge } ->
G -:= { { u, v } } : GrphUnd, { { GrphVert, GrphVert rbrace } ->
G -:= { [u, v] } : GrphDir, { [ GrphVert, GrphVert ] } ->
RemoveEdge(~G, e) : Grph, GrphEdge ->
RemoveEdges(~G, S) : Grph, { GrphEdge } ->
RemoveEdge(~G, u, v) : Grph, GrphVert, GrphVert ->
RemoveEdges(~G, S) : GrphDir, { { GrphVert, GrphVert } } ->
RemoveEdges(~G, S) : GrphDir, { [ GrphVert, GrphVert ] } ->
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:
- (i)
- The graph G;
- (ii)
- The vertex-set V of G;
- (iii)
- The edge-set E of G.
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.
We illustrate the use of some of these operations by using them
to construct the Grötzch graph. This graph may be built by taking the
complete graph K5, choosing a cycle of length 5 (say, 1-3-5-2-4), inserting
a vertex of degree two on each edge of this cycle and finally connecting
each of these vertices to a new vertex.
> 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 ;
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|