Simple Graphs and Multigraphs
What you'll learn: You'll understand the difference between graphs that allow at most one edge between any two vertices versus graphs that permit multiple edges or self-loops.
The Core Distinction
Now that you understand graphs have vertices and edges, it's time to learn that not all graphs follow the same rules about connections.
A simple graph is the most restricted type: between any pair of vertices, there can be at most one edge, and vertices cannot have edges to themselves (no loops). Think of this like a professional network where you're either connected to someone or you're not—there's no concept of being "double-connected."
A multigraph relaxes these restrictions: it allows multiple edges between the same pair of vertices, and some variants permit self-loops (edges from a vertex back to itself).
Real-World Analogy
Imagine a city transportation map:
- Simple graph: A map showing whether two cities are connected by any road. Either there's a connection or there isn't.
- Multigraph: A realistic map showing that two cities might be connected by multiple highways, a train line, and a ferry route—each represented as a separate edge.
Similarly, a flight network is a multigraph because airlines often run multiple daily flights between major cities (multiple edges), and a self-loop could represent a scenic tour flight that departs and returns to the same airport.
Why It Matters
The distinction affects how you implement and traverse graphs. Simple graphs are easier to represent (you only track whether an edge exists), while multigraphs require counting or distinguishing between multiple connections.
Key Takeaway: Simple graphs allow at most one edge per vertex pair with no self-loops, while multigraphs permit multiple edges between vertices and sometimes self-loops.