Arborescence

Let D=(V,A) be a directed graph. An arborescence of D is a (not necessarily spanning) subdigraph whose underlying undirected graph is a tree and every node has in-degree at most 1. The single node of the tree with in-degree 0 is called the root of the arborescence. Sometimes this is referred to as an out-arborescence, while a tree subdigraph where every node has out-degree at most 1 is called an in-arborescence.

A spanning arborescence is an arborescence whose underlying undirected graph is a spanning tree. We note that in Schrijver's book this is the definition of "arborescence". For a node [math]r \in V[/math], an r-arborescence is an arborescence with root r.

A branching of D is a subdigraph whose underlying undirected graph is a forest and every node has in-degree at most 1. The nodes of in-degree 0 are called the roots of the branching. For [math]R \subseteq V[/math], an R-branching is a branching with root set R.

Two arborescences are independent if for any common node v the unique directed paths from the root to v in the two arborescences are internally node-disjoint.