The Vertex–Set and Edge–Set of Multigraphs#

Much of the functionality for simple graphs (see Section The Vertex–Set and Edge–Set of a Graph) also applies to multigraphs. We will not repeat here the functions pertaining to the vertex-set and edge-set of a graph, but concentrate instead on the edges. Indeed, there is a difference in the manner in which multigraph edges are created and accessed when compared to simple graph edges.

Since multigraphs may have multiple edges from \(u\) to \(v\), it is necessary to know how many of these edges there are, and how each can be accessed. More importantly a scheme is required to uniquely identify an edge.

Recall that a multigraph is represented by means of an adjacency list, so any edge from \(u\) to \(v\) can be identified by its index in this list. If there is more than one edge from \(u\) to \(v\), then a list of indices will identify each edge from \(u\) to \(v\). Thus, the index of the edge in the adjacency list will be the means by which this edge can be uniquely identified.

This has a bearing on how an edge can be coerced into a multigraph: Successful coercion will require two vertices \(u\) and \(v\) so that \(v\) is a neighbour of \(u\), and a valid index \(i\) in the multigraph’s adjacency list. That is, the position \(i\) in the list is the index of an edge from \(u\) to \(v\).

EdgeIndices(u, v): GrphVert, GrphVert -> SeqEnum#
Indices(u, v): GrphVert, GrphVert -> SeqEnum#: Given vertices \(u\) and \(v\) of a multigraph \(G\), returns the indices of the possibly multiple edge from \(u\) to \(v\).

EdgeMultiplicity(u, v): GrphVert, GrphVert -> RngIntElt#
Multiplicity(u, v): GrphVert, GrphVert -> RngIntElt#: Given vertices \(u\) and \(v\) of a multigraph \(G\), returns the multiplicity of the possibly multiple edge from \(u\) to \(v\). Returns 0 if \(u\) is not adjacent to \(v\).

Edges(u, v): GrphVert, GrphVert -> SeqEnum#: Given vertices \(u\) and \(v\) of a multigraph \(G\), returns all the edges from \(u\) to \(v\) as a sequence of elements of the edge-set of \(G\).

IncidentEdges(u): GrphVert -> SetEnum#: Given a vertex \(u\) of an undirected multigraph \(G\), returns all the edges incident to \(u\) as a set of elements of the edge-set of \(G\). If \(G\) is a multidigraph, the function returns all the edges incident to and from \(u\) as a set of elements of the edge-set of \(G\).

E ! < { u, v }, i >: GrphEdgeSet, < . > -> GrphEdge#: Given the edge-set \(E\) of the undirected multigraph \(G\) and objects \(u\), \(v\) belonging to the support of \(G\) corresponding to adjacent vertices, returns the edge from \(u\) to \(v\) which corresponds to the edge with index \(i\) in the adjacency list of \(G\). This requires that the edge at \(i\) in the adjacency list of \(G\) is an edge from \(u\) to \(v\).

E ! < [ u, v ], i >: GrphEdgeSet, < . > -> GrphEdge#: Given the edge-set \(E\) of the multidigraph \(G\) and objects \(u\), \(v\) belonging to the support of \(G\) corresponding to adjacent vertices, returns the edge from \(u\) to \(v\) which corresponds to the edge with index \(i\) in the adjacency list of \(G\). This requires that the edge at \(i\) in the adjacency list of \(G\) is an edge from \(u\) to \(v\).

E.i {E . i}: GrphEdgeSet, RngIntElt -> GrphEdge#

Let \(E\) be the edge-set of \(G\). If \(G\) is a simple graph (digraph) then this function is as described in Subsection Creating Edges and Vertices.

If \(G\) is a multigraph or multidigraph, then this function returns the edge at index \(i\) in the adjacency list of \(G\), provided \(i\) is a valid index.

EndVertices(e): GrphEdge -> { GrphVert, GrphVert }#
EndVertices(e): GrphEdge -> [ GrphVert, GrphVert ]#: Given an edge \(e\) in an undirected multigraph \(G\), returns the end vertices of \(e\) as a set of vertices \(\{u, v\}\). If \(G\) is a multidigraph, returns \(e\)’s end vertices as a sequence of vertices \([u, v]\).

InitialVertex(e): GrphEdge -> GrphVert#: Given an edge \(e = \{u, v\}\) or \(e = [u, v]\), returns 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 edge \(e = \{u, v\}\) or \(e = [u, v]\), returns vertex \(v\). This is useful in the undirected case since it indicates, where relevant, the direction in which the edge has been traversed.

Index(e): GrphEdge -> RngIntElt#: Given an edge \(e\) in a multi(di)graph \(G\), returns the index of \(e\) in the adjacency list of \(G\).

s eq t: GrphEdge, GrphEdge -> BoolElt#: Returns true if the edge \(s\) is equal to the edge \(t\). It \(s\) and \(t\) are edges in a multi(di)graph \(G\), returns true if and only if \(s\) and \(t\) have the same index in the adjacency list of \(G\).

Example: GrphMult Edges (ex-16c702)#

> G := MultiGraph< 3 | < 1, {2, 3} >, < 1, {2} >, < 2, {2, 3} > >;

Run in calculator

The graph \(G\) has a loop at vertex 2:

> Edges(G);
{@ < {1, 2}, 1 >, < {1, 2}, 5 >, < {1, 3}, 3 >, < {2, 2}, 7 >, < {2,
3}, 9 > @}
> E := EdgeSet(G);
> E.7;
< {2, 2}, 7 >
> assert InitialVertex(E.7) eq TerminalVertex(E.7);

Run in calculator

The graph \(G\) has a multiple edge from vertex 1 to vertex 2:

> u := VertexSet(G)!1;
> v := VertexSet(G)!2;
> I := EdgeIndices(u, v);
> I;
[ 5, 1 ]
> assert #I eq Multiplicity(u, v);
>
> E := EdgeSet(G);
> e1 := E!< { 1, 2 }, I[1] >;
> e2 := E!< { 1, 2 }, I[2] >;
> e1, e2;
< {1, 2}, 5 > < {1, 2}, 1 >
> EndVertices(e1);
{ 1, 2 }
> EndVertices(e2);
{ 1, 2 }
> assert Index(e1) eq I[1];
> assert Index(e2) eq I[2];
>
> assert e1 eq E.I[1];
> assert not e2 eq E.I[1];
> assert e2 eq E.I[2];
> assert not e1 eq E.I[2];

Run in calculator

We have seen that these two edges can be accessed directly:

> Edges(u, v);
[ < {1, 2}, 5 >, < {1, 2}, 1 > ]

Run in calculator