Course contentsShow
← Computer Science
Lesson 687 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

Self-Loops and Their Implications

Understanding edges that connect a vertex to itself and contexts where they matter.

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.