9.11. Summary of Relational Properties 347
+0+1+0+0 +1+1+100
11
10
01
+0Figure 9.10 The 2-bit graph.mines your 3-good string from part (a).
(c)Explain why a walk in the graph of Figure 9.10 that includes every every edge
exactly onceprovides a minimum-length 3-good string.^13
(d)Generalize the 2-bit graph to ak-bit digraph,Bk, fork 2 , whereV.Bk/WWD
f0;1gk, and any walk throughBkthat contains every edge exactly once determines
a minimum length.kC1/-good bit-string.^14
What is this minimum length?
Define the transitions ofBk. Verify that the in-degree and out-degree of every
vertex is even, and that there is a positive path from any vertex to any other vertex
(including itself) of length at mostk.
Homework Problems
Problem 9.6. (a)Give an example of a digraph in which a vertexvis on a positive
even-length closed walk, butnovertex is on an even-length cycle.
(^13) The 3-good strings explained here generalize ton-good strings forn 3. They were studied by
the great Dutch mathematician/logician Nicolaas de Bruijn, and are known asde Bruijn sequences.
de Bruijn died in February, 2012 at the age of 94.
(^14) Problem 9.8 explains why such “Eulerian” paths exist.