De Bruijn-graf

En tredimensionell de Bruijn-graf över {0,1}

Inom grafteori är en n-dimensionell de Bruijn-graf över m tecken en riktad graf som representerar överlappningar mellan teckensekvenser. Den har mn hörn (noder), vilka består av alla möjliga sekvenser med längden n av de givna tecknen (samma tecken får förekomma mer än en gång i samma sekvens). Om vi har mängden med m tecken S:={s1,... ,sm} så är mängden hörn:

V=Sn = {s1...s1s1, s1...s1s2, ..., s1...s1sm, s1...s2s1, ..., smsmsm}

Om ett hörn kan uttryckas genom att ta bort det första tecknet och lägga till ett annat tecken på slutet av ett annat hörn så har detta senare en riktad kant (eller båge) till det förstnämnda hörnet. Mängden kanter är alltså:

E={((v1, v2, ..., vn), (v2, ..., vn, si)) : i = 1, ..., m}

Fastän de Bruijn-grafer är uppkallade efter Nicolaas Govert de Bruijn, upptäcktes de oberoende av både de Bruijn[1] och Irving John [2]. Camille Flye Sainte-Marie[3] utnyttjade deras egenskaper långt tidigare.

Egenskaper

  • Om n = 1 kommer alla hörn att kunna förbindas med varandra med en kant (vilket tecken som helst kan ju bytas ut mot vilket annat tecken som helst - eller sig själv) och sålunda kommer det att finnas m2 kanter.
  • Varje hörn har exakt m inkommande och exakt m utgående kanter.
  • Varje n-dimensionell de Bruijn-graf är den riktade kantgrafen till den (n-1)-dimensionella de Bruijn-grafen med samma teckenuppsättning.[4]
  • Varje de Bruijn-graf är Eulersk och Hamiltonsk. Eulercyklerna och Hamiltoncyklerna till dessa grafer (som är ekvivalenta med varandra genom kantgrafskonstruktionen) är de Bruijn-sekvenser (av dimension n respektive n - 1).

De tre minsta binära kantgrafernas konstruktion avbildas nedan. Som framgår av illustrationen motsvarar varje hörn i den n-dimensionella de Bruijn-grafen en kant i den (n-1)-dimensionella och varje kant i den n-dimensionella de Bruijn-grafen motsvaras av en tvåkantsväg i den (n-1)-dimensionella.

Dynamiska system

Binära de Bruin-grafer kan ritas (nedan till vänster) på ett sådant sätt att de liknar objekt från teorin för dynamiska system som Lorenzattraktorn (nedan till höger):

       

Referenser

  1. ^ de Bruijn, N. G. (1946). ”A Combinatorial Problem”. Koninklijke Nederlandse Akademie v. Wetenschappen 49: sid. 758–764. 
  2. ^ Good, I. J. (1946). ”Normal recurring decimals”. Journal of the London Mathematical Society 21 (3): sid. 167–169. doi:10.1112/jlms/s1-21.3.167. 
  3. ^ Flye Sainte-Marie, C. (1894). ”Question 48”. L'Intermédiaire Math. 1: sid. 107–110. 
  4. ^ Zhang, Fu Ji; Lin, Guo Ning (1987). ”On the de Bruijn-Good graphs”. Acta Math. Sinica 30 (2): sid. 195–205. 

Externa länkar