multigraphen

Multigraphen, commonly known as multigraph, is a graph-theoretic structure that generalizes a graph by allowing multiple edges between the same pair of vertices. In the undirected form, a multigraph consists of a set V of vertices and a multiset E of edges, where each edge connects two vertices. In the directed form, edges are ordered pairs and multiple edges from one vertex to another are permitted. Some conventions also allow loops, edges that start and end at the same vertex; in many texts such objects are called pseudographs.

Formally, an undirected multigraph is G = (V, E) with V finite and E a multiset of unordered pairs of vertices. A directed multigraph is G = (V, A) where A is a multiset of ordered pairs from V x V. The multiplicity mu(u,v) (undirected) or mu(u,v) (directed) records how many parallel edges join u and v (or go from u to v).

Some properties depend on conventions about loops. If loops are allowed, a loop at vertex v contributes two to the degree of v in the undirected case, while in a directed multigraph a loop contributes one to both in-degree and out-degree. A simple graph is a special case of a multigraph with at most one edge between any pair of distinct vertices and no loops; other terms such as pseudograph are used for variants that allow loops and parallel edges.

Applications include modeling networks with multiple connections, such as transportation or communication networks where several parallel channels exist between locations. Multigraphs are studied in graph algorithms, spectral theory, and network science, where edge multiplicities influence traversal, flow, and connectivity. Conceptually, a multigraph reduces to a simple graph by collapsing parallel edges and removing loops.