TAOCP 2.3.4.4 Exercise 27

Section 2.3.4.4: Enumeration of Trees

Exercise 27. [**] [M28] Let $U_1,U_2,\ldots,U_p,\ldots,U_q;\ V_1,V_2,\ldots,V_r$ be vertices of a directed graph, where $1\le p\le q$. Let $f$ be any function from the set ${p+1,\ldots,q}$ into the set ${1,2,\ldots,r}$, and let the directed graph contain exactly $q-p$ arcs, from $U_k$ to $V_{f(k)}$ for $p<k\le q$. Show that the number of ways to add $r$ additional arcs, one from each of the $V$'s to one of the $U$'s, such that the resulting directed graph contains no oriented cycles, is $q^{r-1}p$. Prove this by generalizing the canonical representation method; that is, set up a one-to-one correspondence between all such ways of adding $r$ further arcs and the set of all sequences of integers $a_1,a_2,\ldots,a_r$, where $1\le a_k\le q$ for $1\le k<r$, and $1\le a_r\le p$.

Verified: no
Solve time: 5m07s

---

Let

$$ U_1,U_2,\ldots,U_q,\qquad V_1,V_2,\ldots,V_r $$

be vertices of a directed graph. For each $k\in{p+1,\ldots,q}$ there is a fixed arc

$$ U_k\to V_{f(k)}, $$

and these are the only arcs initially present.

We must count the ways to add one arc from each $V_i$ to some $U_j$ so that the resulting graph contains no oriented cycle. The proof is to be obtained by a generalization of the canonical representation method.

1. Structure of the completed graph

After the $r$ new arcs are added, each $V_i$ has outdegree $1$, while each $U_k$ with $k>p$ still has outdegree $1$, and each $U_k$ with $k\le p$ has outdegree $0$.

Hence every directed path alternates

$$ V \to U \to V \to U \to \cdots . $$

Since the vertices $U_1,\ldots,U_p$ have no outgoing arcs, every directed path reaching one of them terminates.

Let us call $U_1,\ldots,U_p$ terminal vertices.

Observe that every directed cycle must contain at least one vertex $V_i$, because the graph has no arcs between two $U$'s or between two $V$'s.

2. Existence of a removable vertex

Consider any acyclic completion.

We claim that some $V_i$ points to a terminal vertex $U_j$ with $j\le p$.

Indeed, if every $V_i$ pointed to some $U_k$ with $k>p$, then every vertex $V_i$ would have a successor, and every $U_k$ with $k>p$ would also have a successor. Starting from any $V_i$ and following successors would therefore produce an infinite directed path in a finite graph, hence a directed cycle, contrary to acyclicity.

Thus at least one $V_i$ points to a terminal vertex.

Let $V_t$ be the largest-indexed vertex having this property. Let

$$ V_t\to U_a,\qquad 1\le a\le p. $$

Delete $V_t$ and its outgoing arc. Also delete every fixed arc

$$ U_k\to V_t. $$

The remaining graph is again of exactly the same form as the original problem, but with $r-1$ vertices of type $V$. Since deleting vertices cannot create a cycle, the remaining graph is acyclic.

This is the recursive step of the canonical representation.

3. Canonical encoding

Given an acyclic completion, define a sequence

$$ (a_1,a_2,\ldots,a_r) $$

recursively as follows.

Choose $V_t$ as above, the largest-indexed $V$-vertex that points to a terminal vertex. Record

$$ a_r=a, $$

where $V_t\to U_a$ and $1\le a\le p$.

Remove $V_t$ and all fixed arcs entering it. Renumber the remaining $V$-vertices in increasing order. Apply the same procedure recursively to the smaller graph. The recursive steps produce

$$ a_1,\ldots,a_{r-1}. $$

At each stage, before the final step, the removed vertex may point to any of the $q$ vertices $U_1,\ldots,U_q$. Therefore

$$ 1\le a_k\le q \qquad (1\le k<r), $$

while at the last stage the removable vertex necessarily points to a terminal vertex, giving

$$ 1\le a_r\le p. $$

Thus every acyclic completion yields a sequence satisfying

$$ 1\le a_k\le q \ (k<r),\qquad 1\le a_r\le p. $$

4. Decoding

Conversely, suppose a sequence

$$ (a_1,\ldots,a_r) $$

is given with

$$ 1\le a_k\le q \ (k<r),\qquad 1\le a_r\le p. $$

We reconstruct the completion recursively.

For $r=1$, add the arc

$$ V_1\to U_{a_1}. $$

Since $a_1\le p$, the graph is acyclic.

Assume recursively that every admissible sequence of length $r-1$ determines a unique acyclic completion of the reduced graph.

Starting from the completion corresponding to

$$ (a_1,\ldots,a_{r-1}), $$

reinsert the deleted vertex $V_t$. Restore all fixed arcs entering $V_t$, namely

$$ U_k\to V_t $$

for those $k$ with $f(k)=t$. Finally add

$$ V_t\to U_{a_r}. $$

Because $a_r\le p$, the vertex $U_{a_r}$ is terminal. Any directed path beginning at $V_t$ therefore reaches $U_{a_r}$ immediately and stops. Hence no directed cycle can contain $V_t$.

The previously constructed part of the graph is acyclic by the induction hypothesis. Therefore the reconstructed graph is acyclic.

Thus every admissible sequence determines a unique acyclic completion.

5. Proof that the constructions are inverse

The encoding removes, at each stage, the largest-indexed $V$-vertex that points to a terminal vertex and records its target.

The decoding inserts vertices back in the reverse order, restoring exactly the deleted fixed arcs and the recorded outgoing arc.

Therefore the decoding reconstructs precisely the graph from which the sequence was obtained.

Conversely, encoding the graph produced by the decoding procedure recovers the same sequence.

Hence the two constructions are mutually inverse and establish a bijection between

$$ {\text{acyclic completions}} $$

and

$$ {(a_1,\ldots,a_r): 1\le a_k\le q \ (k<r),; 1\le a_r\le p}. $$

6. Enumeration

The number of such sequences is

$$ q^{,r-1}p, $$

since there are $q$ choices for each of $a_1,\ldots,a_{r-1}$ and $p$ choices for $a_r$.

By the bijection, the number of ways to add the $r$ arcs so that no oriented cycle is created is

$$ \boxed{q^{,r-1}p}. $$

This is exactly the desired result. ∎