# Directed graph

In mathematics, and more specifically in graph theory, a **directed graph** (or **digraph**) is a graph that is made up of a set of vertices connected by directed edges often called **arcs**.

In formal terms, a directed graph is an ordered pair *G* = (*V*, *A*) where^{[1]}

It differs from an ordinary or undirected graph, in that the latter is defined in terms of unordered pairs of vertices, which are usually called *edges*, *links* or *lines*.

The aforementioned definition does not allow a directed graph to have multiple arrows with the same source and target nodes, but some authors consider a broader definition that allows directed graphs to have such multiple arcs (namely, they allow the arc set to be a multiset). More specifically, these entities are addressed as **directed multigraphs** (or **multidigraphs**).

On the other hand, the aforementioned definition allows a directed graph to have loops (that is, arcs that directly connect nodes with themselves), but some authors consider a narrower definition that doesn't allow directed graphs to have loops.^{[2]}
More specifically, directed graphs without loops are addressed as **simple directed graphs**, while directed graphs with loops are addressed as *loop-digraphs* (see section Types of directed graphs).

An arc (*x*, *y*) is considered to be directed *from* *x* *to* *y*; *y* is called the *head* and *x* is called the *tail* of the arc; *y* is said to be a *direct successor* of *x* and *x* is said to be a *direct predecessor* of *y*. If a path leads from *x* to *y*, then *y* is said to be a *successor* of *x* and *reachable* from *x*, and *x* is said to be a *predecessor* of *y*. The arc (*y*, *x*) is called the *reversed arc* of (*x*, *y*).

The adjacency matrix of a multidigraph with loops is the integer-valued matrix with rows and columns corresponding to the vertices, where a nondiagonal entry *a*_{ij} is the number of arcs from vertex *i* to vertex *j*, and the diagonal entry *a*_{ii} is the number of loops at vertex *i*. The adjacency matrix of a directed graph is unique up to identical permutation of rows and columns.

Another matrix representation for a directed graph is its incidence matrix.

For a vertex, the number of head ends adjacent to a vertex is called the *indegree* of the vertex and the number of tail ends adjacent to a vertex is its *outdegree* (called *branching factor* in trees).

Let *G* = (*V*, *A*) and *v* ∈ *V*. The indegree of *v* is denoted deg^{−}(*v*) and its outdegree is denoted deg^{+}(*v*).

A vertex with deg^{−}(*v*) = 0 is called a *source*, as it is the origin of each of its outcoming arcs. Similarly, a vertex with deg^{+}(*v*) = 0 is called a *sink*, since it is the end of each of its incoming arcs.

If for every vertex *v* ∈ *V*, deg^{+}(*v*) = deg^{−}(*v*), the graph is called a *balanced directed graph*.^{[9]}

The degree sequence of a directed graph is the list of its indegree and outdegree pairs; for the above example we have degree sequence ((2, 0), (2, 2), (0, 2), (1, 1)). The degree sequence is a directed graph invariant so isomorphic directed graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a directed graph; in some cases, non-isomorphic digraphs have the same degree sequence.

The directed graph realization problem is the problem of finding a directed graph with the degree sequence a given sequence of positive integer pairs. (Trailing pairs of zeros may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the directed graph.) A sequence which is the degree sequence of some directed graph, i.e. for which the directed graph realization problem has a solution, is called a directed graphic or directed graphical sequence. This problem can either be solved by the Kleitman–Wang algorithm or by the Fulkerson–Chen–Anstee theorem.

A directed graph is *weakly connected* (or just *connected*^{[10]}) if the undirected *underlying graph* obtained by replacing all directed edges of the graph with undirected edges is a connected graph.

A directed graph is *strongly connected* or *strong* if it contains a directed path from *x* to *y* (and from *y* to *x*) for every pair of vertices (*x*, *y*). The *strong components* are the maximal strongly connected subgraphs.

A connected rooted graph (or *flow graph*) is one where there exists a directed path to every vertex from a distinguished *root vertex*.