Directed graph

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).

Similarly, a vertex with deg+(v) = 0 is called a sink, since it is the end of each of its incoming arcs.

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.)