TAOCP 2.3.4.2: Oriented Trees
Section 2.3.4.2 exercises: 28/28 solved.
Section 2.3.4.2. Oriented Trees
Exercises from TAOCP Volume 1 Section 2.3.4.2: 28/28 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [**] | verified | 41s | |
| 2 | [**] | solved | 4m51s | |
| 3 | [**] | verified | 2m47s | |
| 4 | [**] | verified | 4m34s | |
| 5 | [**] | verified | 1m02s | |
| 6 | [**] | verified | 2m14s | |
| 7 | [**] | verified | 1m49s | |
| 8 | [**] | verified | 2m06s | |
| 9 | [**] | verified | 55s | |
| 10 | [**] | verified | 1m06s | |
| 11 | [**] | verified | 1m11s | |
| 12 | [**] | verified | 1m13s | |
| 13 | [**] | solved | 3m46s | |
| 14 | [**] | verified | 1m07s | |
| 15 | [**] | verified | 1m04s | |
| 16 | [**] | solved | 5m16s | |
| 17 | [**] | solved | 4m12s | |
| 18 | [**] | verified | 1m26s | |
| 19 | [**] | verified | 2m57s | |
| 20 | [**] | verified | 1m13s | |
| 21 | [**] | verified | 3m26s | |
| 22 | [**] | verified | 2m12s | |
| 23 | [**] | verified | 2m03s | |
| 24 | [**] | verified | 51s | |
| 25 | [**] | verified | 3m27s | |
| 26 | [**] | solved | 3m39s | |
| 27 | [**] | solved | 5m54s | |
| 28 | [**] | solved | 1m49s |
TAOCP 2.3.4.2 Exercise 1
Let $(e_1,\ldots,e_n)$ be an oriented walk from $V$ to $V'$.
TAOCP 2.3.4.2 Exercise 2
Let $C_e$ be the fundamental cycle determined by a non-tree arc $e$.
TAOCP 2.3.4.2 Exercise 3
Take three vertices $A,B,C$ and two arcs, A\to B,\qquad C\to B.
TAOCP 2.3.4.2 Exercise 4
A finite directed graph can be topologically sorted if and only if it contains no oriented cycles.
TAOCP 2.3.4.2 Exercise 5
Assume that $G$ contains an oriented walk $(e_1,\ldots,e_n)$ with $n\ge1$ and \operatorname{fin}(e_n)=\operatorname{init}(e_1).
TAOCP 2.3.4.2 Exercise 6
\boxed{\text{True}} Let $G$ be a directed graph that is rooted and contains neither cycles nor oriented cycles.
TAOCP 2.3.4.2 Exercise 7
The claim is **true**: any finite directed graph satisfying (a) and (b) and having no directed cycles must already be an oriented tree, because condition (c) is forced by the other assumptions.
TAOCP 2.3.4.2 Exercise 8
Let $G$ be a finite or locally finite oriented tree in which every vertex $v\neq R$ has exactly one outgoing arc and the root $R$ has no outgoing arc.
TAOCP 2.3.4.2 Exercise 9
Let $T$ be the free tree in Fig.
TAOCP 2.3.4.2 Exercise 10
Let $R$ be the original root, and let V_j,V_{a_1},V_{a_2},\ldots,V_{a_t},R be the unique oriented path from $V_j$ to $R$.
TAOCP 2.3.4.2 Exercise 11
Let the directed graph be processed exactly as in the solution to exercise 2.
TAOCP 2.3.4.2 Exercise 12
The degree of a node in the tree terminology of Section 2.
TAOCP 2.3.4.2 Exercise 13
Let $G$ be a directed graph, possibly infinite, and let $R$ be a root of $G$.
TAOCP 2.3.4.2 Exercise 14
The root of $G'$ is $V_1$, since the arcs of the oriented tree are $e_{01}$ and $e_{21}$.
TAOCP 2.3.4.2 Exercise 15
True.
TAOCP 2.3.4.2 Exercise 16
Let $G$ be the directed graph with vertices $V_1,\dots,V_{13}$, where $V_{13}$ is the center pile, and where for $j\neq 13$ there is an arc e_j:V_j\to V_{b(j)}, $b(j)$ being the value of the bottom ca...
TAOCP 2.3.4.2 Exercise 17
**Corrected Solution to Exercise 2.
TAOCP 2.3.4.2 Exercise 18
For (a), first suppose that $G$ is a free tree and $m=n$.
TAOCP 2.3.4.2 Exercise 19
Let $G$ be a directed graph with vertices $V_0, V_1, \dots, V_n$.
TAOCP 2.3.4.2 Exercise 20
Let $A$ be the incidence matrix of exercise 18.
TAOCP 2.3.4.2 Exercise 21
**Exercise 2.
TAOCP 2.3.4.2 Exercise 22
Let $G$ be a balanced directed graph, so for every vertex $V_j$ the indegree equals the outdegree $\sigma_j$.
TAOCP 2.3.4.2 Exercise 23
We restart from the structure that is actually relevant to the sequence, and we avoid the incorrect passage through Eulerian-trail counting entirely.
TAOCP 2.3.4.2 Exercise 24
Construct a new directed graph $G'$ by replacing each arc $e_j$ of $G$ with $E_j$ parallel arcs from $\operatorname{init}(e_j)$ to $\operatorname{fin}(e_j)$.
TAOCP 2.3.4.2 Exercise 25
We are asked to design a computer representation of directed graphs using **one node per arc**, two link fields `ALINK`, `BLINK`, and two one-bit tag fields `ATAG`, `BTAG`, such that: 1.
TAOCP 2.3.4.2 Exercise 26
**Corrected Solution to Exercise 2.