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

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). Sometimes these entities are called 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 does not allow directed graphs to have loops. Directed graphs without loops may be called simple directed graphs, while directed graphs with loops may be called loop-digraphs (see section Types of directed graph).

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 a logical matrix, and is unique up to permutation of rows and columns.

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

See direction for more definitions.