Direct Euler Cycle and de Brujin Sequence
- From: "eKo1" <berndlosert@xxxxxxxxxxxx>
- Date: 16 Oct 2006 23:33:25 -0700
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?
.
- Follow-Ups:
- Re: Direct Euler Cycle and de Brujin Sequence
- From: Robby Goetschalckx
- Re: Direct Euler Cycle and de Brujin Sequence
- Prev by Date: Re: K-regular bipartitie graph
- Next by Date: Re: Direct Euler Cycle and de Brujin Sequence
- Previous by thread: Halting Problem: There are two kinds of people, those who finish what they start and those who ...
- Next by thread: Re: Direct Euler Cycle and de Brujin Sequence
- Index(es):