Re: Direct Euler Cycle and de Brujin Sequence

eKo1 wrote:

Let G be a directed graph with vertices corresponding to all bit
strings of length n - 1. A directed edge exists from x_1 ... x_(n - 1)
to x_2 ... x_n. Show that a directed Euler cycle in G corresponds to a
de Brujin sequence.

I think this problem is bogus because I can produce a quick
counter-example for n - 1 = 2: Let G = (V, E) where V = {00, 01, 11,
10} and E = {(00, 00), (00, 01), (01, 10), (01, 11), (10, 01), (10,
00), (11, 10), (11, 11)}. Let C = (00, 00, 01, 10, 01, 11, 11, 10, 00)
be a directed Euler cycle in G. The sequence is 000001100111111000.
Note that I'm not able to find the substring 0010 in the sequence so
this sequence is not a de Brujin sequence.

Or maybe I'm just understand the problem wrong?

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 :-)

--
Robby Goetschalckx
Department of Computer Science
Catholic University Leuven
Celestijnenlaan 200A
B-3001 Heverlee
Belgium


.

Relevant Pages

  • Re: Cantors definition of set
    ... finite sequence: The domain is a finite set. ... Corresponds to the function: ... You don't find a set theory axiom that deals ...
    (sci.logic)
  • Re: The natural numbers are uncountable
    ... >sequence, there is first element in the sequence, a second element in the ... >sequence, and so on, and so on, hence any simply infinite sequence of unique ... each unique element of M corresponds with a unique element of the set ...
    (sci.logic)
  • Re: Review of Mueckenheims book.
    ... the Waft Maximum of a sequence that does not take on its supremum ... We should distinguish between the COMPLETE TREE Twhich contains ... A path in a tree corresponds to a sequence ... Each element of P_F corresponds to a sequence ...
    (sci.math)
  • Direct Euler Cycle and de Brujin Sequence
    ... Show that a directed Euler cycle in G corresponds to a ... be a directed Euler cycle in G. ... The sequence is 000001100111111000. ... this sequence is not a de Brujin sequence. ...
    (comp.theory)
  • Re: Review of Mueckenheims book.
    ... is not a sequence, nor can it be written as a sequence. ... T_U is a tree. ... Each element of P_F corresponds to a sequence ... An endless path cannot be mapped on a natural number. ...
    (sci.math)