Multigraphs and Weighted Graphs

Definition

A multigraph is a graph in which more than one edge may connect the same pair of vertices. These repeated edges are called parallel edges. In many textbook definitions, a multigraph may also contain loops, which are edges that start and end at the same vertex.

A weighted graph is a graph in which each edge is associated with a numerical or descriptive value called a weight. The weight may represent distance, cost, time, length, capacity, reliability, or any other quantity relevant to the problem.

Example of a multigraph: If vertices $A$ and $B$ are connected by two different roads, then the graph may have two distinct edges between $A$ and $B$.

Example of a weighted graph: If edge $AB$ has weight 5, it may mean that the distance between $A$ and $B$ is 5 km.

Main Content

1. Multigraphs

Structure and meaning

• A multigraph extends the idea of a simple graph by allowing multiple edges between the same pair of vertices.
• It is useful when the relationship between two objects is not unique. For example, two computers may be connected by multiple network cables, or two towns may have several roads between them.
• Depending on the convention used, multigraphs may also allow loops, which are edges from a vertex back to itself.
• Parallel edges are treated as separate edges even if they connect the same vertices.

Representation and example

• Suppose the vertex set is $V = \{A, B, C\}$.
• If there are two edges between $A$ and $B$, one edge between $B$ and $C$, and one loop at $C$, then the graph is a multigraph.
• A simple ASCII sketch for this situation:

A == B --- C
          ↺

• Here, == indicates two parallel edges between $A$ and $B$, and the curved arrow indicates a loop at $C$.

2. Weighted Graphs

Edge weights and interpretation

• In a weighted graph, each edge has a number or label attached to it.
• The weight may represent different things depending on the application:
  • distance between cities,
  • time taken to travel,
  • cost of communication,
  • bandwidth of a network link,
  • risk level in a decision model.
• The graph itself may be directed or undirected, simple or multigraph-like, but the key feature is the presence of weights.

Example and notation

• Consider a graph with vertices $A$, $B$, and $C$.
• If edge $AB$ has weight 4, edge $BC$ has weight 7, and edge $AC$ has weight 2, then the weighted graph can be written as:
  • $AB(4)$
  • $BC(7)$
  • $AC(2)$
• A simple diagram:

A ---4--- B
 \       /
  2     7
   \   /
     C

• The numbers on edges show their weights.

3. Relationship, Uses, and Mathematical Importance

How multigraphs and weighted graphs differ

• A multigraph focuses on the number of connections between vertices.
• A weighted graph focuses on the value or cost of each connection.
• A graph can be both a multigraph and a weighted graph if it has multiple edges and each edge has a weight.
• Example: Two roads between the same cities may have different distances. This is both a multigraph situation and a weighted graph situation.

Why they matter in graph theory

• Many algorithms and theorems are first developed for simple graphs but can be adapted for multigraphs and weighted graphs.
• Weighted graphs are essential for shortest path problems such as finding the minimum travel distance.
• Multigraphs are important in networks where redundancy or repeated connections exist.
• These graph types help model real systems more accurately than simple graphs.

Working / Process

1. Identify the type of graph needed

• Decide whether the problem involves repeated edges, numerical costs, or both.
• If there are multiple connections between the same vertices, use a multigraph.
• If each edge has a measurement like distance or cost, use a weighted graph.
• If both conditions are present, use a weighted multigraph.

2. Construct the graph correctly

• List all vertices first.
• Draw edges carefully:
  • use separate parallel lines for multiple edges,
  • use a loop if allowed and needed,
  • write weights near each edge.
• Make sure each edge is distinguishable when more than one edge joins the same vertices.

3. Use the graph for analysis

• Apply graph concepts such as degree, path, cycle, connectivity, shortest path, or spanning tree.
• For weighted graphs, compare total weights to find the least-cost route or optimal solution.
• For multigraphs, count all edges accurately, including parallel edges and loops if they are part of the definition.
• Interpret results in the context of the application, such as traffic flow, communication cost, or network reliability.

Advantages / Applications

More realistic modeling of real-world systems

• Multigraphs model situations with multiple links between the same nodes, such as several roads, flight routes, or communication channels.
• Weighted graphs represent practical quantities like distance, time, cost, or capacity.

Useful in optimization and algorithms

• Weighted graphs are used in shortest path algorithms, minimum spanning trees, and network routing.
• Multigraphs help in studying networks with redundant or repeated connections, which is useful in reliability analysis and transport planning.

Wide range of applications

• Transportation networks: roads, railways, airline routes.
• Computer networks: multiple cables or parallel communication links.
• Social networks: repeated interactions or different types of relationships.
• Electrical circuits and logistics: path costs, loads, and capacities.
• Operations research: efficient movement of goods and resources.

Summary

• Multigraphs allow multiple edges between the same pair of vertices and sometimes loops.
• Weighted graphs assign values to edges to represent distance, cost, time, or other measures.
• Both concepts make graph models more practical and powerful for real-world problems.