Re: Direct Euler Cycle and de Brujin Sequence


Robby Goetschalckx wrote:
Yes, I think so. The sequence from your Euler cycle is 0001011100. Every
edge corresponds to adding one symbol to the back of the sequence. To
create the sequence: write the start node of your graph, and then every
symbol which corresponds to the appropriate edges.
Check if it is a De Bruijn sequence:
000,001,010,011,100,101,110,111 are all in this sequence, so it is indeed a
De Bruijn sequence of order 3.

The proof in the general case is left as an exercise to the reader :-)

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.

Is that OK?

.

Relevant Pages

  • Re: Direct Euler Cycle and de Brujin Sequence
    ... I can use this method to build a De Bruijn sequence of ... eKo1 wrote: ... The sequence derived from the Euler cycle in G will produce both x_1 ... This follows from Lemma 1 and the definition of a Euler cycle. ...
    (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)
  • 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)