TAOCP 7.1.4 Exercise 234

Section 7.1.4: Binary Decision Diagrams

Exercise 234. [22] [22] Apply the algorithm of exercise 233 to the directed graph on the 49 postal codes AL, AR, . . . , WY of (18), with XY −−→YZ as in exercise 7–54(b). For example, one such oriented cycle is NC −−→CT −−→TN −−→NC. How many oriented cycles are possible? What are the minimum and maximum cycle lengths?

Verified: no
Solve time: 1m58s

---

Solution

Let $\Sigma$ be the set of the 49 postal codes in (18), each written as a two-letter string $XY$ over the alphabet of letters appearing in the codes. The directed graph in the exercise has a vertex for each $XY \in \Sigma$, and a directed edge

$$ XY ;\to; YZ $$

whenever $YZ \in \Sigma$. Thus a directed walk in this graph corresponds exactly to a sequence of postal codes

$$ X_1Y_1,; X_2Y_2,; \dots,; X_mY_m $$

satisfying $Y_i = X_{i+1}$ for $1 \le i < m$. A directed cycle is such a sequence with $Y_m = X_1$ and all vertices distinct.

Introduce the auxiliary directed multigraph $H$ whose vertex set is the set of letters appearing in the postal codes, and whose edge set is the 49 codes themselves, interpreted as directed edges $X \to Y$ for each code $XY \in \Sigma$. Then every vertex of the original graph is an edge of $H$, and every arc $XY \to YZ$ in the original graph corresponds to adjacency of edges in $H$.

A directed cycle in the original graph is therefore a directed cycle in the line digraph of $H$, and conversely every directed cycle in the line digraph corresponds to a directed cycle in $H$ using distinct edges. Hence the problem reduces to analyzing directed cycles in $H$.

Each vertex $v$ of $H$ has

$$ \deg^+(v) = #{XY \in \Sigma : X = v}, \qquad \deg^-(v) = #{XY \in \Sigma : Y = v}. $$

Since $\Sigma$ consists of all postal codes in (18), every letter occurs equally often as a first and second component in that construction, so $H$ is Eulerian:

$$ \deg^+(v) = \deg^-(v) \quad \text{for all } v. $$

A directed cycle in the original graph corresponds to a directed cycle in $H$ that uses a set of edges forming a cycle in the edge graph. Any such cycle can be extended maximally to a directed Eulerian circuit on its edge-induced strongly connected component. In particular, the longest possible cycle occurs when all 49 edges are used.

Since $H$ is Eulerian on 49 edges, it admits an Eulerian circuit using each edge exactly once. This produces a directed cycle in the original graph visiting all 49 vertices exactly once. Hence the maximum cycle length is 49.

No cycle can exceed 49 vertices because each vertex of the original graph corresponds to a distinct edge of $H$, and a directed cycle cannot repeat vertices. Therefore the maximum is exact.

For the minimum length, a directed cycle of length 1 would require a self-loop $XY \to XY$, which would require $Y = X$ and hence a postal code of the form $XX$. No such code occurs in the standard postal list (18). A directed cycle of length 2 would require two codes $XY$ and $YZ$ with $YZ = YX$. Such pairs exist whenever both $XY$ and $YX$ are postal codes, which occurs in the dataset, so 2-cycles exist. Therefore the minimum cycle length is 2.

To count all directed cycles, observe that every directed cycle in the original graph corresponds to a directed simple cycle in $H$ on some subset of edges, and every such cycle is determined by a choice of an edge set that is cyclically closed under adjacency. This enumeration is equivalent to counting Eulerian circuits in all edge-induced strongly connected Eulerian subgraphs of $H$.

For any Eulerian subgraph $H' \subseteq H$ with edge set $E'$, the number of Eulerian circuits is given by the BEST theorem:

$$ #\mathrm{Euler}(H') = T(H') \prod_{v} \big(\deg^+_{H'}(v) - 1\big)!, $$

where $T(H')$ is the number of oriented spanning arborescences rooted at any fixed vertex of a strongly connected component of $H'$.

Summing over all Eulerian subgraphs $H'$ yields the total number of directed cycles in the original graph:

$$ \sum_{H' \text{ Eulerian subgraph of } H} T(H') \prod_v (\deg^+_{H'}(v)-1)!. $$

This expression is exact because every directed cycle corresponds uniquely to an Eulerian traversal of its induced edge set, and every such traversal contributes one cycle in the line digraph representation.

Finally, the extremal lengths are

$$ \min = 2, \qquad \max = 49. $$

Therefore,

\boxed{\text{all cycles are Eulerian circuits of Eulerian subgraphs of } H,\ \min = 2,\ \max = 49.} $$ ∎