Directed graph

In the field of mathematics, specifically within graph theory, a directed graph is a structured way to model connections that have a specific direction. Also known as a digraph, this mathematical object consists of two primary components. The first is a set of elements called vertices, nodes, or points. The second is a set of ordered pairs of these vertices, which are known as arcs, directed edges, or arrows.

Unlike an undirected graph, where connections are simply links between points, a digraph uses the order of the pairs to establish a clear sense of movement. This distinction allows mathematicians to model systems where the relationship between two points is not necessarily mutual.

To understand how a digraph functions, one must look at the anatomy of its arcs. Every arc has a specific starting point and a specific ending point. The starting point is formally called the tail, while the ending point is known as the head.

Because of this structure, we can define the relationship between vertices using terms like predecessor and successor. If an arc travels from vertex X to vertex Y, then X is the direct predecessor of Y, and Y is the direct successor of X. If a sequence of arcs allows you to travel from one vertex to another, the destination is said to be reachable from the starting point. Some digraphs even include loops, which are arcs that connect a vertex directly back to itself.

Directed graphs can be categorized into several distinct types based on their specific properties. A simple directed graph is one that contains no loops and no multiple arrows sharing the same source and target nodes. If a graph allows multiple arrows between the same two points, it is classified as a directed multigraph. Some graphs are defined by the absence of cycles, which are paths that return to their starting point. These are called directed acyclic graphs, or DAGs.

Another specialized type is the tournament. A tournament is an oriented graph created by assigning a single direction to every edge in an undirected complete graph.

This results in a semicomplete digraph where every pair of vertices is connected by exactly one arc.

Mathematical properties can also be used to classify these structures, such as symmetry and transitivity. A symmetric directed graph is one where every arc has a corresponding inverse arc traveling in the opposite direction. In these graphs, every connection is essentially bidirected. There are also quasi-transitive digraphs, which follow a specific rule regarding triples of vertices. In a quasi-transitive digraph, if there is an arc from vertex X to Y and an arc from Y to Z, there must also be an arc from X to Z. This creates a predictable flow within the network, similar to how certain logical arguments or hierarchies function.

We can quantify the connectivity of a vertex by measuring its indegree and outdegree. The indegree, denoted as deg−(v), is the number of arrow heads adjacent to a vertex. The outdegree, denoted as deg+(v), is the number of tails adjacent to that vertex.

These numbers allow us to identify special roles within a network. A vertex with an indegree of zero is called a source, as it only serves as an origin for outgoing arcs. Conversely, a vertex with an outdegree of zero is called a sink, because it only receives incoming arcs. The sum of all indegrees in a digraph will always equal the sum of all outdegrees, a fundamental rule known as the degree sum formula.

Beyond simple connections, digraphs can be enhanced with additional data to create more complex models. Weighted directed graphs, often called directed networks, assign specific numerical weights to each arc. This is useful in flow networks, where two specific nodes are distinguished as a source and a sink to represent the movement of resources. In computer science, control-flow graphs are used as rooted digraphs to represent the various paths a computer program might take during execution. These models help engineers visualize and predict how software will behave under different conditions.

Directed graphs serve as essential tools across a vast range of scientific and mathematical disciplines. In category theory, commutative diagrams use digraphs to represent mathematical objects and morphisms. In the study of Lie groups, a structure called a quiver uses a directed graph to characterize a representation. They are also used in signal-flow graphs to represent functional connections between system variables. Whether they are modeling the logic of a computer program or the complex flows of a physical network, directed graphs provide a precise language for describing the directed nature of our world.