Multigraph

Multi-pseudograph

Multigraph

A multigraph is a type of graph in the field of graph theory. Unlike a simple graph, a multigraph is allowed to have multiple edges, also known as parallel edges, between the same pair of vertices. These multiple edges can represent different relationships or interactions between the vertices.

Definition

Formally, a multigraph is defined as an ordered pair \( G = (V, E) \), where:

• \( V \) is a set of vertices.
• \( E \) is a multiset of unordered pairs of vertices, called edges.

In a multigraph, the edges are not required to be unique, meaning that two or more edges can connect the same pair of vertices. This is in contrast to a simple graph, where each pair of vertices is connected by at most one edge.

Types of Multigraphs

Multigraphs can be classified into different types based on their properties:

• Undirected Multigraph: A multigraph where the edges do not have a direction.
• Directed Multigraph: Also known as a multidigraph, where each edge has a direction, represented as an ordered pair of vertices.

Applications

Multigraphs are used in various fields to model complex systems with multiple relationships. Some common applications include:

• Transportation networks, where multiple routes can exist between two locations.
• Communication networks, where multiple communication channels can exist between two nodes.
• Social networks, where multiple types of relationships (e.g., friendship, collaboration) can exist between individuals.

Related Concepts

• Graph (discrete mathematics)
• Simple graph
• Directed graph
• Weighted graph
• Graph theory

See Also

• Graph theory
• Graph (discrete mathematics)
• Simple graph
• Directed graph
• Weighted graph