multigraph

A multigraph is a graph that allows multiple edges between the same pair of vertices. In addition, many definitions permit loops, which are edges whose endpoints are the same vertex. If a graph forbids both parallel edges and loops, it is called a simple graph; when loops or parallel edges are allowed, it is often described as a multigraph, though some sources reserve the term “pseudograph” for graphs that may include loops.

Formally, a multigraph G = (V, E) consists of a set V of vertices and a multiset E of edges, where each edge is an unordered pair of vertices from V. If loops are allowed, an edge may be of the form (v, v). The multiplicity of a given pair {u, v} is the number of distinct edges joining u and v. Edges are counted with multiplicity, so a pair of vertices can be connected by more than one edge.

The degree of a vertex v in a multigraph is the sum of the multiplicities of all edges incident to v; a loop at v contributes twice to deg(v) because it touches v in two incidences. Concepts such as paths, cycles, and connectivity extend from simple graphs to multigraphs, with the understanding that multiple edges provide additional routes between vertices.

Common representations include the adjacency matrix A, where A[u, v] records the number of edges between u and v (and A[v, v] counts loops), and the edge list, which may contain duplicate entries for parallel edges.

Applications of multigraphs appear in transportation and communication networks, where multiple channels or routes can connect the same locations, and in various models where redundancy or parallel relations are intrinsic.