Course contentsShow
← Mathematics
Lesson 2649 of 3,12153. Graph TheoryFree lesson

Directed Graphs (Digraphs)

Introduce digraphs where edges have direction, distinguishing in-degree and out-degree of vertices.

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.