1 Basic definition and notation

A directed graph, or digraph, is a graph in which each connection has an assigned direction. It is used to represent relationships that are not necessarily symmetric, such as one-way links, precedence, or flow. Formally, a digraph consists of a set of vertices together with a set of directed edges joining ordered pairs of vertices.

1.1 Vertices and directed edges

The vertices are the fundamental objects of the graph, often drawn as points or nodes. A directed edge, also called an arc, begins at one vertex and ends at another. The starting point is the tail, and the ending point is the head. This orientation distinguishes a digraph from an undirected graph, where edges do not have a direction.

1.2 Ordered pairs and incidence

Because direction matters, a directed edge from vertex \(u\) to vertex \(v\) is written as an ordered pair \((u,v)\). The order indicates that the edge leaves \(u\) and enters \(v\). An edge is said to be incident from its tail and incident to its head. If the same two vertices are connected in both directions, the digraph contains two distinct directed edges.

1.3 Common symbols and conventions

Directed graphs are commonly denoted by \(D\), \(G\), or similar symbols, with the vertex set written as \(V\) and the edge set as \(E\). In diagrams, arrows show direction. A loop is a directed edge that starts and ends at the same vertex. Depending on the setting, repeated edges between the same ordered pair may be allowed or excluded.

2 Types of directed graphs

Directed graphs appear in several standard forms, depending on whether repeated edges, loops, or edge weights are permitted. These distinctions help tailor the model to the structure being studied.

2.1 Simple digraphs

A simple digraph has no loops and no multiple edges between the same ordered pair of vertices. Each possible directed connection appears at most once. This is the most elementary directed-graph model and is often used when only the presence or absence of a one-way relation matters.

2.2 Multidigraphs

A multidigraph allows more than one directed edge from one vertex to another. These parallel edges are treated as distinct, even if they share the same endpoints. Multidigraphs are useful when several kinds of directed relations need to be represented separately within one structure.

2.3 Directed multigraphs with loops

Some directed graphs permit both multiple edges and loops. In such a graph, a vertex may have an edge pointing to itself, and several edges may connect the same ordered pair. This general form is flexible enough to encode repeated actions, self-dependence, or countable interactions.

2.4 Weighted directed graphs

In a weighted directed graph, each directed edge carries a numerical value. The weight may represent cost, distance, capacity, time, probability, or strength of association. Weights do not change the direction of an edge, but they add another layer of information that is often crucial in applications.

3 Fundamental properties

The structure of a digraph is analyzed through local properties of vertices and global patterns of movement through the graph. Direction influences how information, influence, or flow can propagate.

3.1 In-degree and out-degree

The in-degree of a vertex is the number of edges entering it, while the out-degree is the number leaving it. These measures describe how a vertex receives and sends connections. In weighted settings, one may also define weighted in-degree and out-degree by summing the weights of incident edges.

3.2 Adjacency and reachability

Two vertices are adjacent when there is a directed edge from one to the other. Reachability is broader: a vertex \(v\) is reachable from \(u\) if there exists a directed path from \(u\) to \(v\). Adjacency concerns a single edge, whereas reachability depends on the existence of a route that respects direction.

3.3 Paths and directed cycles

A directed path is a sequence of vertices connected by edges that all point forward along the sequence. A directed cycle is a path that begins and ends at the same vertex without repeating other vertices. Cycles are important because they indicate feedback, repetition, or circular dependence within the graph.

3.4 Connectivity notions

Connectivity in digraphs has several versions, since direction can prevent travel even when the underlying connections are present. As a result, a digraph may behave differently from its undirected counterpart.

3.4.1 Strong connectivity

A digraph is strongly connected if every vertex is reachable from every other vertex by directed paths in both directions. This is a stringent condition and indicates that the direction structure allows mutual access throughout the graph.

3.4.2 Weak connectivity

A digraph is weakly connected if its underlying undirected graph is connected. In this case, the graph becomes connected once edge directions are ignored, even if directed travel between some vertices is impossible.

4 Representations

Directed graphs can be stored and studied in several standard forms. Each representation highlights different features and is suited to different computational tasks.

4.1 Adjacency list

An adjacency list associates each vertex with a list of vertices that can be reached by outgoing edges. This representation is efficient for sparse graphs, where most possible edges are absent. It is widely used in algorithms because it gives direct access to outgoing neighbors.

4.2 Adjacency matrix

An adjacency matrix is a square array whose entries indicate whether an edge exists from one vertex to another. For a digraph with \(n\) vertices, the matrix has size \(n \times n\). This form is convenient for dense graphs and for algebraic methods, though it may use more memory when the graph is sparse.

4.3 Incidence matrix

An incidence matrix records the relationship between vertices and edges. In directed form, each column corresponds to an edge, and the entries typically indicate the tail and head of that edge. This representation is useful in theoretical work and in computations involving flows or conservation laws.

4.4 Edge list representation

