De Bruijn-szó

Egy (n,k) típusú De Bruijn-szó az a legrövidebb szó, amely részszóként tartalmazza az összes k hosszúságú szót, melyet egy n betűs ábécé szavaiból képezhetünk.

Értelmezése

Adott egy n betűs A ábécé, amelynek betűiből képezzük az összes k hosszúságú szót. Keressük azt a legrövidebb szót, melyik tartalmazza az összes így képzett k betűs szót. Például, legyen A={0,1}, ekkor n=2, és legyen k=3. Az összes kétbetűs három hosszúságú szó: 000, 001, 010, 011, 100, 101, 110, 111. Ekkor a 0001011100 és 0001110100 szavak mindegyike kielégíti a definíciót, így mindegyik (2,3) típusú De Bruijn-szó. Észrevehető, hogy ha ciklikusan tekintjük a szót, azaz az utolsó betű után következik az első, akkor a 00010111 és 00011101 szavak ciklikus De Bruijn-szavak. Egy (n,k) típusú De Bruijn-szó hossza n^k+k-1, a ciklikusé pedig n^k.

Története

Nevét Nicolaas Govert de Bruijn holland matematikusról kapta, akárcsak a De Bruijn-gráf, de már szanszkrit szövegekben találkozunk ilyen szavakkal. Helyesen De Bruijn-szóként kell írni, nagy kezdőbetűvel. Csak a teljes névben szerepel kisbetűs de formában.

Képzése

B(2,3) De Bruijn-gráf

De Bruijn-szót sok algoritmussal lehet képezni. A legegyszerűbb, ha a megfelelő B(n,k) De Bruijn-gráf egy Hamilton-körét felírjuk (például a mellékelt ábrán: 000, 001, 011, 111, 110, 101, 010, 100), majd egymásra csúsztatjuk a szomszédos szavak azonos betűit (0001110100).

Közismert még a Martin-algoritmus. Rendezzük sorrendbe az ábécé betűit: a₁, a₂, ..., a_n. Az (n,k) típusú De Bruijn-szót a következőképpen képezzük:

• Írjunk le k darab a₁-et.
• Írjuk be a sor végére azt a legnagyobb indexű a_i-t, amelynek odaillesztésével az utolsó k betűből képzett szó először fordul elő.
• Amennyiben nem tudjuk folytatni, a keletkezett szó éppen egy keresett De Bruijn-szó.

Példa: Legyen n=2 és k=3. A betűk sorrendje legyen 0, 1. Ekkor 000-val kezdünk.

A következő három betű mindegyike lehet 1, mert 001, 011, 111 először jelenik meg. Tehát eddig 000111 a kapott szó.

Ezután 1-gyel már nem lehet folytatni, hisz akkor 111 másodszor jelenne meg. Tehát 0001110 az eddigi szó.

Most ismét lehet 1-gyel folytatni, hisz 101 még nem volt, az eredmény eddig 00011101.

Ekkor csak 0-val lehet folytatni, hisz 011 már előfordult: 000111010.

Ezután már csak 0-val tudjuk folytatni (mert 101 már volt): 0001110100.

Mivel 000 és 001 is szerepel már a szóban, sem 1-gyel, sem 0-val nem folytathatjuk, a kapott szó éppen egy De Bruijn-szó.

Források

• Bege Antal, Kása Zoltán: Algoritmikus kombinatorika és számelmélet, Kolozsvári Egyetemi Kiadó, 2006.
• J. H. van Lint, R. M. Wilson: A course in combinatorics (2nd ed.), Cambridge University Press. Chapter 8.