Construction of Multigraphs

In this implementation, the order n of a multigraph or multidigraph is bounded by 134217722. See Section Bounds on the Graph Order in Chapter GRAPHS for more details.

Contents

Construction of a General Multigraph

Undirected multigraphs are constructed in a similar way to graphs (Subsection Construction of a General Graph).

MultiGraph<n | edges > : RngIntElt, List -> GrphMultUnd, GrphVertSet, GrphEdgeSet
MultiGraph<S | edges > : SetEnum, List -> GrphMultUnd, GrphVertSet, GrphEdgeSet
MultiGraph<S | edges > : SetIndx, List -> GrphMultUnd, GrphVertSet, GrphEdgeSet
Construct the multigraph G with vertex-set V = {@ v1, v2, ..., vn @} (where vi = i for each i if the first form of the constructor is used, or the ith element of the enumerated or indexed set S otherwise), and edge-set E = { e1, e2, ..., eq }. This function returns three values: The multigraph G, the vertex-set V of G; and the edge-set E of G.

The elements of E are specified by the list edges, where the items of edges may be objects of the following types:

(a)
A pair {vi, vj} of vertices in V. The undirected edge {vi, vj} from vi to vj will be added to the edge-set for G.

(b)
A tuple of the form < vi, Ni > where Ni will be interpreted as a set of neighbours for the vertex vi. The elements of the sets Ni must be elements of V. If Ni = { u1, u2, ..., ur }, the edges {vi, u1}, ..., {vi, ur} will be added to G.

(c)
A sequence [ N1, N2, ..., Nn ] of n sets, where Ni will be interpreted as a set of neighbours for the vertex vi. The edges {vi, ui}, ui ∈Ni, are added to G.

In addition to these three basic ways of specifying the edges list, the items in edges may also be:

(d)
An edge e of a graph or digraph or multigraph or multidigraph or network of order n. If e is an edge from u to v, then the edge {u, v} is added to G.

(e)
An edge-set E of a graph or digraph or multigraph or multidigraph or network of order n. Every edge e in E will be added to G according to the rule set out for a single edge.

(f)
A graph or a digraph or a multigraph or a multidigraph or a network H of order n. Every edge e in H's edge-set is added to G according to the rule set out for a single edge.

(g)
A set of

(i)
Pairs of the form {vi, vj} of vertices in V.
(ii)
Tuples of the form < vi, Ni > where Ni will be interpreted as a set of neighbours for the vertex vi.
(iii)
Edges of a graph or digraph or multigraph or multidigraph or network of order n.
(iv)
Graphs or digraphs or multigraphs or multidigraphs or networks of order n.

(h)
A sequence of

(i)
Tuples of the form < vi, Ni > where Ni will be interpreted as a set of neighbours for the vertex vi.

Example MultiGraph_GrphMultUnd_Constr (H163E1)

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

1       2 3 2 ;
2       3 2 2 1 1 ;
3       2 1 ;

Construction of a General Multidigraph

Multidigraphs are constructed in the same way as digraphs (Subsection Construction of a General Digraph).

MultiDigraph<n | edges > : RngIntElt, List -> GrphMultDir, GrphVertSet, GrphEdgeSet
MultiDigraph<S | edges > : SetEnum, List -> GrphMultDir, GrphVertSet, GrphEdgeSet
MultiDigraph<S | edges > : SetIndx, List -> GrphMultDir, GrphVertSet, GrphEdgeSet
Construct the multidigraph G with vertex-set V = {@ v1, v2, ..., vn @} (where vi = i for each i if the first form of the constructor is used, or the ith element of the enumerated or indexed set S otherwise), and edge-set E = { e1, e2, ..., eq }. This function returns three values: The multidigraph G, the vertex-set V of G; and the edge-set E of G.

The elements of E are specified by the list edges, where the items of edges may be objects of the following types:

(a)
A pair [vi, vj] of vertices in V. The directed edge [vi, vj] from vi to vj will be added to the edge-set for G.

