multiedges

A multiedge is an edge in a graph that connects the same pair of vertices as one or more other edges. In a multigraph, it is possible for two vertices to be joined by several distinct edges, rather than by a single edge as in a simple graph. The term parallel edges is commonly used to refer to multiple edges between the same endpoints, though terminology varies: some authors distinguish between a single edge that is one of several parallel edges and a separate concept of parallelism.

There are two common forms of multigraph. An undirected multigraph allows multiple undirected edges between the same pair of vertices. A directed multigraph (or multi-digraph) allows multiple directed edges, or arcs, from one vertex to another; both directions may be represented by distinct edges if needed. In many definitions, loops (edges that start and end at the same vertex) are allowed in a multigraph, while in others they are excluded; when loops are allowed, the graph is sometimes called a pseudograph.

Edge multiplicity, the number of parallel edges between a given pair of vertices, is a key characteristic. Data structures often store either multiple edge objects or a count of edges between vertex pairs. Adjacency matrices can encode multiplicity by placing the number of edges (or a weight) in the cell corresponding to the vertex pair; adjacency lists may include repeated entries or attach a multiplicity attribute to each neighbor pair.

Multiedges influence both theory and algorithms. Some algorithms for simple graphs extend to multigraphs by treating parallel edges separately or by considering the smallest/largest weight among parallel edges. Multigraph models are used in network design, transportation, circuit design, and various applications where multiple connections between the same components are relevant.