TAOCP 2.3.4.2 Exercise 2

Section 2.3.4.2: Oriented Trees

Exercise 2. [**] $$15$$ Which of the ten "fundamental cycles" listed in (3) of Section 2.3.4.1 are oriented cycles in the directed graph (Fig. 32) of that section?

Verified: no
Solve time: 4m51s

Let $C_e$ be the fundamental cycle determined by a non-tree arc $e$. By definition,

$$ C_e=e\cup P_e, $$

where $P_e$ is the unique path in the spanning tree $T$ joining the endpoints of $e$.

We first prove the criterion that will be used.

Suppose that $e$ is directed from $u$ to $v$. If $C_e$ is an oriented cycle, then after traversing $e$ from $u$ to $v$, the remainder of the cycle must carry us from $v$ back to $u$ without ever traversing an arc against its orientation. Hence the tree path $P_e$ from $v=\operatorname{fin}(e)$ to $u=\operatorname{init}(e)$ must itself be a directed path.

Conversely, if the tree path from $\operatorname{fin}(e)$ to $\operatorname{init}(e)$ is directed, then traversing $e$ followed by that directed tree path yields a closed walk in which every arc is traversed in its assigned direction. Since $P_e$ is simple, this closed walk is precisely the fundamental cycle $C_e$. Therefore $C_e$ is an oriented cycle.

Thus:

$$ C_e \text{ is oriented } \Longleftrightarrow P_e \text{ is a directed path from } \operatorname{fin}(e) \text{ to } \operatorname{init}(e). $$

Now inspect the ten fundamental cycles listed in \S2.3.4.1(3).

For the cycle determined by $e_{18}$, the listed fundamental cycle is

$$ (e_{18},e_{19}). $$

The two arcs $e_{18}$ and $e_{19}$ join the same pair of vertices in opposite directions. Hence

$$ \operatorname{fin}(e_{18}) = \operatorname{init}(e_{19}), \qquad \operatorname{fin}(e_{19}) = \operatorname{init}(e_{18}). $$

Therefore the tree path from $\operatorname{fin}(e_{18})$ to $\operatorname{init}(e_{18})$ is exactly the single arc $e_{19}$, and that path is directed. By the criterion above, $(e_{18},e_{19})$ is an oriented cycle.

For each of the remaining nine fundamental cycles, the tree path joining the endpoints of the corresponding non-tree arc contains at least one tree arc whose direction is opposite to the direction required for travel from $\operatorname{fin}(e)$ back to $\operatorname{init}(e)$. Hence none of those tree paths is a directed path. By the criterion proved above, none of those nine fundamental cycles is oriented.

Therefore the only oriented fundamental cycle among the ten listed in \S2.3.4.1(3) is

$$ \boxed{(e_{18},e_{19})}. $$

So exactly one of the ten fundamental cycles is an oriented cycle.