Mathematics.

graph structures

Directed Graphs

Graph Theory25 minDifficulty3 out of 10

You should know: graph basics

Overview

A directed graph (or digraph) is a graph in which edges have a direction, running from one vertex to another rather than simply connecting them. Each edge is an ordered pair (u, v), meaning there is a connection from u to v but not necessarily from v to u. Directed graphs naturally model asymmetric relationships — following on social media, one-way streets, task dependencies, and web hyperlinks. Key notions unique to digraphs include in-degree and out-degree, directed paths, strongly connected components, and directed acyclic graphs (DAGs), which forbid directed cycles and underlie scheduling and dependency resolution.

Intuition

Think of a directed graph as a city of one-way streets: you can drive from vertex A to vertex B along an edge, but that doesn't mean there's a street letting you drive back from B to A. Twitter's 'follows' relationship works the same way — you can follow a celebrity without them following you back. That asymmetry is exactly what an ordered-pair edge (u, v) captures, versus an undirected edge which is symmetric.

Formal Definition

Definition

A directed graph is an ordered pair of a vertex set and a set of ordered-pair edges:

G=(V,E),E⊆V×VG = (V, E), \quad E \subseteq V \times V
Directed graph definition
deg⁡+(v)=∣{(v,u)∈E}∣,deg⁡−(v)=∣{(u,v)∈E}∣\deg^{+}(v) = |\{(v,u) \in E\}|, \quad \deg^{-}(v) = |\{(u,v) \in E\}|
Out-degree and in-degree
∑v∈Vdeg⁡+(v)=∑v∈Vdeg⁡−(v)=∣E∣\sum_{v \in V} \deg^{+}(v) = \sum_{v \in V} \deg^{-}(v) = |E|
Directed handshaking lemma

Worked Examples

  1. Out-degree of A counts edges leaving A: A→B and A→C, so deg⁺(A) = 2.

    deg⁡+(A)=2\deg^{+}(A) = 2

  2. In-degree of C counts edges entering C: B→C and A→C, so deg⁻(C) = 2.

    deg⁡−(C)=2\deg^{-}(C) = 2

Answer: deg⁺(A) = 2, deg⁻(C) = 2.

Practice Problems

Difficulty 3/10

A digraph has edges A→B, A→C, B→D, C→D, D→A. What is deg⁻(D)?

Difficulty 4/10

A course-prerequisite system has edges Calc1→Calc2, Calc2→Calc3, Calc1→LinAlg. Is this digraph a DAG, and why does that matter for scheduling?

Difficulty 5/10

In a digraph, what does it mean for two vertices u and v to be 'strongly connected', and how does that differ from ordinary (weak) connectivity in the underlying undirected graph?

Quiz

In a directed graph, an edge (u, v) means:
A directed acyclic graph (DAG) is a directed graph that:
The sum of all out-degrees in a directed graph equals:

Summary

  • A directed graph's edges are ordered pairs (u, v), representing a one-way connection from u to v.
  • In-degree and out-degree replace the single 'degree' of undirected graphs; both sum to |E| across all vertices.
  • A digraph with no directed cycle is a DAG — the structure guaranteeing a valid topological order (scheduling, build systems, prerequisites).

References

  1. WebsiteWikipedia — Directed graph