directedgraph

A directed graph, or digraph, is a set of vertices connected by directed edges. Formally, a directed graph G is defined as G = (V, E) where V is a set of vertices and E is a set of ordered pairs of vertices, with an edge (u, v) indicating a connection from u to v. In a simple digraph there are no loops (edges from a vertex to itself) and at most one edge in a given direction between any two vertices; general digraphs may have multiple arcs or loops.

Directed graphs encode directionality and are used to model asymmetric relationships. A directed path from a vertex u to a vertex v is a sequence of distinct vertices connected by edges in the forward direction. The in-degree of a vertex is the number of edges entering it, while the out-degree is the number of edges leaving it. The out-neighborhood N+(v) consists of vertices reachable by following outgoing edges from v. Representations commonly include an adjacency matrix A, where A[i][j] = 1 if edge i → j exists, and an adjacency list mapping each vertex to its out-neighbors.

Key concepts include directed acyclic graphs (DAGs), which have no directed cycles and are central to scheduling and dependency modeling. Strongly connected components partition the vertices into maximal subsets where each vertex is reachable from every other via directed paths. The transitive closure of a digraph adds an edge for every pair of vertices connected by a directed path, illustrating reachability.

Applications and variants: directed graphs model systems such as citation networks, web link structures, transportation and data-flow networks, and project scheduling. An orientation assigns a direction to each edge of an undirected graph. A tournament is a complete digraph with exactly one directed edge between every pair of vertices; multigraphs allow parallel edges.