# 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](../Graphs/graph-digraph.md#graph-subsec-graph-size) in Chapter [Graphs](../Graphs/index-graphs.md#graph) for more details. ## Construction of a General Multigraph Undirected multigraphs are constructed in a similar way to graphs (Subsection [Construction of a General Graph](../Graphs/graph-digraph.md#graph-subsec-graph)). ### `MultiGraph: RngIntElt, List -> GrphMultUnd, GrphVertSet, GrphEdgeSet` ### `MultiGraph: SetEnum, List -> GrphMultUnd, GrphVertSet, GrphEdgeSet` ### `MultiGraph: 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)` ```magma > 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](../Graphs/graph-digraph.md#graph-subsec-digraph)). ### `MultiDigraph: RngIntElt, List -> GrphMultDir, GrphVertSet, GrphEdgeSet` ### `MultiDigraph: SetEnum, List -> GrphMultDir, GrphVertSet, GrphEdgeSet` ### `MultiDigraph: 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)` ```magma > 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](#example-ex-3c3311) and [Example: GrphMultDir Constr](#example-ex-f50793). ## 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](../Graphs/graph-digraph.md#graph-subsec-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](multig-decorations.md#multigraph-subsec-vertex-decs) and [Edge Decorations](multig-decorations.md#multigraph-subsec-edge-decs)). ### `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)` ```magma > 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 ; ```