Re: Direct Euler Cycle and de Brujin Sequence

Consequently, I can use this method to build a De Bruijn sequence of
order n > 1 right?

eKo1 wrote:
eKo1 wrote:
I understand now. Let s be the sequence derived from a Euler cycle in
G. Let x_1 x_2 ... x_n be an n-bit string. Is this string in s? Yes.
The sequence derived from the Euler cycle in G will produce both x_1
x_2 ... x_(n - 1) 0 and x_1 x_2 ... x_(n - 1) 1 by its construction and
since x_n has to be one of 0 or 1, then it follows that s is a de
Brujin sequence of order 3.

Here is a more rigorous proof:

Lemma 1. Vertices x_2 ... x_(n - 1) 0 and x_2 ... x_(n - 1) 1 are
adjacent to x_1 x_2 ... x_(n - 1).
Proof. This follows from the definition of G.

Corollary 1. x_1 x_2 ... x_(n - 1), x_2 ... x_(n - 1) 0 and x_1 x_2 ...
x_(n - 1), x_2 ... x_(n - 1) 1 form part of a directed Euler cycle in
G.
Proof. This follows from Lemma 1 and the definition of a Euler cycle.

Theorem 1. The sequence formed from the directed Euler cycle contains
x_1 x_2 ... x_(n - 1) x_n.
Proof. Suppose x_n = 0. Start the Euler cycle from x_1 x_2 ... x_(n -
1), x_2 ... x_(n - 1) 0. By definition, the sequence will start with
x_1 x_2 ... x_(n - 1) 0 which is x_1 x_2 ... x_(n - 1) x_n. The same
argument applies if x_n = 1.

.

Relevant Pages

  • Re: Direct Euler Cycle and de Brujin Sequence
    ... eKo1 wrote: ... Brujin sequence of order 3. ... This follows from Lemma 1 and the definition of a Euler cycle. ... The sequence formed from the directed Euler cycle contains ...
    (comp.theory)
  • Re: Direct Euler Cycle and de Brujin Sequence
    ... be a directed Euler cycle in G. ... The sequence is 000001100111111000. ... this sequence is not a de Brujin sequence. ... edge corresponds to adding one symbol to the back of the sequence. ...
    (comp.theory)
  • Re: Direct Euler Cycle and de Brujin Sequence
    ... edge corresponds to adding one symbol to the back of the sequence. ... De Bruijn sequence of order 3. ... The sequence derived from the Euler cycle in G will produce both x_1 ...
    (comp.theory)
  • Re: Direct Euler Cycle and de Brujin Sequence
    ... eKo1 wrote: ... you have correctly shown that you can construct a De Bruijn ... sequence in the alphabet of any order using this method. ...
    (comp.theory)
  • Re: Direct Euler Cycle and de Brujin Sequence
    ... Robby Goetschalckx wrote: ... edge corresponds to adding one symbol to the back of the sequence. ... Check if it is a De Bruijn sequence: ...
    (comp.theory)