0
$\begingroup$

I am not following how wikipedia constructs a de Bruijn sequence from an Eulerian tour here. When our Eulerian tour visits vertices $000,000, 001, 011, 111, 111, 110, 101, 011, 110, 100, 001, 010, 101, 010, 100, 000$, wikipedia constructs the de Bruijn sequence using this as $0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1$. However, to me it seems that the last few vertices have been cut off. Why do we not continue the sequence with $000$? My underdstanding was that we find the de Bruijn sequence from the Eulerian tour by first using the first vertex in its entirety, and then augmenting this by the last digit of every subsequent vertex in the tour. The wikipedia example seems to have done this only up to the fourth to last vertex in the tour. Why did it suddenly stop there, and in what ways have I misunderstood how to construct the de Bruijn sequence from the Eulerian tour?

$\endgroup$
1
  • 4
    $\begingroup$ The cleaner way to state the method is "pick the first entry of each vertex"; then there is no cut-off any more (except of course that the last vertex doesn't count, since it is just the first vertex repeated). This is equivalent to what you said, but doesn't require special-casing the first and the last few vertices. $\endgroup$ Aug 12, 2023 at 11:03

2 Answers 2

0
$\begingroup$

The sequence should be thought of as a cycle: $0000111101100101$ is

\begin{array}{c|c|c} 0&0&0&0&1\\\hline 1&&&&1\\\hline 0&&&&1\\\hline 1&&&&1\\\hline 0&0&1&1&0 \end{array}

$\endgroup$
0
$\begingroup$

Remember that de Bruijn sequences are cyclic. Notice that the 000 you want to add to the end is exactly the beginning of the sequence. Whether you build the sequence as you describe or as Darij suggests in his comment, the goal is to find a length $2^4 = 16$ cyclic sequence containing all binary 4-tuples.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .