# Tagged: de Bruijn Graph

# Complete Word Tours

Suppose we were to take a finite alphabet of letters, say , and we considered all the possible ‘words’ of a given length. For instance, the worlds of length 2 are:

and there are many of these. Let’s denote the set of length- words using the alphabet by .

What I am interested in now is “For a given and , what is the minimum length string of letters I can write down and still be sure that every word in appears somewhere in it as a substring?”. *Why* might I be interested in such a thing? Because I really should be working on my PhD, that’s why.

Example:

01100

contains every length-2 word of 2 letters, in order 01, 11, 10, 00. It’s of optimal length, too, because if we start with just ’01’ and successively add ‘1’, ‘0’, and ‘0’, we find that at every stage the newly added letter creates a new sub-word not previously seen, and so every element of appears exactly once. We cannot delete a letter to make a shorter string without losing one of the words. Similarly,

0011101000

and

0201221100

are examples of optimal tours through and respectively, as they both have this property that each letter added after the first adds a previously unseen word.

Notice I’ve introduced the terminology *tour* for any string that contains all words in a given , with *optimal tour* being the tour that is of minimum possible length for that and .