The Vertex--Set and Edge--Set of a Graph

Contents

Introduction

Let G be a graph on n vertices and m edges whose vertex-set is V = {v1, ..., vm} and edge-set is E = {e1, ..., em}. 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 ≤i ≤#V, create the vertex vi 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 ≤i ≤#E, create the i-th edge of E.

Example Graph_EdgeSets (H158E8)

The construction of vertices and edges is illustrated using the Odd Graph, O3. 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

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.

V2.28, 13 July 2023