(b)
A tuple of the form < vi, Ni > where Ni will be interpreted as a set of out-neighbours for the vertex vi. The elements of the sets Ni must be elements of V. If Ni = { u1, u2, ..., ur }, the edges [vi, u1], ..., [vi, ur] will be added to G.

(c)
A sequence [ N1, N2, ..., Nn ] of n sets, where Ni will be interpreted as a set of out-neighbours for the vertex vi. All the edges [vi, ui], ui ∈Ni, are added to G.

In addition to these four basic ways of specifying the edges list, the items in edges may also be:

(d)
An edge e of a graph or digraph or multigraph or multidigraph or network of order n. If e is an edge from u to v, then the edge [u, v] is added to G. Thus, if e is an undirected edge from u to v, both edges [u, v] and [v, u] are added to G.

(e)
An edge-set E of a graph or digraph or multigraph or multidigraph or network of order n. Every edge e in E will be added to G according to the rule set out for a single edge.

(f)
A graph or a digraph or a multigraph or a multidigraph or a network H of order n. Every edge e in H's edge-set is added to G according to the rule set out for a single edge.

(g)
A set of

(i)
Pairs of the form [vi, vj] of vertices in V.
(ii)
Tuples of the form < vi, Ni > where Ni will be interpreted as a set of out-neighbours for the vertex vi.
(iii)
Edges of a graph or digraph or multigraph or multidigraph or network of order n.
(iv)
Graphs or digraphs or multigraphs or multidigraphs or networks of order n.

(h)
A sequence of

(i)
Tuples of the form < vi, Ni > where Ni will be interpreted as a set of out-neighbours for the vertex vi.

Example MultiGraph_GrphMultDir_Constr (H163E2)

> G := MultiDigraph< 3 | < 1, {2, 3} >, < 1, {2} >, < 2, {2, 3} > >;
> G; 
Multidigraph
Vertex  Neighbours

1       2 3 2 ;
2       3 2 ;
3       ;

Printing of a Multi(di)graph

A multi(di)graph is displayed by listing, for each vertex, all of its adjacent vertices. If the multigraph has multiple edges from u to v, then the adjacency list of u contains as many copies of the vertex v as there are edges from u to v.

The vertices in the adjacency list are not ordered, they appear in the order in which they were created. See the previous examples H163E1 and H163E2.

Operations on the Support

The support of a multi(di)graph is subject to exactly the same operations as simple graphs (see Subsection Operations on the Support).

Support(G) : GrphMult -> SetIndx
Support(V) : GrphVertSet -> SetIndx
The indexed set used in the construction of G (or the graph for which V is the vertex-set), or the standard set {@ 1, ..., n @} if it was not given.
ChangeSupport(G, S) : GrphMult, SetIndx -> GrphMult, GrphVertSet, GrphEdgeSet
If G is a graph having n vertices and S is an indexed set of cardinality n, return a new graph H equal to G but whose support is S. That is, H is structurally equal to G and its vertex and edge decorations are the same as those for G (see Sections Vertex Decorations: Labels and Edge Decorations).
ChangeSupport(~G, S) : GrphMult, SetIndx ->
The procedural version of the above function.
StandardGraph(G) : GrphMult -> GrphMult
Returns a graph H that is isomorphic to G but defined on the standard support. That is, H is structurally equal to G and its vertex and edge decorations are the same as those for G.

Example MultiGraph_GrphMult_Support (H163E3)

> S := {@ "a", "b", "c" @};
> G := MultiGraph< S | < 1, {2, 3} >, < 1, {2} >, < 2, {2, 3} > >;
> G;
Multigraph
Vertex  Neighbours

c       b a b ;
b       a b b c c ;
a       b c ;

> StandardGraph(G);
Multigraph
Vertex  Neighbours

1       2 3 2 ;
2       3 2 2 1 1 ;
3       2 1 ;
[Next][Prev] [Right] [Left] [Up] [Index] [Root]


Version: V2.29 of Fri Nov 28 15:14:01 AEDT 2025
Search: