|
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.
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 such that
1 ≤i ≤#V, create the vertex vi 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.
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 such that 1 ≤i ≤#E,
create the i-th edge of E.
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
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 : GrphEdgeSet -> RngIntElt
The cardinality of the set S.
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 : 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 : 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 : 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 : GrphEdgeSet, GrphEdgeSet -> BoolElt
Return true if the vertex-set (edge-set) S is equal to the vertex-set
(edge-set) T.
s eq t : GrphEdge, GrphEdge -> BoolElt
Returns true if the vertex (edge) s
is equal to the vertex (edge) t.
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 : GrphEdge, GrphEdge -> BoolElt
Returns 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) : GrphEdge -> Grph
Return the graph G for which s is a vertex (edge).
Random(S) : GrphEdgeSet -> GrphEdge
Choose a random element from the vertex-set (edge-set) S.
Rep(S) : GrphVertSet -> GrphVert
Representative(S) : GrphEdgeSet -> GrphEdge
Rep(S) : GrphEdgeSet -> GrphEdge
Choose some element from the vertex-set (edge-set) S.
The vertex-set (edge-set) S may appear as the
range in the for-statement.
The vertex-set (edge-set) S may appear as the
range in the for random - statement.
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.
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.
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.
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.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|