TAOCP 2.3.4.2 Exercise 9

Section 2.3.4.2: Oriented Trees

Exercise 9. [**] $$18$$ By assigning directions to the edges, draw the oriented tree corresponding to the free tree in Fig. 30 on page 363, with $G$ as the root.

Verified: yes
Solve time: 55s

Let $T$ be the free tree in Fig. 30 with distinguished vertex $G$. For each edge $V\text{--}V'$, there is a unique simple path in $T$ from $V$ to $G$. If this path begins $(V,V',\ldots,G)$, then the edge $V\text{--}V'$ is replaced by the arc $V\to V'$. Otherwise the path from $V'$ to $G$ begins $(V',V,\ldots,G)$, and the edge is replaced by the arc $V'\to V$. This rule assigns a direction to every edge since each edge lies on exactly one of the two simple paths from its endpoints to $G$.

Equivalently, every edge is oriented toward the endpoint that is closer to $G$ along the unique path to the root, so every arc points in the direction of the unique path leading to $G$. This produces the oriented tree with root $G$ in which each vertex $V\ne G$ has exactly one outgoing arc $e[V]$ directed toward its parent on the path to $G$, and $G$ has no outgoing arcs. This completes the construction. ∎