Directed graph

In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph, or set of nodes connected by edges, where the edges have a direction associated with them. In formal terms, a digraph is a pair $G=(V,A)$ (sometimes $G=(V,E)$ ) of:^[1]

a set V, whose elements are called vertices or nodes,
a set A of ordered pairs of vertices, called arcs, directed edges, or arrows (and sometimes simply edges with the corresponding set named E instead of A).

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.

A digraph is called "simple" if it has no loops, and no multiple arcs (arcs with same starting and ending nodes). A directed multigraph, in which the arcs constitute a multiset, rather than a set, of ordered pairs of vertices may have loops (that is, "self-loops" with same starting and ending node) and multiple arcs. Some, but not all, texts allow a digraph, without the qualification simple, to have self loops, multiple arcs, or both.

Basic terminology

An arc $e=(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 made up of one or more successive arcs leads from $x$ to $y$ , then $y$ is said to be a successor of $x$ , and $x$ is said to be a predecessor of $y$ . The arc $(y,x)$ is called the arc $(x,y)$ inverted.

An orientation of a simple undirected graph is obtained by assigning a direction to each edge. Any directed graph constructed this way is called an "oriented graph". A directed graph is an oriented simple graph if and only if it has neither self-loops nor 2-cycles.^[2]

A weighted digraph is a digraph with weights assigned to its arcs, similar to a weighted graph. In the context of graph theory a digraph with weighted edges is called a network.

The adjacency matrix of a digraph (with loops and multiple arcs) is the integer-valued matrix with rows and columns corresponding to the nodes, where a nondiagonal entry $a_{ij}$ is the number of arcs from node i to node j, and the diagonal entry $a_{ii}$ is the number of loops at node i. The adjacency matrix of a digraph is unique up to identical permutation of rows and columns.

Another matrix representation for a digraph is its incidence matrix.

See direction for more definitions.

Indegree and outdegree

A digraph with vertices labeled (indegree, outdegree)

For a node, the number of head endpoints adjacent to a node is called the indegree of the node and the number of tail endpoints adjacent to a node is its outdegree (called "branching factor" in trees).

The indegree is denoted $\deg ^{-}(v)$ and the outdegree as $\deg ^{+}(v).$ A vertex with $\deg ^{-}(v)=0$ is called a source, as it is the origin of each of its incident edges. Similarly, a vertex with $\deg ^{+}(v)=0$ is called a sink.

The degree sum formula states that, for a directed graph,

\sum _{v\in V}\deg ^{+}(v)=\sum _{v\in V}\deg ^{-}(v)=|A|\,.

If for every node $v \in V$ , $\deg ^{+}(v)=\deg ^{-}(v)$ , the graph is called a balanced digraph.^[3]

Degree sequence

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 graph; in some cases, non-isomorphic graphs have the same degree sequence.

The digraph realization problem is the problem of finding a digraph with the degree sequence being 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 digraph.) A sequence which is the degree sequence of some digraph, i.e. for which the digraph realization problem has a solution, is called a digraphic or digraphical sequence. This problem can either be solved by the Kleitman–Wang algorithm or by the Fulkerson–Chen–Anstee theorem.

Digraph connectivity

A digraph G is called weakly connected (or just connected^[4]) if the undirected underlying graph obtained by replacing all directed edges of G with undirected edges is a connected graph. A digraph is strongly connected or strong if it contains a directed path from u to v and a directed path from v to u for every pair of vertices u,v. The strong components are the maximal strongly connected subgraphs.

Classes of digraphs

A directed graph G is called symmetric if, for every arc that belongs to G, the corresponding reversed arc also belongs to G. A symmetric, loopless directed graph is equivalent to an undirected graph with the edges replaced by pairs of inverse arcs; thus the number of edges is equal to the number of arcs halved.

An acyclic directed graph, acyclic digraph, or directed acyclic graph is a directed graph with no directed cycles. Special cases of acyclic directed graphs include multitrees (graphs in which no two directed paths from a single starting node meet back at the same ending node), oriented trees or polytrees (digraphs formed by orienting the edges of undirected acyclic graphs), and rooted trees (oriented trees in which all edges of the underlying undirected tree are directed away from the roots).

A tournament is an oriented graph obtained by choosing a direction for each edge in an undirected complete graph.

In the theory of Lie groups, a quiver Q is a directed graph serving as the domain of, and thus characterizing the shape of, a representation V defined as a functor, specifically an object of the functor category FinVct_K^F(Q) where F(Q) is the free category on Q consisting of paths in Q and FinVct_K is the category of finite-dimensional vector spaces over a field K. Representations of a quiver label its vertices with vector spaces and its edges (and hence paths) compatibly with linear transformations between them, and transform via natural transformations.

Notes

^ Bang-Jensen & Gutin (2000). Diestel (2005), Section 1.10. Bondy & Murty (1976), Section 10.
^ Diestel (2005), Section 1.10.
^ Satyanarayana, Bhavanari; Prasad, Kuncham Syam, Discrete Mathematics and Graph Theory, PHI Learning Pvt. Ltd., p. 460, ISBN 978-81-203-3842-5; Brualdi, Richard A. (2006), Combinatorial matrix classes, Encyclopedia of mathematics and its applications, vol. 108, Cambridge University Press, p. 51, ISBN 978-0-521-86565-4.
^ Bang-Jensen & Gutin (2000) p. 19 in the 2007 edition; p. 20 in the 2nd edition (2009).

References

Bang-Jensen, Jørgen; Gutin, Gregory (2000), Digraphs: Theory, Algorithms and Applications, Springer, ISBN 1-85233-268-9
(the corrected 1st edition of 2007 is now freely available on the authors' site; the 2nd edition appeared in 2009 ISBN 1-84800-997-6).
Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, ISBN 0-444-19451-7.
Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6 (the electronic 3rd edition is freely available on author's site).
Harary, Frank; Norman, Robert Z.; Cartwright, Dorwin (1965), Structural Models: An Introduction to the Theory of Directed Graphs, New York: Wiley.
Number of directed graphs (or digraphs) with n nodes.

[1] Bang-Jensen & Gutin (2000). Diestel (2005), Section 1.10. Bondy & Murty (1976), Section 10.

[2] Diestel (2005), Section 1.10.

[3] Satyanarayana, Bhavanari; Prasad, Kuncham Syam, Discrete Mathematics and Graph Theory, PHI Learning Pvt. Ltd., p. 460, ISBN 978-81-203-3842-5; Brualdi, Richard A. (2006), Combinatorial matrix classes, Encyclopedia of mathematics and its applications, vol. 108, Cambridge University Press, p. 51, ISBN 978-0-521-86565-4.

[4] Bang-Jensen & Gutin (2000) p. 19 in the 2007 edition; p. 20 in the 2nd edition (2009).

[1]

[2]

[3]

[4]