Directed Graph — Definition, Formula & Examples

A directed graph is a graph in which every edge has a specific direction, pointing from one vertex to another. Each edge is an ordered pair, so the edge from vertex A to vertex B is different from the edge from B to A.

A directed graph (or digraph) is an ordered pair $G = (V, E)$ where $V$ is a finite set of vertices and $E \subseteq V \times V$ is a set of ordered pairs of vertices called directed edges (or arcs). For an arc $(u, v) \in E$ , vertex $u$ is the tail and vertex $v$ is the head.

How It Works

Each edge in a directed graph is drawn as an arrow from one vertex to another. The arrow indicates that the relationship goes one way:

(u, v)

means there is a connection from

u

v

, but not necessarily from

v

u

. The in-degree of a vertex counts how many arrows point into it, while the out-degree counts how many arrows leave it. Directed graphs model any situation where relationships are not symmetric, such as web page hyperlinks, prerequisite chains, or one-way streets.

Worked Example

Problem: Given the directed graph G = (V, E) with V = {1, 2, 3, 4} and E = {(1,2), (1,3), (2,3), (3,4), (4,1)}, find the in-degree and out-degree of each vertex.

Count out-degrees: Count how many edges leave each vertex. Vertex 1 appears as a tail in (1,2) and (1,3). Vertex 2 appears as a tail in (2,3). Vertex 3 appears as a tail in (3,4). Vertex 4 appears as a tail in (4,1).

\text{out-deg}(1) = 2,\; \text{out-deg}(2) = 1,\; \text{out-deg}(3) = 1,\; \text{out-deg}(4) = 1

Count in-degrees: Count how many edges point into each vertex. Vertex 1 is the head of (4,1). Vertex 2 is the head of (1,2). Vertex 3 is the head of (1,3) and (2,3). Vertex 4 is the head of (3,4).

\text{in-deg}(1) = 1,\; \text{in-deg}(2) = 1,\; \text{in-deg}(3) = 2,\; \text{in-deg}(4) = 1

Verify: The sum of all in-degrees equals the sum of all out-degrees, and both equal the number of edges.

\sum \text{in-deg} = \sum \text{out-deg} = |E| = 5

Answer: Out-degrees: 2, 1, 1, 1. In-degrees: 1, 1, 2, 1. Both sums equal 5, confirming the count.

Why It Matters

Directed graphs are central to algorithms you encounter in computer science courses, including topological sorting, shortest-path algorithms like Dijkstra's, and network flow problems. They also model real systems such as social media follow relationships, compiler dependency resolution, and finite automata in theory of computation.

Common Mistakes

Mistake: Treating (u, v) and (v, u) as the same edge.

Correction: In a directed graph, order matters. The arc (u, v) goes from u to v, while (v, u) goes from v to u. They are distinct edges and both can exist independently.