Subsections

• Introduction
• Creating Edges and Vertices
• Operations on Edges and Vertices

Let G be a (p, q) graph whose vertex set is V = {v_1, ..., v_p} and whose edge set is E = {e_1, ..., e_q}. 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. Note the use of a hyphen to distinguish between ordinary sets of vertices and edges and these type sets. 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

Given a graph G, return the edge-set of G.

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.

Given a graph G, return the vertex-set of G.

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.

Given the vertex-set V of the graph G and an element v of the support of V, create the corresponding vertex of G.

Given a vertex-set V and an integer i, create the vertex v_i of V.

Given a vertex v of some graph G, return the index of v in the (indexed) vertex-set of G.

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.

Given an edge-set E and an integer i, create the i-th edge of E.

> 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

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 eq t : GrphVert, GrphVert -> BoolElt

s eq t : GrphEdge, GrphEdge -> BoolElt

True if the vertex (edge) s is equal to the vertex (edge) t.

S ne T : GrphEdgeSet, GrphEdgeSet -> BoolElt

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

True if the vertex (edge) s is not equal to the vertex (edge) t.

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