Directed Graphs (Digraphs)
What You'll Learn
You'll learn how direction transforms graphs, distinguishing between edges that go "one way" versus "both ways," and how to measure vertex connectivity differently for incoming versus outgoing edges.
The Core Idea
Until now, edges in graphs have been symmetric—if vertex A connects to vertex B, then B automatically connects to A. Directed graphs (or digraphs) change this by assigning a direction to each edge, creating one-way relationships.
Think of a digraph like a network of one-way streets: you can travel from intersection A to intersection B, but that doesn't mean you can travel back from B to A without following a different route. Or consider social media "following": if Alice follows Bob, Bob doesn't automatically follow Alice back.
In-Degree and Out-Degree
In digraphs, we distinguish two types of degree for each vertex:
- Out-degree: the number of edges leaving (pointing away from) a vertex
- In-degree: the number of edges entering (pointing toward) a vertex
For example, imagine vertex V with three arrows pointing away from it to other vertices, and two arrows coming into it from other vertices. Then V has out-degree 3 and in-degree 2.
Notation and Terminology
A directed edge from vertex u to vertex v is often written as an ordered pair (u, v) or shown with an arrow u → v. The direction matters: (u, v) ≠ (v, u) unless both directed edges exist.
If both (u, v) and (v, u) exist, the vertices are connected in both directions—essentially like an undirected edge, but represented as two separate directed edges.
Key Takeaway: Directed graphs model one-way relationships through directed edges, requiring us to track in-degree (incoming edges) and out-degree (outgoing edges) separately for each vertex.