Self-Loops and Their Implications
What you'll learn: You'll understand what self-loops are in graphs and when they become relevant in real-world modeling.
What is a Self-Loop?
A self-loop is an edge that connects a vertex to itself. Picture a node with an arrow (in directed graphs) or line (in undirected graphs) that curves back and points to the same node it started from.
In mathematical terms, if you have a vertex v, a self-loop is an edge (v, v).
Why Do Self-Loops Matter?
Self-loops might seem unusual at first—why would something connect to itself? But they appear naturally in certain contexts:
State machines: A system might remain in the same state under certain inputs. For example, a traffic light stuck on red due to a "wait" signal creates a self-loop on the red state.
Social networks: Someone might have a relationship with themselves (e.g., "follows self" on social media platforms that allow it).
Task dependencies: A recursive process where a task can trigger itself creates a self-loop in a dependency graph.
Implications for Graph Algorithms
Self-loops affect various graph properties and algorithms:
- Degree calculation: In undirected graphs, a self-loop traditionally adds 2 to a vertex's degree (the edge touches the vertex twice)
- Cycle detection: A self-loop is technically a cycle of length 1
- Simple graphs: By definition, simple graphs don't allow self-loops (or multiple edges between the same vertices)
When to Allow or Forbid Them
Whether you permit self-loops depends on your problem domain. Most theoretical graph problems assume simple graphs (no self-loops), but practical applications like finite automata or workflow systems often require them.
Key Takeaway: Self-loops are edges from a vertex to itself; they're forbidden in simple graphs but essential for modeling systems where entities can have reflexive relationships or remain in their current state.