Tree¶

Recognition Tests¶

A forest is an acyclic, undirected graph, and a tree is a connected forest. Depending on the subfield, there are various conventions for generalizing these definitions to directed graphs.

In one convention, directed variants of forest and tree are defined in an identical manner, except that the direction of the edges is ignored. In effect, each directed edge is treated as a single undirected edge. Then, additional restrictions are imposed to define branchings and arborescences.

In another convention, directed variants of forest and tree correspond to the previous convention’s branchings and arborescences, respectively. Then two new terms, polyforest and polytree, are defined to correspond to the other convention’s forest and tree.

Summarizing:

+-----------------------------+
| Convention 1 | Convention 2 |
+=============================+
| forest       | polyforest   |
| tree         | polytree     |
| branching    | forest       |
| arborescence | tree         |
+-----------------------------+

Each convention has its reasons. The first convention emphasizes definitional similarity in that directed forests and trees are only concerned with acyclicity and do not have an in-degree constraint, just as their undirected counterparts do not. The second convention emphasizes functional similarity in the sense that the directed analog of a spanning tree is a spanning arborescence. That is, take any spanning tree and choose one node as the root. Then every edge is assigned a direction such there is a directed path from the root to every other node. The result is a spanning arborescence.

NetworkX follows the first convention. Explicitly, these are:

undirected forest

An undirected graph with no undirected cycles.

undirected tree

A connected, undirected forest.

directed forest

A directed graph with no undirected cycles. Equivalently, the underlying graph structure (which ignores edge orientations) is an undirected forest. In another convention, this is known as a polyforest.

directed tree

A weakly connected, directed forest. Equivalently, the underlying graph structure (which ignores edge orientations) is an undirected tree. In another convention, this is known as a polytree.

branching

A directed forest with each node having, at most, one parent. So the maximum in-degree is equal to 1. In another convention, this is known as a forest.

arborescence

A directed tree with each node having, at most, one parent. So the maximum in-degree is equal to 1. In another convention, this is known as a tree.