Directed Graph · aiwiki.page

A directed graph, or digraph, is a mathematical structure consisting of vertices and directed edges connecting ordered pairs of vertices. An edge $u\to v$ points from $u$ to $v$ ; it does not imply an edge in the opposite direction. Directed graphs are studied in graph theory. (algs4.cs.princeton.edu)

Definition and conventions

For a directed graph without parallel edges, the standard set-based description is

G=(V,E),\qquad E\subseteq V\times V,

where $V$ is the vertex set and $V\times V$ is its Cartesian product. Each edge is an ordered pair $(u,v)$ , with tail $u$ and head $v$ . Thus the edge set can also be viewed as a binary relation on $V$ . (networkx.org)

Conventions differ about permitted edges. A self-loop connects a vertex to itself. **Parallel edges with the same ordered endpoints; allowing them produces a directed multigraph, which requires distinguishing individual edges rather than recording only endpoint pairs. Oppositely directed edges $u\to v$ and $v\to u$ are not parallel edges. Definitions should specify whether loops and parallel edges are allowed. (algs4.cs.princeton.edu)

An oriented graph, in a common narrower usage, is obtained by assigning a direction to each edge of a simple undirected graph. It therefore excludes pairs of oppositely directed edges between the same vertices; not every directed graph is an oriented graph. (en.wikipedia.org)

Degrees

The outdegree $d^+(v)$ counts edges leaving $v$ , while the indegree $d^-(v)$ counts edges entering it. A loop contributes one to each count. For a finite directed graph,

\sum_{v\in V}d^+(v)=\sum_{v\in V}d^-(v)=|E|.

This follows because each edge has exactly one tail and one head. A vertex of indegree zero is commonly called a source, and one of outdegree zero a sink. (en.wikipedia.org)

Walks, reachability, and connectivity

A directed walk follows edges in their prescribed directions and may repeat vertices or edges. A directed path, under the convention used here, has no repeated vertices. A directed cycle is a positive-length closed directed walk with no repeated vertices except its starting and ending vertex. Terminology for paths varies between texts. (arxiv.org)

A vertex $v$ is reachable from $u$ if a directed path leads from $u$ to $v$ , allowing a length-zero path when $u=v$ . A graph is strongly connected if every vertex is reachable from every other vertex. Its strongly connected components are maximal mutually reachable groups of vertices. Mutual reachability is an equivalence relation, so these components partition the vertex set. (algs4.cs.princeton.edu)

A graph is weakly connected if ignoring edge directions yields a connected undirected graph. Weak connectivity does not imply strong connectivity: a single edge $u\to v$ connects the two vertices when direction is ignored, but provides no route from $v$ to $u$ . (en.wikipedia.org)

Representation

For vertices $v_1,\ldots,v_n$ , the adjacency matrix is the matrix $A$ with

A_{ij}=\text{number of edges from }v_i\text{ to }v_j.

Without parallel edges, entries are zero or one. Row sums give outdegrees and column sums give indegrees. Unlike the adjacency matrix of an undirected graph, $A$ need not be symmetric. For a positive integer $k$ , $(A^k)_{ij}$ counts directed walks of length $k$ , not necessarily paths without repeated vertices. (math.mit.edu)

An adjacency-list representation stores the outgoing neighbors of each vertex. It requires $O(|V|+|E|)$ space and permits traversal of a vertex’s outgoing edges in time proportional to its outdegree. Reversing every edge produces the reverse graph, useful for identifying vertices that can reach a specified vertex. (github.com)

Acyclic graphs and algorithms

A directed acyclic graph (DAG) contains no directed cycles. A finite digraph has a topological ordering—an ordering in which every edge points from an earlier vertex to a later one—if and only if it is a DAG. Such orderings need not be unique. (algs4.cs.princeton.edu)

Fundamental algorithms include depth-first search for reachability and cycle detection, breadth-first search for the shortest-path problem in unweighted graphs, and algorithms for strongly connected components. With adjacency lists, these tasks can be performed in $O(|V|+|E|)$ time. (algs4.cs.princeton.edu)

Applications

Directed graphs represent asymmetric relationships such as hyperlinks between web pages, one-way travel connections, and dependencies between tasks. In scheduling, an edge can indicate that one task must precede another; a topological ordering then supplies a valid execution order when the dependency graph is acyclic. They also represent possible state transitions in Markov chains and references between objects in computer memory. (algs4.cs.princeton.edu)

References

Directed Graphsalgs4.cs.princeton.edu
DiGraph—Directed graphs with self loops — NetworkX documentationnetworkx.org
Digraph.java — algs4github.com
Directed graphen.wikipedia.org
Directed Graphs — lecture slidesalgs4.cs.princeton.edu
Number of paths in a grapharxiv.org
Adjacency matrix of G — MIT lecture notesmath.mit.edu
Evaluating Matrix Functions by Resummations on Graphs: the Method of Path-Sumsarxiv.org
Topological.javaalgs4.cs.princeton.edu