digraph

Digraph, short for directed graph, is a set of vertices together with a set of ordered pairs of vertices called arcs or directed edges. Each arc u -> v indicates a relationship from vertex u to vertex v. Unlike undirected graphs, the direction of edges matters, so the pair (u, v) is distinct from (v, u). A simple digraph has at most one arc in each direction between any pair of vertices and typically no loops; a multigraph may include parallel arcs and loops.

In a digraph, the in-degree of a vertex is the number of arcs entering it, and the out-degree is the number of arcs leaving it. The sum of all in-degrees equals the number of arcs, and the sum of all out-degrees also equals the number of arcs. Digraphs may contain directed cycles; a directed cycle starts at a vertex and returns to it following edge directions. A digraph is acyclic if it has no directed cycles, a structure known as a DAG that is useful for representing precedence relations. Strong connectivity means every vertex is reachable from every other following edge directions; weak connectivity ignores edge directions.

Representations include adjacency matrices, where entry A[i][j] records arcs from i to j, and adjacency lists that store outgoing neighbors for each vertex. Algorithms such as depth-first search and breadth-first search extend to digraphs; topological sorting applies to DAGs; reachability, transitive closure, and strongly connected component decompositions (e.g., Kosaraju or Tarjan) identify structural features.

Applications of digraphs span computer science and beyond, including modeling state machines, scheduling, network flow, citation and web graphs, and various relational systems.

In linguistics, digraph also denotes a pair of letters representing a single phoneme, as in "ph" or "th" in certain languages, distinct from the graph-theoretical concept.