Multigraphs and multidigraphs are graphs and digraphs which may have multiple (i.e., parallel) edges and loops. This is in contrast to simple graphs (see Section Introduction in the chapter on graphs). In the context of this chapter we use the term "graph" as a generic term for the general vertex-edge incident structure, and the term "multigraph" as a generic term whenever we want to emphasize the possible existence of multiple edges and loops. Thus, graphs and multigraphs may be directed or undirected. The meaning of the terms "graph" and "multigraph" should be made clear from the context in which they occur.
Multigraphs are represented in the form of an adjacency list; for more information on this topic we refer the reader to Section Graphs with a Sparse Representation. As is the case for simple graphs, the vertices and edges of a multigraph may be given "decorations". More precisely, they may be labelled; in addition the edges may also be assigned a capacity (if one is interested in flow problems) and/or a weight (for investigation of shortest path problems).
For convenience, Magma provides users with networks: in the Magma context, a network is understood as being a multidigraph whose edges are always given a capacity. Any Magma function that takes a network as an argument will usually take any graph whose edges have a capacity as an argument. Networks are covered in Chapter NETWORKS; a few functionalities specific to networks will, however, be discussed in the general multigraph context whenever there is a need to highlight some differences between networks and general multi(di)graphs.
In particular, almost all the standard graph construction functions (see Section Standard Construction for Multigraphs) preserve the graph's support set and vertex and edge decorations. That is, the resulting graph will have a support and vertex and edge decorations compatible with the original graph and the operation performed on that graph.
A Magma multigraph object has type GrphMultUnd, a multidigraph has type GrphMultDir, and a network has type GrphNet. All three objects are of type GrphMult.
The multigraph facilities represent a significant subset of the (simple) graph functionality. Consequently, some sections of this chapter are very similar to their counterparts in Chapter GRAPHS. For the sake of clarity, this chapter describes the complete multigraph functionality.