De Bruijn sequence¶
Can we write \(2^n\) digits of 0s and 1s around a circle such that if we consider all consecutive segments of length \(n\), they produce all \(n\)-bit binary numbers?
Conversion to Hamiltonian Cycle¶
Our first idea for modeling this graph is as follows:
We construct a graph with \(2^n\) vertices, where each vertex represents an \(n\)-tuple of 0s and 1s. And vertex \(a\) has a directed edge to vertex \(b\) if we can remove the last digit of string \(a\) and then add a character to its beginning such that string \(b\) is obtained. Now, the question is equivalent to finding a Hamiltonian cycle in the graph we constructed!
Here we reach a dead end because we have no method to determine whether a graph contains a Hamiltonian cycle or not.
Conversion to Eulerian Tour¶
We construct a graph with \(2^{n-1}\) vertices, where each vertex corresponds to an \(n-1\)-tuple of 0s and 1s. Each vertex, such as \(u\), has exactly two outgoing edges. The outgoing edge labeled with 0 goes to vertex \(w\) such that if we remove the last character of string \(u\) and add 0 to its beginning, the resulting string will be \(w\). The outgoing edge labeled with 1 can be defined similarly.
The main difference between the previous graph and this graph is that in the previous graph, each \(n\)-tuple of 0s and 1s around the circle corresponded to a vertex in the graph. But here, it corresponds to an edge of the graph. And we have converted the problem to finding an Eulerian tour in the graph. (It can be proven that just as the out-degree of each vertex is 2, the in-degree of each vertex is also 2, and the underlying graph is connected, thus it is an Eulerian graph).
Now, if you find an Eulerian tour of the graph and write the digits on its edges sequentially around the circle, our desired arrangement will be obtained!
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at اکتبر 13, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
