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\), coerce \(v\) to a vertex of \(G\). If \(v\) lies in the support of \(G\), return the corresponding vertex. If \(v\) is an integer \(i\) with \(1 \leq i \leq \#V\), return the vertex with index \(i\) (equivalent to V . i).

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 an undirected graph \(G\), coerce the unordered pair \(\{u, v\}\) to the edge of \(G\) joining the vertices \(V!u\) and \(V!v\), where \(V\) is the vertex-set of \(G\). It is an error to use this form on a directed graph; use E ! [u, v] for directed graphs.

E ! [u, v]: GrphEdgeSet, [ . ] -> GrphEdge: Given the edge-set \(E\) of a directed graph \(G\) (not a network), coerce the ordered pair \([u, v]\) to the directed edge of \(G\) from vertex \(V!u\) to vertex \(V!v\), where \(V\) is the vertex-set of \(G\). It is an error to use this form on an undirected graph; use E ! {u, v} for undirected graphs.

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: Vertices and Edges of an Odd Graph (ex-e2c41e)

Run in calculator (opens in a new tab)

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
> V ! 8;
{1, 2} GrphVert
> x := E!{ {1,2}, {3,4}};
> x, Type(x);
{{ 1, 2 }, { 3, 4 }} GrphEdge

Run in calculator (opens in a new tab)

Example: Coercing Vertices and Edges of a Digraph (ex-12cef7)

Directed edge coercion uses sequence notation.

> D, VD, ED := Digraph< 3 | {[1,2],[2,3],[3,1]} >;
> v := VD ! 2;
> v, Type(v);
2 GrphVert
> e := ED ! [1, 2];
> e, Type(e);
[1, 2] GrphEdge

Run in calculator (opens in a new tab)

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\).

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

Introduction#

Creating Edges and Vertices#

Operations on Vertex-Sets and Edge-Sets#

Operations on Edges and Vertices#

The Vertex–Set and Edge–Set of a Graph

Introduction

Creating Edges and Vertices

Operations on Vertex-Sets and Edge-Sets

Operations on Edges and Vertices