An edge list stores the directed edges as ordered pairs, often with additional data such as weights. It is simple to construct and easy to serialize. However, it may be less efficient for certain queries, such as finding all outgoing edges from a given vertex.

Subgraphs allow a directed graph to be analyzed through smaller pieces that preserve part of its structure. They are often used to isolate local behavior or to simplify large networks.

5.1 Induced subgraphs

An induced subgraph is formed by choosing a subset of vertices and including every directed edge whose endpoints both lie in that subset. This construction preserves all original connections among the selected vertices. It is a natural way to study the internal structure of a chosen group of nodes.

5.2 Spanning subgraphs

A spanning subgraph contains all the vertices of the original digraph but only some of its edges. Such subgraphs are useful when one wants to retain the full set of objects while focusing on a reduced set of relations. Many optimization problems involve finding a spanning subgraph with particular properties.

5.3 Directed acyclic graphs

A directed acyclic graph, or DAG, is a digraph with no directed cycles. DAGs are central in many areas because they encode partial orders and stage-by-stage processes. Their lack of cycles makes them especially amenable to hierarchical interpretation.

5.3.1 Sources and sinks

A source is a vertex with in-degree zero, so no edge enters it. A sink is a vertex with out-degree zero, so no edge leaves it. In a DAG, sources often represent starting points, while sinks represent terminal states.

5.3.2 Topological ordering

A topological ordering is a linear arrangement of the vertices of a DAG such that every directed edge points from an earlier vertex to a later one. Not every digraph admits such an ordering; it exists precisely when the graph has no directed cycles. This ordering is a standard tool for organizing dependent tasks.

6 Traversal and analysis algorithms

Algorithms for digraphs aim to explore structure, test properties, or compute optimal routes. Direction must always be respected, which changes both the logic and the outcome of many procedures.

Depth-first search explores a graph by moving as far as possible along outgoing edges before backtracking. In directed graphs, it follows only the permitted directions, making it suitable for discovering reachability, classifying edges, and identifying cycles. It is a foundational technique in graph algorithms.

Breadth-first search visits vertices in layers according to directed distance from a starting vertex. It is particularly useful for finding shortest paths in unweighted digraphs. The method examines all neighbors at one depth before moving to the next, producing a systematic outward expansion.

6.3 Cycle detection

Cycle detection determines whether a digraph contains a directed cycle. This problem is important because cycles can affect ordering, dependency resolution, and termination properties. Common approaches use depth-first search, vertex coloring, or repeated removal of vertices with zero in-degree.

6.4 Shortest path algorithms

Shortest path algorithms find minimum-cost routes between vertices in a weighted digraph. The best-known methods include techniques for nonnegative weights and more general methods that can handle certain negative weights. These algorithms are central to routing, scheduling, and path optimization.

7 Special classes of digraphs

Certain families of directed graphs have distinctive edge patterns that make them mathematically interesting and useful in modeling.

7.1 Tournament graphs

A tournament graph is a complete orientation of a simple graph: for every pair of distinct vertices, exactly one of the two possible directed edges is present. Tournaments are often used to model pairwise competitions or preference relations. Their structure can reveal ranking-like patterns and dominance relationships.

7.2 Complete digraphs

A complete digraph contains a directed edge from every vertex to every other distinct vertex. In the strict form, it includes both directions for each pair of different vertices. Such graphs maximize connectivity and serve as reference cases in directed graph theory.

7.3 Regular digraphs

A regular digraph is one in which every vertex has the same in-degree and the same out-degree. This uniformity makes the graph highly symmetric in local structure. Regular digraphs are studied for their balance properties and for their role in constructing structured networks.

7.4 Bipartite directed graphs

A bipartite directed graph has its vertices divided into two disjoint sets, with directed edges constrained by the chosen bipartite rule. Often, edges are allowed only between the two parts, not within either part. These graphs are useful when interactions occur only between two classes of entities.

8 Applications

Directed graphs are widely used because many systems involve one-way relations, ordered processes, or asymmetric influence. Their flexibility makes them a standard modeling tool across mathematics and computing.

8.1 Computer networks

In computer networking, directed graphs can represent data routes, message forwarding, or one-directional links. They help model how packets move through a system and how traffic can be directed through specific channels. Weighted versions are often used to capture latency or capacity.

8.2 Workflow and dependency graphs

Workflows and dependency structures are naturally expressed as digraphs, where tasks point to later tasks that depend on them. This makes it easier to identify prerequisites, schedule operations, and detect circular dependencies. DAGs are especially common in this setting.

8.3 State-transition systems

A state-transition system describes how a process moves from one state to another, often under specific actions or inputs. Directed graphs provide a compact representation of these transitions. They are useful in automata theory, verification, and the study of dynamic processes.

8.4 Social and information networks

Directed graphs can model asymmetric relations in social and information settings, such as following relationships, citation links, or message flow. The direction helps distinguish influence from reception and source from target. Such models are used to study dissemination, prestige, and connectivity patterns.