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.

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

Given a graph G and an integer i, create the vertex v_i of G.

Given the vertex-set V of the graph G and an integer i in the range [1, ..., p], create the vertex v_i of G.

E ! { i, j } : EdgeSet, RngIntElt, RngIntElt -> Edge

Given the edge-set E of the graph G and distinct integers i and j lying in the range [1, ..., p], such that v_i and v_j are adjacent, create the edge v_iv_j of G.

E ! { u, v } : EdgeSet, Vert, Vert -> Edge

Given the edge-set E of the graph G and adjacent vertices u and v of G, create the edge uv of G.

E ! [i, j] : EdgeSet, RngIntElt, RngIntElt -> Edge

Given the edge-set E of the digraph G and distinct integers i and j lying in the range [1, ..., p], return the edge v_iv_j of the digraph G if that edge exists.

E ! [u, v] : EdgeSet, Vert, Vert -> Edge

Given the edge-set E of the digraph G and vertices u and v of G, return the edge uv of the digraph G if that edge exists.

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.

# S : VertSet -> RngIntElt

# S : EdgeSet -> RngIntElt

The cardinality of the set S.

s in S : Edge, EdgeSet -> BoolElt

True if the vertex (edge) s lies in the vertex-set (edge-set) S, otherwise false.

s notin S : Edge, EdgeSet -> BoolElt

True if the vertex (edge) s does not lie in the vertex-set (edge-set) S, otherwise false.

S subset T : EdgeSet, EdgeSet -> BoolElt

True if the vertex-set (edge-set) S is contained in the vertex-set (edge-set) T, otherwise false.

S notsubset T : EdgeSet, EdgeSet -> BoolElt

True if the vertex-set (edge-set) S is not contained in the vertex-set (edge-set) T, otherwise false.

S eq T : EdgeSet, EdgeSet -> BoolElt

True if the vertex-set (edge-set) S is equal to the vertex-set (edge-set) T.

s eq t : Vert, Vert -> BoolElt

s eq t : Edge, Edge -> BoolElt

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

S ne T : EdgeSet, EdgeSet -> BoolElt

True if the vertex-set (edge-set) S is not equal to the vertex-set (edge-set) T.

s ne t : Vert, Vert -> BoolElt

s ne t : Edge, Edge -> BoolElt

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

ParentGraph(S) : EdgeSet -> Grph

Return the graph G for which S is the vertex-set (edge-set).

ParentGraph(s) : Vert -> Grph

ParentGraph(s) : Edge -> Grph

Return the graph G for which s is a vertex (edge).

Random(S) : EdgeSet -> Edge

Choose a random element from the set S.

Rep(S) : VertSet -> Vert

Representative(S) : EdgeSet -> Edge

Rep(S) : EdgeSet -> Edge

Choose some element from the set S.

The set S may appear as the range in the for-statement.

The set S may appear as the range in the for random-statement.