De Bruijnův graf - De Bruijn graph

v teorie grafů, an n-dimenzionální De Bruijnův graf z m symboly je a řízený graf představující přesahy mezi sekvencemi symbolů. Má to mⁿ vrcholy, skládající se ze všech možných délek-n sekvence daných symbolů; stejný symbol se může objevit několikrát za sebou. Pokud máme sadu m symboly ${ displaystyle S: = {s_ {1}, tečky, s_ {m} }}$ pak sada vrcholů je:

${ displaystyle V = S ^ {n} = {(s_ {1}, dots, s_ {1}, s_ {1}), (s_ {1}, dots, s_ {1}, s_ {2 }), dots, (s_ {1}, dots, s_ {1}, s_ {m}), (s_ {1}, dots, s_ {2}, s_ {1}), dots, ( s_ {m}, dots, s_ {m}, s_ {m}) }.}$

Pokud lze jeden z vrcholů vyjádřit jako jiný vrchol posunutím všech jeho symbolů o jedno místo doleva a přidáním nového symbolu na konec tohoto vrcholu, pak má druhý orientovaný okraj k předchozímu vrcholu. Sada oblouků (tj. Směrované hrany) tedy je

${ displaystyle E = {((t_ {1}, t_ {2}, dots, t_ {n}), (t_ {2}, dots, t_ {n}, s_ {j})): t_ {i} v S, 1 leq i leq n, 1 leq j leq m }.}$

Ačkoli jsou De Bruijnovy grafy pojmenovány Nicolaas Govert de Bruijn, objevili je nezávisle oba De Bruijn^[1] a I. J. Dobrý.^[2] Mnohem dříve, Camille Flye Sainte-Marie^[3] implicitně využily jejich vlastnosti.

Vlastnosti

• Li ${ displaystyle n = 1}$ pak podmínka pro libovolné dva vrcholy tvořící hranu drží vakuově, a proto jsou všechny vrcholy spojeny a tvoří celkem ${ displaystyle m ^ {2}}$ hrany.
• Každý vrchol má přesně ${ displaystyle m}$ příchozí a ${ displaystyle m}$ odchozí hrany.
• Každý ${ displaystyle n}$-dimenzionální De Bruijn graf je řádkový digraf z ${ displaystyle (n-1)}$-dimenzionální De Bruijn graf se stejnou sadou symbolů.^[4]
• Každý graf De Bruijn je Eulerian a Hamiltonian. Eulerovy cykly a Hamiltonovské cykly těchto grafů (navzájem ekvivalentní konstrukcí spojnicového grafu) jsou De Bruijn sekvence.

The hranový graf níže je znázorněna konstrukce tří nejmenších binárních De Bruijnových grafů. Jak je vidět na obrázku, každý vrchol ${ displaystyle n}$-dimenzionální graf De Bruijn odpovídá okraji ${ displaystyle (n-1)}$-dimenzionální graf De Bruijn a každá hrana v ${ displaystyle n}$-dimenzionální graf De Bruijn odpovídá dvousměrné cestě v ${ displaystyle (n-1)}$-rozměrný graf De Bruijn.

Dynamické systémy

Binární De Bruijn grafy lze kreslit (dole, vlevo) takovým způsobem, že se podobají objektům z teorie dynamické systémy, tak jako Lorenzův atraktor (dole vpravo):

Tuto analogii lze učinit přísnou: n-dimenzionální m-symbol De Bruijn graf je model Satelitní mapa Bernoulli

${ displaystyle x mapsto mx { bmod {}} 1}$

Mapa Bernoulli (nazývaná také 2x mapa mod 1 pro m = 2) je ergodický dynamický systém, který lze chápat jako jediný posun a m-adic číslo.^[5] Trajektorie tohoto dynamického systému odpovídají procházkám v grafu De Bruijn, kde je korespondence dána mapováním každé skutečné X v intervalu [0,1] k vrcholu odpovídajícímu prvnímu n číslice v základna -m zastoupení X. Ekvivalentně procházky v grafu De Bruijn odpovídají jednostranným trajektoriím podřazení konečného typu.

Směrované grafy dvou B (2, 3) de Bruijn sekvence a a B (2, 4) sekvence. V B (2,3). každý vrchol je navštíven jednou, zatímco v B (2,4) je každá hrana jednou projet.

Vložení podobné tomuto lze použít k ukázce, že binární grafy De Bruijn mají číslo fronty 2^[6] a že mají tloušťka knihy nanejvýš 5.^[7]

Použití

• Nějaký síťová síť topologie jsou grafy De Bruijn.
• The distribuovaná hash tabulka protokol Koorde používá graf De Bruijn.
• v bioinformatika, De Bruijn grafy se používají pro de novo shromáždění sekvenčních čtení do a genom.^{[8][9][10][11][12]}

Viz také

• De Bruijnova sekvence
• De Bruijn torus
• Hammingův graf
• Kautzův graf

Reference

externí odkazy

• Weisstein, Eric W. „De Bruijn Graph“. MathWorld.
• Výukový program k používání De Bruijnových grafů v bioinformatice podle Homolog.us