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