Re: Direct Euler Cycle and de Brujin Sequence

eKo1 wrote:


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?

Yes, except that you miss-spelled 'De Bruijn' :-).

robby
.

Relevant Pages

  • Re: Direct Euler Cycle and de Brujin Sequence
    ... Robby Goetschalckx wrote: ... sequence in the alphabet of any order using this method. ... Because each vertex is represented by a bit-string ...
    (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
    ... 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)