---
title: "Construction of Multigraphs"
canonical: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/multig-constr.html"
source: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/multig-constr.md"
part: "Combinatorics"
chapter: "Multigraphs"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Combinatorics", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/index-combinatorics.md"}
  - {"title": "Multigraphs", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/index-multigraphs.md"}
prev: {"title": "Introduction", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/multig-introduction.md"}
next: {"title": "The Vertex–Set and Edge–Set of Multigraphs", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/multig-vertex-edge-set.md"}
intrinsics:
  - {"name": "MultiGraph", "signature": "MultiGraph<n | edges >: RngIntElt, List -> GrphMultUnd, GrphVertSet, GrphEdgeSet"}
  - {"name": "MultiGraph", "signature": "MultiGraph<S | edges >: SetEnum, List -> GrphMultUnd, GrphVertSet, GrphEdgeSet"}
  - {"name": "MultiGraph", "signature": "MultiGraph<S | edges >: SetIndx, List -> GrphMultUnd, GrphVertSet, GrphEdgeSet"}
  - {"name": "MultiDigraph", "signature": "MultiDigraph<n | edges >: RngIntElt, List -> GrphMultDir, GrphVertSet, GrphEdgeSet"}
  - {"name": "MultiDigraph", "signature": "MultiDigraph<S | edges >: SetEnum, List -> GrphMultDir, GrphVertSet, GrphEdgeSet"}
  - {"name": "MultiDigraph", "signature": "MultiDigraph<S | edges >: SetIndx, List -> GrphMultDir, GrphVertSet, GrphEdgeSet"}
  - {"name": "Support", "signature": "Support(G): GrphMult -> SetIndx"}
  - {"name": "Support", "signature": "Support(V): GrphVertSet -> SetIndx"}
  - {"name": "ChangeSupport", "signature": "ChangeSupport(G, S): GrphMult, SetIndx -> GrphMult, GrphVertSet, GrphEdgeSet"}
  - {"name": "ChangeSupport", "signature": "ChangeSupport(~G, S): GrphMult, SetIndx"}
  - {"name": "StandardGraph", "signature": "StandardGraph(G): GrphMult -> GrphMult"}
examples:
  - "ex-3c3311"
  - "ex-f50793"
  - "ex-256013"
---

# 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](https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/graph-digraph.md#graph-subsec-graph-size) in Chapter [Graphs](https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/index-graphs.md#graph) for more details.

<a id="multig-undconstr"></a>
<a id="multigraph-subsec-und-constr"></a>
## Construction of a General Multigraph

Undirected multigraphs are constructed in a similar way to graphs (Subsection [Construction of a General Graph](https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/graph-digraph.md#graph-subsec-graph)).

<a id="constructor-constructor-multigraph-rngintelt-list-grphmultund-grphvertset-grphedgeset"></a>
### `MultiGraph<n | edges >: RngIntElt, List -> GrphMultUnd, GrphVertSet, GrphEdgeSet`

<a id="constructor-constructor-multigraph-setenum-list-grphmultund-grphvertset-grphedgeset"></a>
### `MultiGraph<S | edges >: SetEnum, List -> GrphMultUnd, GrphVertSet, GrphEdgeSet`

<a id="constructor-constructor-multigraph-setindx-list-grphmultund-grphvertset-grphedgeset"></a>
### `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$.

<a id="example-ex-3c3311"></a>
### `Example: Constructing a Multigraph (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 ;
```

<a id="multig-dirconstr"></a>
<a id="multigraph-subsec-dir-constr"></a>
## Construction of a General Multidigraph

Multidigraphs are constructed in the same way as digraphs (Subsection [Construction of a General Digraph](https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/graph-digraph.md#graph-subsec-digraph)).

<a id="constructor-constructor-multidigraph-rngintelt-list-grphmultdir-grphvertset-grphedgeset"></a>
### `MultiDigraph<n | edges >: RngIntElt, List -> GrphMultDir, GrphVertSet, GrphEdgeSet`

<a id="constructor-constructor-multidigraph-setenum-list-grphmultdir-grphvertset-grphedgeset"></a>
### `MultiDigraph<S | edges >: SetEnum, List -> GrphMultDir, GrphVertSet, GrphEdgeSet`

<a id="constructor-constructor-multidigraph-setindx-list-grphmultdir-grphvertset-grphedgeset"></a>
### `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$.

<a id="example-ex-f50793"></a>
### `Example: Constructing a Multidigraph (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       ;
```

<a id="printing-of-a-multi-di-graph"></a>
<a id="multi-print"></a>
<a id="multigraph-subsec-multi-print"></a>
## 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 [Constructing a Multigraph](https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/multig-constr.md#example-ex-3c3311) and [Constructing a Multidigraph](https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/multig-constr.md#example-ex-f50793).

<a id="multig-support"></a>
<a id="multigraph-subsec-support"></a>
## 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](https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/graph-digraph.md#graph-subsec-support)).

<a id="function-support-grphmult"></a>
### `Support(G): GrphMult -> SetIndx`

<a id="function-support-grphvertset"></a>
### `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.

<a id="function-changesupport-grphmult-setindx"></a>
### `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](https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/multig-decorations.md#multigraph-subsec-vertex-decs) and [Edge Decorations](https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/multig-decorations.md#multigraph-subsec-edge-decs)).

<a id="procedure-changesupport-grphmult-setindx-ref"></a>
### `ChangeSupport(~G, S): GrphMult, SetIndx`

The procedural version of the above function.

<a id="function-standardgraph-grphmult"></a>
### `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$.

<a id="example-ex-256013"></a>
### `Example: Support of a Multigraph (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 ;
```
