A simple directed graph
A simple 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.

Definition

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). 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.[2] 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).

Types of directed graphs

See also: Graph (discrete mathematics) § Types of graphs

Subclasses

A simple directed acyclic graph
A simple directed acyclic graph
A tournament on 4 vertices
A tournament on 4 vertices

Digraphs with supplementary properties

This list is incomplete; you can help by adding missing items. (August 2016)

Basic terminology

Oriented graph with corresponding incidence matrix
Oriented graph with corresponding incidence matrix

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 aij is the number of arcs from vertex i to vertex j, and the diagonal entry aii 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.

Indegree and outdegree

A directed graph with vertices labeled (indegree, outdegree)
A directed graph with vertices labeled (indegree, outdegree)

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

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

If for every vertex vV, deg+(v) = deg(v), the graph is called a balanced directed graph.[9]

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

Directed graph connectivity

Main article: Connectivity (graph theory)

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.

See also

Notes

  1. ^ Bang-Jensen & Gutin (2000). Bang-Jensen & Gutin (2018), Chapter 1.Diestel (2005), Section 1.10. Bondy & Murty (1976), Section 10.
  2. ^ a b c Chartrand, Gary (1977). Introductory Graph Theory. Courier Corporation. ISBN 9780486247755. Archived from the original on 2023-02-04. Retrieved 2020-10-02.
  3. ^ Bang-Jensen & Gutin (2018), Chapter 7 by Yeo.
  4. ^ Bang-Jensen & Gutin (2018), Chapter 2 by Bang-Jensen and Havet.
  5. ^ Bang-Jensen & Gutin (2018), Chapter 8 by Galeana-Sanchez and Hernandez-Cruz.
  6. ^ Diestel (2005), Section 1.10.
  7. ^ Bang-Jensen & Gutin (2018), Chapter 2 by Bang-Jensen and Havet.
  8. ^ Bang-Jensen & Gutin (2018), Chapter 3 by Gutin.
  9. ^ 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.
  10. ^ Bang-Jensen & Gutin (2000) p. 19 in the 2007 edition; p. 20 in the 2nd edition (2009).

References