[Math] the equivalent of a tree for directed graphs

connectednessdirected graphsgraph theorytrees

A tree is defined as a connected acyclic undirected graph at page 171 of this online book.

What is the equivalent of a tree for directed graphs? A connected acyclic directed graph (i.e. a connected DAG)? In other words, what is a directed tree? If you have a good reference I am really interested.

Best Answer

With the help of Narsingh Deo’s book Graph Theory with Applications to Engineering and Computer Science (thank you @ShubhamJohri for the reference) I could answer to myself:

Section 9.4. Directed paths and connectedness:

Walks, paths, and circuits in a directed graph, in addition to being what they are in the corresponding undirected graph, have the added consideration of orientation. […]

A directed walk from a vertex vi to vj is an alternating sequence of vertices and edges, beginning with vi and ending with vj, such that each edge is oriented from the vertex preceding it to the vertex following it. Of course, no edge in a directed walk appears more than once, but a vertex may appear more than once, just as in the case of undirected graphs. A semiwalk in a directed graph is a walk in the corresponding undirected graph, but is not a directed walk. A walk in a digraph can mean either a directed walk or a semiwalk.

The definitions of circuit, semicircuit, and directed circuit can be written similarly. […]

Connected Digraphs: In Chapter 2 a graph (i.e., undirected graph) was defined as connected if there was at least one path between every pair of vertices. In a digraph, there are two different types of paths. Consequently, we have two different types of connectedness in digraphs. A digraph G is said to be strongly connected if there it at least one directed path from every vertex to every other vertex. A digraph G is said to be weakly connected if its corresponding undirected graph is connected but G is not strongly connected. […] The statement that a digraph G is connected simply means that its corresponding undirected graph is connected; and thus G may be strongly or weakly connected. A directed graph that is not connected is dubbed as disconnected.

Section 9.6. Trees with directed edges:

A tree (for undirected graphs) was defined as a connected graph without any circuit. The basic concept as well as the term “tree” remains the same for digraphs. A tree is a connected digraph that has no circuit—neither a directed circuit nor a semicircuit. A tree of n vertices contains n − 1 directed edges and has properties similar to those with undirected edges. […]

Arborescence: A digraph G is said to be an arborescence if

  1. G contains no circuit—neither directed nor semicircuit.

  2. In G there is precisely one vertex v of zero in-degree.

This vertex v is called the root of the arborescence. […]

THEOREM 9.2. An arborescence is a tree in which every vertex other than the root has an in-degree of exactly one.

[…]

An arborescence is in a sense a tree directed out of the root. Therefore an arborescence is sometimes referred to as an out-tree. (Reversing the direction of every edge in an arborescence will produce what may be called an in-tree.)

Section 9.11. Acyclic digraphs and decyclization:

In many situations semicircuits are of no significance, and one is concerned only with whether or not a given digraph has a directed circuit. A digraph that has no directed circuit is called acyclic.

To sum up, for directed graphs:

  • a connected directed graph is either a strongly connected directed graph or a weakly connected directed graph;
  • a cycle is either a directed cycle or a semicycle;
  • an acyclic directed graph (DAG) is a directed graph without directed cycles;
  • a directed tree is a connected directed graph without cycles (not to be confused with a connected directed graph without directed cycles—a connected DAG). In other words, it is a directed graph whose underlying graph is a tree;
  • an arborescence (or out-tree) is a directed tree whose vertices have a maximum in-degree of 1;
  • an anti-arborescence (or in-tree) is a directed tree whose vertices have a maximum out-degree of 1.

For instance, this connected DAG is not a directed tree: ({a, b, c}, {(a, b), (b, c), (a, c)}), since even if it is connected (more precisely weakly connected) it has semicycles, for instance (a, (a, b), b, (b, c), c, (a, c), a).

Likewise, for directed graphs:

  • a directed forest is a directed graph without cycles (not to be confused with an acyclic directed graph, i.e. a DAG). In other words, it is a directed graph whose underlying graph is a forest.
  • a branching (or out-forest) is a directed forest whose vertices have a maximum in-degree of 1;
  • an anti-branching (or in-forest) is a directed forest whose vertices have a maximum out-degree of 1.

Another convention calls a directed tree a polytree, an arborescence a directed tree, a directed forest a polyforest and a branching a directed forest.

Cf. the documentation of NetworkX, a Python library.

Related Question