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.
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 = \lbrace @ v_1, v_2, \ldots, v_n @ \rbrace\) (where \(v_i = i\) for each \(i\) if the first form of the constructor is used, or the \(i\)th element of the enumerated or indexed set \(S\) otherwise), and edge-set \(E = \lbrace e_1, e_2, \ldots, e_q \rbrace\). 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 \(\{v_i, v_j\}\) of vertices in \(V\). The undirected edge \(\{v_i, v_j\}\) from \(v_i\) to \(v_j\) will be added to the edge-set for \(G\).
- (b)
A tuple of the form \(\langle v_i, N_i \rangle\) where \(N_i\) will be interpreted as a set of neighbours for the vertex \(v_i\). The elements of the sets \(N_i\) must be elements of \(V\). If \(N_i = \lbrace u_1, u_2, \ldots, u_r \rbrace\), the edges \(\{v_i, u_1\}, \ldots, \{v_i, u_r\}\) will be added to \(G\).
- (c)
A sequence \([ N_1, N_2, \ldots, N_n ]\) of \(n\) sets, where \(N_i\) will be interpreted as a set of neighbours for the vertex \(v_i\). The edges \(\{v_i, u_i\}\), \(u_i \in N_i\), 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 \(\{v_i, v_j\}\) of vertices in \(V\).
- (ii)
Tuples of the form \(\langle v_i, N_i \rangle\) where \(N_i\) will be interpreted as a set of neighbours for the vertex \(v_i\).
- (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 \(\langle v_i, N_i \rangle\) where \(N_i\) will be interpreted as a set of neighbours for the vertex \(v_i\).
- Example: GrphMultUnd Constr (ex-3c3311)#
> 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 = \lbrace @ v_1, v_2, \ldots, v_n @ \rbrace\) (where \(v_i = i\) for each \(i\) if the first form of the constructor is used, or the \(i\)th element of the enumerated or indexed set \(S\) otherwise), and edge-set \(E = \lbrace e_1, e_2, \ldots, e_q \rbrace\). 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 \([v_i, v_j]\) of vertices in \(V\). The directed edge \([v_i, v_j]\) from \(v_i\) to \(v_j\) will be added to the edge-set for \(G\).
- (b)
A tuple of the form \(\langle v_i, N_i \rangle\) where \(N_i\) will be interpreted as a set of out-neighbours for the vertex \(v_i\). The elements of the sets \(N_i\) must be elements of \(V\). If \(N_i = \lbrace u_1, u_2, \ldots, u_r \rbrace\), the edges \([v_i, u_1], \ldots, [v_i, u_r]\) will be added to \(G\).
- (c)
A sequence \([ N_1, N_2, \ldots, N_n ]\) of \(n\) sets, where \(N_i\) will be interpreted as a set of out-neighbours for the vertex \(v_i\). All the edges \([v_i, u_i]\), \(u_i \in N_i\), 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 \([v_i, v_j]\) of vertices in \(V\).
- (ii)
Tuples of the form \(\langle v_i, N_i \rangle\) where \(N_i\) will be interpreted as a set of out-neighbours for the vertex \(v_i\).
- (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 \(\langle v_i, N_i \rangle\) where \(N_i\) will be interpreted as a set of out-neighbours for the vertex \(v_i\).
- Example: GrphMultDir Constr (ex-f50793)#
> 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 Example: GrphMultUnd Constr and Example: GrphMultDir Constr.
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 \(\lbrace @ 1, \ldots, n @ \rbrace\) 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: GrphMult Support (ex-256013)#
> 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 ;