Multigraph

Imagine drawing dots on a page.

You can draw lines to join them.

In a multigraph, dots can have many lines between them.

Some lines might even go back to the same dot.

These lines are called edges.

Some people call these special graphs pseudographs.

This helps show many ways to get from one place to another.

It is a fun way to see paths.

Imagine you have dots on a paper. We call these dots vertices. You can draw lines to join the dots. These lines are called edges.

In most graphs, you only draw one line between two dots. But a multigraph is different. In a multigraph, you can draw many edges between the same two vertices. This shows there are many ways to get from one place to another. Some edges might even connect a dot to itself. These are called loops. Some math books call a multigraph with loops a pseudograph.

Edges can also have a direction. This is called a directed multigraph. You can think of these like arrows. They show you must go from one dot to another. An airline might use this to show flights. One arrow goes from City A to City B. Another arrow goes from City B back to City A.

There are also labeled multigraphs. This means you can give each dot and each edge a name or a label. This helps people keep track of different paths in a big group of dots.

Imagine you are looking at a map of several cities. Each city is a dot, which mathematicians call a vertex. To show how you can travel, you draw lines between these dots. These lines are called edges. In a simple graph, you only draw one line between two cities. But sometimes, there is more than one way to travel between the same two places. A multigraph is a special kind of graph that allows this. It lets you draw many edges between the same two vertices.

There are two main ways to think about these extra edges. In the first way, the edges do not have their own names. We only care about which two dots they connect. In the second way, every edge is its own separate thing. This means each edge has its own identity, just like the dots do. Some people also allow loops in a multigraph. A loop is an edge that connects a dot to itself. Some math books call a multigraph with loops a pseudograph.

Math rules can change depending on which author you read. For example, Balakrishnan wrote about this in 1997. Chartrand and Zhang also wrote about these ideas in 2012. These experts have different ways of defining what a multigraph is. Some say a multigraph cannot have loops at all. They use the word pseudograph to describe a graph that does have loops. Other writers, like Bollobás in 2002 or Diestel in 2010, allow loops. Wilson also wrote about these different definitions in 2002.

Sometimes, edges have a specific direction, like an arrow. This is called a directed multigraph, or sometimes a quiver. You can use these to show how things move in one way. An airline might use this to model flight connections between cities. One arrow shows a flight going from City A to City B. Another arrow shows a flight going from City B back to City A. This helps show all the possible paths a plane can take.

You can also add labels to your multigraph. A labeled multidigraph has names for its vertices and its arcs. This means you can give every dot and every arrow a specific label. This is helpful when you need to keep track of many different paths. It is like giving every person and every road a unique name on a map. This makes it much easier to study how everything is connected.

In the field of graph theory, mathematicians use models to represent connections between objects. A standard graph typically shows a single connection between any two points. However, a multigraph is a more complex structure that allows for multiple connections between the same points. These connections are called multiple edges, or sometimes parallel edges. This type of graph is essential for modeling systems where more than one relationship exists between two entities.

To understand how a multigraph works, we must look at its two main components. The first component is a set of vertices, which are the individual points or nodes. The second component is a set of edges, which are the lines connecting those nodes. In a multigraph, the edges can connect the same two vertices more than once. There are two distinct ways to define these edges. In one view, edges lack their own identity and are defined only by the nodes they connect. In the other view, edges are primitive entities with their own unique identities, just like the nodes themselves.

Mathematicians categorize these structures into several specific types. An undirected multigraph is one where the edges do not have a specific direction. If the edges have their own identity, the graph is defined as an ordered triple containing the vertices, the edges, and a function that assigns each edge to its two endpoints. Another type is the directed multigraph, often called a multidigraph. In a multidigraph, the edges are called arcs or arrows because they have a specific source and a specific target. A mixed multigraph combines both undirected edges and directed arcs within the same system.

There is often disagreement among mathematicians regarding the use of loops. A loop is an edge that connects a vertex to itself. Some authors, such as Bollobás in 2002 or Diestel in 2010, allow multigraphs to include these loops. However, other writers like Wilson in 2002 or Chartrand and Zhang in 2012 use different terminology. These authors often reserve the term multigraph for structures without loops. They instead use the term pseudograph to describe a multigraph that is permitted to have loops.

Directed multigraphs serve very practical purposes in real-world modeling. One common example is the modeling of airline flight connections. An airline might use a multidigraph to represent the possible paths between different cities. In this model, the vertices represent cities and the arcs represent specific flights. To show that a plane can fly both to and from a location, the graph would use pairs of directed parallel edges. This allows the model to show the specific direction of travel for every connection.

In the advanced field of category theory, these structures become even more specialized. A small category can be defined as a multidigraph where the edges have their own identity. This specific type of multidigraph must also include an associative composition law. Additionally, it requires a distinguished self-loop at every vertex to serve as an identity for composition. Because of this deep connection, experts in category theory often use the term "graph" to mean a multidigraph. They refer to the underlying structure as an underlying digraph.

Finally, multigraphs can be enhanced through a process called labeling. A labeled multidigraph is a structure where both the vertices and the arcs have specific labels. Formally, this is described as an eight-tuple that includes sets for vertices and arcs, as well as alphabets for their labels. These labels are applied through specific maps that describe the identity of each part. This allows researchers to track highly complex networks where every single connection and node has a unique name or value.