Wykres De Bruijna

W teorii grafów $n$ -wymiarowy wykres De Bruijna $m$ symboli jest grafem skierowanym reprezentującym nakładanie się sekwencji symboli. Ma $m n$ wierzchołków , składających się ze wszystkich możliwych długości $-n$ ciągów danych symboli; ten sam symbol może pojawiać się wielokrotnie w sekwencji. Dla zbioru $m$ symboli $S = {s 1, \dots, m} zbiór$ s wierzchołków to:

{\ Displaystyle V = S ^ {n} = \ {(s_ {1}, \ kropki, s_ {1}, s_ {1}), (s_ {1}, \ kropki, s_ {1}, s_ {2} }),\kropki ,(s_{1},\kropki,s_{1},s_{m}),(s_{1},\kropki,s_{2},s_{1}),\kropki,( s_{m},\kropki,s_{m},s_{m})\}.}

Jeśli jeden z wierzchołków można wyrazić jako inny wierzchołek, przesuwając wszystkie jego symbole o jedno miejsce w lewo i dodając nowy symbol na końcu tego wierzchołka, to ten ostatni ma krawędź skierowaną do poprzedniego wierzchołka. Zatem zbiór łuków (czyli skierowanych krawędzi) jest

{\ Displaystyle E = \ {((t_ {1}, t_ {2}, \ kropki, t_ {n}), (t_ {2}, \ kropki, t_ {n}, s_ {j})): t_ {i}\in S,1\równoważnik i\równoważnik n,1\równoważnik j\równoważnik m\}.}

Chociaż grafy De Bruijna zostały nazwane na cześć Nicolaasa Goverta de Bruijna , zostały odkryte niezależnie zarówno przez De Bruijna, jak i IJ Gooda . Znacznie wcześniej Camille Flye Sainte-Marie pośrednio korzystała z ich właściwości.

Nieruchomości

Jeśli $n = 1$ , to warunek dla dowolnych dwóch wierzchołków tworzących krawędź jest spełniony próżniowo , a zatem wszystkie wierzchołki są połączone, tworząc w sumie $m 2$ krawędzi.
Każdy wierzchołek ma dokładnie $m krawędzi$ wejściowych i $m$ krawędzi wychodzących.
Każdy $n$ -wymiarowy wykres De Bruijna jest digrafem liniowym $(n - 1)$ -wymiarowego wykresu De Bruijna z tym samym zestawem symboli.
Każdy graf De Bruijna jest eulerowski i hamiltonowski . Cykle Eulera i cykle Hamiltona tych grafów (równoważne sobie poprzez konstrukcję wykresu liniowego) są sekwencjami De Bruijna .

Konstrukcja wykresu liniowego trzech najmniejszych binarnych wykresów De Bruijna jest przedstawiona poniżej. Jak widać na ilustracji, każdy wierzchołek $n$ -wymiarowego grafu De Bruijna odpowiada krawędzi $(n - 1)$ -wymiarowego grafu De Bruijna, a każda krawędź $n$ -wymiarowego grafu De Bruijna odpowiada dwuwymiarowej -krawędziowa ścieżka w $(n - 1)$ -wymiarowym grafie De Bruijna.

Image showing multiple De Bruijn graphs, each the line graph of the previous one

Układy dynamiczne

Binarne grafy De Bruijna można narysować w taki sposób, aby przypominały obiekty z teorii układów dynamicznych , takie jak atraktor Lorenza :

Wykres binarny De Bruijna

atraktor Lorenza

Ta analogia może być ścisła: $n$ -wymiarowy wykres $m$ -symbol De Bruijn jest modelem mapy Bernoulliego

{\ Displaystyle x \ mapsto mx \ {\ bmod {\}} 1.}

Mapa Bernoulliego (zwana także mapą $2 x mod 1$ dla $m = 2$ ) jest ergodycznym układem dynamicznym, który można rozumieć jako pojedyncze przesunięcie liczby $m$ -adycznej . Trajektorie tego układu dynamicznego odpowiadają spacerom w grafie De Bruijna, gdzie zgodność jest dana przez odwzorowanie każdego rzeczywistego $x$ w przedziale $[0,1)$ na wierzchołek odpowiadający pierwszym $n$ cyfrom podstawy - $m$ reprezentacji $x$ . Równoważnie spacery na wykresie De Bruijna odpowiadają trajektoriom w jednostronnym przesunięciu podrzędnym typu skończonego .

Skierowane grafy dwóch sekwencji

B (2,3)

de Bruijna i sekwencji

B (2,4)

. W

B (2,3)

każdy wierzchołek jest odwiedzany raz, podczas gdy w

B (2,4)

każda krawędź jest pokonywana raz.

Osadzeń podobnych do tego można użyć do pokazania, że binarne grafy De Bruijna mają numer kolejki 2 i że mają grubość książki co najwyżej 5.

Używa

Niektóre topologie sieci grid to grafy De Bruijna.
Protokół rozproszonej tablicy skrótów Koorde wykorzystuje graf De Bruijna.
W bioinformatyce wykresy De Bruijna są używane do składania de novo odczytów sekwencjonowania w genomie .

Zobacz też

Linki zewnętrzne

Weisstein, Eric W. „Wykres De Bruijna” . MathWorld .
Samouczek dotyczący korzystania z wykresów De Bruijna w bioinformatyce autorstwa Homolog.us