De Bruijn-graf

Inom grafteori är en n-dimensionell de Bruijn-graf över m tecken en riktad graf som representerar överlappningar mellan teckensekvenser. Den har mⁿ 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:={s₁,... ,s_m} så är mängden hörn:

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

V=Sⁿ = {s₁...s₁s₁, s₁...s₁s₂, ..., s₁...s₁s_m, s₁...s₂s₁, ..., s_ms_ms_m}

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={((v₁, v₂, ..., v_n), (v₂, ..., v_n, s_i)) : i = 1, ..., m}

Fastän de Bruijn-grafer är uppkallade efter Nicolaas Govert de Bruijn, upptäcktes de oberoende av både de Bruijn och Irving John . Camille Flye Sainte-Marie 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 m² 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.
• 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):

       

Externa länkar

• Weisstein, Eric W., "De Bruijn Graph", MathWorld. (engelska)
• Tutorial on using De Bruijn Graphs in Bioinformatics av Homolog.us