Simple Graphs and Multigraphs
You'll learn: How graphs differ based on whether they allow multiple edges between the same pair of vertices.
The Core Distinction
In graph theory, we classify graphs by how "strict" their edge rules are.
A simple graph allows at most one edge between any pair of vertices. Think of it like a direct flight map where there's either a flight between two cities or there isn't—no duplicate routes.
A multigraph (or pseudograph) allows multiple edges between the same pair of vertices. Imagine a bus network where multiple bus lines might connect the same two stations, taking different routes or serving different schedules.
Why This Matters
This distinction affects both how we represent graphs and what problems we can model:
-
Simple graphs are cleaner mathematically and more memory-efficient. They're perfect for representing relationships like friendships (you're either friends or not), road networks (one road connects two intersections), or dependencies (task A depends on task B, once).
-
Multigraphs capture real-world complexity like transportation networks (multiple flights between cities), communication channels (several cables between nodes), or weighted alternatives (different cost paths between locations).
Representation Impact
For simple graphs, an adjacency matrix needs only 0s and 1s. For multigraphs, you need to store edge counts or lists of edges, increasing storage complexity.
In code discussions ahead, we'll typically assume simple graphs unless stated otherwise, since they're the foundation for most classic graph algorithms.
Key Takeaway: Simple graphs restrict you to one edge maximum between vertices; multigraphs allow multiple edges, trading simplicity for modeling flexibility.