# Introduction

A *simple graph* is a graph in which each edge joins two distinct vertices and two distinct vertices are joined by at most one edge. A *simple digraph*, whose edges are directed, is defined in an analogous manner. Thus, loops and multiple edges are not permitted in simple graphs and simple digraphs. A graph (digraph) with loops and/or multiple edges joining a fixed pair of vertices is called a *multigraph* (resp. *multidigraph*). A multidigraph whose edges are assigned a capacity is more commonly called a *network*.

In this chapter the term “graph” is used when referring to a simple undirected graph, while the term “digraph” is used when referring to a simple directed graph. Sometimes the term “graph” is used as the generic term for the incidence structure on vertices and edges. Such uses should be clear from the context in which they occur.

There are five Magma graph objects: the undirected simple graph of type `GrphUnd`, the directed simple graph of type `GrphDir`, the undirected multigraph of type `GrphMultUnd`, the directed multigraph of type `GrphMultDir`, and the network of type `GrphNet`. The simple graphs are all of type `Grph`, while the multigraphs (including the network) are of type `GrphMult`. There is a caveat here with respect to simple digraphs and loops: for historical reasons, Magma allows loops in digraphs.

Simple graphs and digraphs are covered in this chapter, while multigraphs, multidigraphs are covered in Chapter [Multigraphs](../Multigraphs/index-multigraphs.md#multigraph) and networks in Chapter [Networks](../Networks/index-networks.md#network). All types of graphs may have vertex labellings and/or edge labellings. In addition, assigning weights and/or capacities to graph edges is also possible, thus allowing to run shortest-paths and flow-based algorithms over the graphs.

Importantly, from the present version (V2.11) onwards, all the standard graph construction functions (see Subsections [Subgraphs and Quotient Graphs](operation.md#graph-subsec-subsup) and [Incremental Construction of Graphs](operation.md#graph-subsec-incr)) respect the graph’s support set and vertex and edge decorations. That is, the resulting graph will have a support set and vertex and edge decorations compatible with the original graph and the operation performed on that graph.

Magma employs two distinct data structures for representing graphs. A graph may be represented in the form of an adjacency matrix (the dense representation) or in the form of an adjacency list (the sparse representation). The latter is better suited for sparse graphs and for algorithms which have been designed with the adjacency list representation in mind. An advantage of the sparse representation is the possibility of creating much larger (sparse) graphs than would be possible using the dense representation, since memory requirements for the adjacency list representation is linear in the number of edges, while memory requirements for the adjacency matrix representation is quadratic in the number of vertices (order) of the graph. This is covered in detail in Section [Bounds on the Graph Order](graph-digraph.md#graph-subsec-graph-size).

Further, multigraphs and multidigraphs (and networks) may only be represented by an adjacency list since they may contain multiple edges. Users have control over the choice of representation when creating simple graphs or digraphs. If no indication is given, simple graphs and digraphs are *always* created with the dense representation. At the time of the present release (V2.11), a significant part of Magma functions are able to work directly with either of the representations. However, wherever necessary, a graph will be converted internally to whichever representation is required by a given function. We emphasize that this process is completely transparent to users and *requires no intervention on their part*.

For a concise and comprehensive overview on graph theory and algorithms, the reader is referred to [[Even, 1979](../../references.md#cite-even)]; in [[T.H. Cormen and Rivest, 1990](../../references.md#cite-corleiri)] they’ll find a clear exposure of some graph algorithms, and [[Ahuja *et al.*, 1993](../../references.md#cite-amo)] is the recommended reference for flow problems in graphs.