What is an Arborescence (Graph Theory)?

Question

On Wikipedia, it states an arborescence is a digraph for which a vertex $u$ called the root and any other vertex $v$, there is exactly one directed path from $u$ to $v$.

In other words, does that mean an arborescence is a digraph whose underlying graph is a tree?

Answer 1

In fact, more is true. Given any tree, every edge can be given uniquely a direction that is towards the root of the tree. In other words, any tree can be uniquely converted into an arborescence. Conversely, any arborescence can be uniquely converted into a tree by changing each directed edge into an undirected edge.

EDIT: We always assume that there is given a root with the tree or arborescence.

Answer 2

An Arborescence by this definition is synonymous with Directed-(“Generalized Spread” or “Tree-Spread”). In Graph Theory, a Tree allows for connections between nodes, but no cycles. Therefore, Tree’s can have multiple roots; a Spread has exactly $1$ root. A DiGraph is a “Directed Graph”, meaning the vertices of the graph have edges that ~direct~ to another vertex. A DiGraph Tree is a ”Directed Acyclic Graph (DAG) because it is directed, and has no cycles. A DAG with a single-root is an Arborescence (alternative definition).

In Set Theory, the definition for a Tree is different: it has $1$ root instead… so it’s not consistent… In Graph Theory, a “PolyTree” is an example of a Tree, that does not fit the definition for a Tree in Set Theory…

By the given definition, an Arborescence has elements with uniqueness of Path:

Uniqueness of path Explanation:

In a Spread ‘$S$’, the root ‘$x_0$’ branches into ${x_1, x_2, x_3}$, (Note: the root has a “degree” of 3 in this example) and $x_1$ could branch into ${y_1,y_2}$, (Note: the nodes could have varying degree)

$y_1$ can only be described by: $x_0$ -> $x_1$ -> $y_1$ , which is also intuitive, because there are no other parents that own $y_1$- there are no other grandparents that own $x_1$ either. Therefore, there is only this Path to $y_1$.

This property is true for all elements in Generalized Spreads.

More on edges (directed edge theory):

A graph is made up of vertices, and edges that connect those vertices, (Note: Graphs can be “connected” or “disconnected”; Trees are all connected, but you could have a “Forest” of Trees…) The Edges connecting the vertices in a graph can be “loose”, “introverted”, “extroverted”, or “directed”. (Note: sometimes the words “directed” and “undirected” are used, but this introduces more variations — it’s kinda interesting) A DiGraph consists of only directed edges…

Fundamentally, a directed edge is made up of two “Half-edges” (one from both vertices); one half-edge is introverted (being directed to) and one half-edge is extroverted (being directed from).

Cheers.