9780023606922, Chapter 2, Problem 25E

Prévia do material em texto

Chapter 2, Problem 25E Step-by-step solution Step 1 of 2 A De Bruijn sequence for every n Consider a directed graph That is, a graph with vertex set and edge set {0,1}" where there is an edge from a = to a' = If and only if: This is equivalent to saying there is an edge from a to and only if a is a prefix of some string and a is a suffix of the same string. Step 2 of 2 To begin the proof it should be noted that a De Bruijn sequence of order n is just an Eulerian tour of DBn. Firstly, consider to prove that an Eulerian Tour exists. For that should be This is because we can take any sequence of length n-1 and delete the last digit, then add a 0 or 1 in front, giving the indeg = 2 for each vertex. Similarly, any sequence of length can be taken and delete the first digit, then add a 0 or a 1 to the end, giving the outdeg = 2 for each vertex. Because indeg = outdeg = 2 the graph considered is Since an Eulerian tour exists as long as a graph is balanced, so we know that for all n there exists a binary De Bruijn sequence of order n. Therefore, there exists a De Bruijn sequence for every