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

[szerkesztés]

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 nk+k-1, a ciklikusé pedig nk.

Története

[szerkesztés]

Nevét Nicolaas Govert de Bruijn holland matematikusról kapta,[1] 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.[2]

Képzése

[szerkesztés]
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.[3] Rendezzük sorrendbe az ábécé betűit: a1, a2, ..., an. Az (n,k) típusú De Bruijn-szót a következőképpen képezzük:

  • Írjunk le k darab a1-et.
  • Írjuk be a sor végére azt a legnagyobb indexű ai-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ó.

Jegyzetek

[szerkesztés]
  1. ↑ N. G. de Bruijn, A combinatorial problem, Koninklijke Nederlandse Akademie v. Wetenschappen, 49 (1946) 758–764.
  2. ↑ "We mention a peculiarity concerning the spelling of some Dutch names. When omitting the initials of N. G. de Bruijn, one should capitalizale the word 'de' and furthermore the name should be listed under B." J. H. van Lint, R. M. Wilson: A course in combinatorics (2nd ed.), Cambridge University Press.
  3. ↑ M. H. Martin: A problem in arrangements,Bulletin A.M.S, 40 (1934) 859-864

Források

[szerkesztés]