The Vertex–Set and Edge–Set of a Graph#

Introduction#

Let \(G\) be a graph on \(n\) vertices and \(m\) edges whose vertex-set is \(V = \{v_1, \ldots, v_m\}\) and edge-set is \(E = \{e_1, \ldots, e_m\}\). A graph created by Magma consists of three objects: the vertex-set \(V\), the edge-set \(E\) and the graph \(G\) itself. The vertex-set and edge-set of a graph are enriched sets and consequently constitute types. The vertex-set and edge-set are returned as the second and third arguments, respectively, by all functions which create graphs. Alternatively, a pair of functions are provided to extract the vertex-set and edge-set of a graph \(G\). The main purpose of having vertex-sets and edge-sets as types is to provide a convenient mechanism for referring to vertices and edges of a graph. Here, the functions applicable to vertex-sets and edge-sets are described.

Creating Edges and Vertices#

EdgeSet(G): Grph -> GrphEdgeSet#: Given a graph \(G\), return the edge-set of \(G\).

Edges(G): Grph -> { @ GrphEdge @ }#: A set \(E\) whose elements are the edges of the graph \(G\). Note that this creates an indexed set and not the edge-set of \(G\), in contrast to the function EdgeSet.

VertexSet(G): Grph -> GrphVertSet#: Given a graph \(G\), return the vertex-set of \(G\).

Vertices(G): Grph -> { GrphVert}#: A set \(V\) whose elements are the vertices of the graph \(G\). In contrast to the function VertexSet, this function returns the collection of vertices of \(G\) in the form of an indexed set.

V ! v: GrphVertSet, . -> GrphVert#: Given the vertex-set \(V\) of the graph \(G\) and an element \(v\) of the support of \(V\), create the corresponding vertex of \(G\).

V . i: GrphVertSet, RngIntElt -> GrphVert#: Given a vertex-set \(V\) and an integer \(i\) such that \(1 \leq i \leq \#V\), create the vertex \(v_i\) of \(V\).

Index(v): GrphVert -> RngIntElt#: Given a vertex \(v\) of some graph \(G\), return the index of \(v\) in the (indexed) vertex-set of \(G\).

E ! { u, v}: GrphEdgeSet, { . } -> GrphEdge#: Given the edge-set \(E\) of the graph \(G\) and objects \(u\), \(v\) belonging to the support of \(G\), which correspond to adjacent vertices, create the edge \(uv\) of \(G\).

E ! [u, v]: GrphEdgeSet, [ . ] -> GrphEdge#: Given the edge-set \(E\) of the digraph \(G\) and objects \(u\), \(v\) belonging to the support of \(G\), which correspond to adjacent vertices, create the edge \(uv\) of \(G\).

E . i: GrphEdgeSet, RngIntElt -> GrphEdge#: Given an edge-set \(E\) and an integer \(i\) such that \(1 \leq i \leq \#E\), create the \(i\)-th edge of \(E\).

Example: Edge Sets (ex-e2c41e)#

The construction of vertices and edges is illustrated using the Odd Graph, \(O_{3}\). and then form its standard graph.

> S := Subsets({1..5}, 2);
> O3, V, E := Graph< S | { {u,v} : u,v in S | IsDisjoint(u, v) } >;
> VertexSet(O3);
Vertex-set of O3
> Vertices(O3);
{@ { 1, 5 }, { 2, 5 }, { 1, 3 }, { 1, 4 }, { 2, 4 }, { 3, 5 },
{ 2, 3 }, { 1, 2 }, { 3, 4 }, { 4, 5 } @}
> EdgeSet(O3);
Edge-set of O3
> Edges(O3);
{@ {{ 1, 5 }, { 2, 4 }}, {{ 1, 5 }, { 2, 3 }}, {{ 1, 5 }, { 3, 4 }},
{{ 2, 5 }, { 1, 3 }}, {{ 2, 5 }, { 1, 4 }}, {{ 2, 5 }, { 3, 4 }},
{{ 1, 3 }, { 2, 4 }}, {{ 1, 3 }, { 4, 5 }}, {{ 1, 4 }, { 3, 5 }},
{{ 1, 4 }, { 2, 3 }}, {{ 2, 4 }, { 3, 5 }}, {{ 3, 5 }, { 1, 2 }},
{{ 2, 3 }, { 4, 5 }}, {{ 1, 2 }, { 3, 4 }}, {{ 1, 2 }, { 4, 5 }} @}
> u := V!{1, 2};
> u, Type(u);
{1, 2} GrphVert
> Index(u);
8
> x := E!{ {1,2}, {3,4}};
> x, Type(x);
{{ 1, 2 }, { 3, 4 }} GrphEdge

