digraf

Digraf is a term occasionally used to refer to a directed graph, or digraph, in some languages or contexts. In standard graph theory, the object is more commonly called a directed graph or digraph. A digraph G consists of a nonempty set V of vertices and a set E of ordered pairs of vertices, called arcs or directed edges. An arc (u, v) represents a connection from u to v. Unlike undirected graphs, the direction of edges matters for reachability and traversal.

Simple digraphs have at most one arc from u to v and no loops, meaning there is no arc from a vertex to itself. In general, a digraph may contain parallel arcs and loops. The outdegree of a vertex is the number of arcs leaving it, and the indegree is the number of arcs entering it.

Key concepts include paths, directed paths, cycles, and reachability. A digraph is acyclic if it contains no directed cycles; such graphs are called DAGs and are central to scheduling and ordering problems. Strongly connected components are maximal subsets of vertices where each vertex is reachable from every other via directed paths.

Representations include an adjacency matrix A, where A[i][j] is 1 if there is an arc i→j, or adjacency lists that enumerate outgoing arcs for each vertex. Common algorithms adapt to digraphs: depth-first search, topological sorting, and shortest-path algorithms (on weighted digraphs) such as Dijkstra or Bellman-Ford.

Applications span computer networks, transportation and logistics, project planning, data flow, and state machines. The digraph relates to its underlying undirected graph obtained by ignoring edge directions. In contexts where digraf is used, it often signals a focus on directional relationships within a graph structure.