Other meanings of Multigraph
Mathematics
In graph theory, a multigraph is a graph in which multiple edges (also called parallel edges) are allowed between the same pair of vertices. Unlike a simple graph, where at most one edge connects any two vertices, a multigraph permits two or more edges to share the same endpoints, and it may also allow loops (edges connecting a vertex to itself) depending on the definition. Multigraphs are used to model situations where multiple relationships, connections, or interactions occur between the same entities, such as in transportation networks, electrical circuits, and social networks.
A multigraph is formally defined as an ordered pair (V, E) where V is a set of vertices and E is a multiset of edges, each edge being an unordered pair of vertices (or a pair (v,v) for a loop). The key distinction from a simple graph is that E is a multiset, allowing duplicate edges. Some authors require that multigraphs have no loops, while others allow them; when loops are allowed, the term 'pseudograph' is sometimes used. In the context of network analysis, multigraphs are also called 'parallel-edge graphs' or 'multi-networks'.
The concept of multigraphs emerged in the 19th century with the work of Leonhard Euler on the Seven Bridges of Königsberg, which is often considered the origin of graph theory. Euler's 1736 solution implicitly allowed multiple bridges between landmasses, effectively modeling a multigraph. Later, in the 1840s, Gustav Kirchhoff used multigraphs to analyze electrical networks, where multiple resistors or wires could connect the same pair of nodes. The formal study of multigraphs as a distinct object gained momentum in the 20th century with the development of algebraic graph theory and the work of mathematicians such as Frank Harary.
Multigraphs are widely used in computer science and engineering. In telecommunications, they model networks with multiple physical links between nodes, such as fiber-optic cables or wireless channels. In transportation, road networks with multiple parallel routes between cities are naturally represented as multigraphs. In social network analysis, multigraphs capture multiple types of relationships (e.g., friendship, family, work) between the same individuals. In chemistry, molecular graphs can be multigraphs when atoms are connected by multiple bonds, such as double or triple bonds.
One lesser-known aspect is the role of multigraphs in the study of graph minors and the graph minor theorem, where multigraphs arise naturally in the context of matroids. Another is the use of multigraphs in the design of fault-tolerant networks, where redundant edges ensure connectivity even if some edges fail. In combinatorics, multigraphs are central to the concept of the 'edge chromatic number', which can be higher than the maximum degree due to parallel edges. Additionally, multigraphs appear in the study of random graphs, where the configuration model generates multigraphs with a given degree sequence, and these are used to approximate real-world networks.
Multigraphs are a fundamental generalization of simple graphs, enabling the modeling of parallel relationships and redundant connections across diverse fields.
Help improve the encyclopedia. Reports go straight to the site manager.