Run in calculator

Operations on Vertex-Sets and Edge-Sets#

For each of the following operations, \(S\) and \(T\) may be interpreted as either the vertex-set or the edge-set of the graph \(G\). The variable \(s\) may be interpreted as either a vertex or an edge. The edge-set and vertex-set support all the standard set operations.

# S: GrphVertSet -> RngIntElt#
# S: GrphEdgeSet -> RngIntElt#: The cardinality of the set \(S\).

s in S: GrphVert, GrphVertSet -> BoolElt#
s in S: GrphEdge, GrphEdgeSet -> BoolElt#: Return true if the vertex (edge) \(s\) lies in the vertex-set (edge-set) \(S\), otherwise false.

s notin S: GrphVert, GrphVertSet -> BoolElt#
s notin S: GrphEdge, GrphEdgeSet -> BoolElt#: Return true if the vertex (edge) \(s\) does not lie in the vertex-set (edge-set) \(S\), otherwise false.

S subset T: GrphVertSet, GrphVertSet -> BoolElt#
S subset T: GrphEdgeSet, GrphEdgeSet -> BoolElt#: Return true if the vertex-set (edge-set) \(S\) is contained in the vertex-set (edge-set) \(T\), otherwise false.

S notsubset T: GrphVertSet, GrphVertSet -> BoolElt#
S notsubset T: GrphEdgeSet, GrphEdgeSet -> BoolElt#: Return true if the vertex-set (edge-set) \(S\) is not contained in the vertex-set (edge-set) \(T\), otherwise false.

S eq T: GrphVertSet, GrphVertSet -> BoolElt#
S eq T: GrphEdgeSet, GrphEdgeSet -> BoolElt#: Return true if the vertex-set (edge-set) \(S\) is equal to the vertex-set (edge-set) \(T\).

s eq t: GrphVert, GrphVert -> BoolElt#
s eq t: GrphEdge, GrphEdge -> BoolElt#: Returns true if the vertex (edge) \(s\) is equal to the vertex (edge) \(t\).

S ne T: GrphVertSet, GrphVertSet -> BoolElt#
S ne T: GrphEdgeSet, GrphEdgeSet -> BoolElt#: Returns true if the vertex-set (edge-set) \(S\) is not equal to the vertex-set (edge-set) \(T\).

s ne t: GrphVert, GrphVert -> BoolElt#
s ne t: GrphEdge, GrphEdge -> BoolElt#: Returns true if the vertex (edge) \(s\) is not equal to the vertex (edge) \(t\).

ParentGraph(S): GrphVertSet -> Grph#
ParentGraph(S): GrphEdgeSet -> Grph#: Return the graph \(G\) for which \(S\) is the vertex-set (edge-set).

ParentGraph(s): GrphVert -> Grph#
ParentGraph(s): GrphEdge -> Grph#: Return the graph \(G\) for which \(s\) is a vertex (edge).

Random(S): GrphVertSet -> GrphVert#
Random(S): GrphEdgeSet -> GrphEdge#: Choose a random element from the vertex-set (edge-set) \(S\).

Representative(S): GrphVertSet -> GrphVert#
Rep(S): GrphVertSet -> GrphVert#
Representative(S): GrphEdgeSet -> GrphEdge#
Rep(S): GrphEdgeSet -> GrphEdge#: Choose some element from the vertex-set (edge-set) \(S\).

for x in S do ... end for;#: The vertex-set (edge-set) \(S\) may appear as the range in the for-statement.

for random x in S do ... end for;#: The vertex-set (edge-set) \(S\) may appear as the range in the for random - statement.

Operations on Edges and Vertices#

EndVertices(e): GrphEdge -> { GrphVert}#
EndVertices(e): GrphEdge -> [ GrphVert ]#: Given an edge \(e\) belonging to the graph \(G\), return a set containing the two end-vertices of \(e\). If \(G\) is a digraph return the two end-vertices in a sequence.

InitialVertex(e): GrphEdge -> GrphVert#: Given an undirected or directed edge \(e\) from vertex \(u\) to vertex \(v\), return vertex \(u\). This is useful in the undirected case since it indicates, where relevant, the direction in which the edge has been traversed.

TerminalVertex(e): GrphEdge -> GrphVert#: Given an undirected or directed edge \(e\) from vertex \(u\) to vertex \(v\), return vertex \(v\). This is useful in the undirected case since it indicates, where relevant, the direction in which the edge has been traversed.

IncidentEdges(u): GrphVert -> { GrphEdge}#: Given a vertex \(u\) of a graph \(G\), return the set of all edges incident with the vertex \(u\). If \(G\) is directed, then the set consists of all the edges incident into \(u\) and from \(v\).