Wykres De Bruijna
De Bruijn wykres jest skierowany wykres , który sprawia, że jest możliwe, aby reprezentować nakładania długości pomiędzy wszystkimi długości słowa w danym alfabetu . Nazwy wykresów pochodzą od matematyka Nicolaasa Goverta de Bruijna, który opisał je w 1946 r. Wykresy zostały już wcześniej opisane, zwłaszcza przez Camille Flye Sainte-Marie w 1894 r. I przez Irvinga J. Gooda w 1946 r.
nie-1{\ displaystyle n-1}
nie{\ displaystyle n}![nie](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
Kolejność grafów de Bruijna na alfabecie z literami jest skonstruowana w następujący sposób. W wierzchołki z są w bijekcji z (są oznakowane) na długość słowa na . Jeśli i są dwoma wierzchołkami, istnieje łuk od do, jeśli słowo otrzymane przez usunięcie pierwszej litery z jest takie samo jak słowo uzyskane przez usunięcie ostatniej litery z ; innymi słowy, jeśli są dwie litery i , i słowo , takie jak i . Obecność łuku oznacza zatem maksymalne zachodzenie na siebie dwóch słów o tej samej długości.
b(k,nie){\ Displaystyle B (k, n)}
nie{\ displaystyle n}
W{\ displaystyle A}
k{\ displaystyle k}
b(k,nie){\ Displaystyle B (k, n)}
knie{\ Displaystyle k ^ {n}}
nie{\ displaystyle n}
W{\ displaystyle A}
u{\ displaystyle u}
v{\ displaystyle v}
u{\ displaystyle u}
v{\ displaystyle v}
u{\ displaystyle u}
v{\ displaystyle v}
w{\ displaystyle a}
b{\ displaystyle b}
x{\ displaystyle x}
u=wx{\ displaystyle u = topór}
v=xb{\ displaystyle v = xb}![v = xb](https://wikimedia.org/api/rest_v1/media/math/render/svg/59773c2f957a060ba4b23972840b2d848a997510)
Przykłady
Wykres obok jest zbudowany na alfabecie binarnym dla słów o długości . Długości 3 słów na alfabetem binarnym to:
b(2,3){\ Displaystyle B (2, 3)}
W={0,1}{\ Displaystyle A = \ {0,1 \}}
nie=3{\ displaystyle n = 3}
23=8{\ Displaystyle 2 ^ {3} = 8}![2 ^ {3} = 8](https://wikimedia.org/api/rest_v1/media/math/render/svg/bb2dded8eba905e4a019b70abad935422b198db4)
000, 001, 010, 011, 111, 110, 101, 100{\ Displaystyle 000 \ 001 \ 010 \ 011 \ 111 \ 110 \ 101 \ 100}![000, \ 001, \ 010, \ 011, \ 111, \ 110, \ 101, \ 100](https://wikimedia.org/api/rest_v1/media/math/render/svg/c18685384178ada12c8430b391344033641503c8)
.
Na przykład istnieje łuk biegnący od góry do góry, ponieważ przyrostek długości 2 jest równy przedrostkowi długości 2 . Podobnie, istnieje łuk biegnący od góry do góry, ponieważ przyrostek długości 2 równa się przedrostkowi długości 2 .
000{\ displaystyle 000}
001{\ displaystyle 001}
000{\ displaystyle 000}
001{\ displaystyle 001}
100{\ displaystyle 100}
000{\ displaystyle 000}
100{\ displaystyle 100}
000{\ displaystyle 000}![000](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e4fc6c26318e380f08d4ace964300ab36ebc789)
Wykres składa się z wierzchołków, po jednym dla każdej litery. Z każdego wierzchołka zaczynają się łuki, więc są łuki.
b(nie,1){\ Displaystyle B (n, 1)}
nie{\ displaystyle n}
nie{\ displaystyle n}
nie2{\ displaystyle n ^ {2}}![n ^ {2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac9810bbdafe4a6a8061338db0f74e25b7952620)
Nieruchomości
- Celu wykres jest wykresem liniowym z rzędu wykresu :b(k,nie){\ Displaystyle B (k, n)}
nie{\ displaystyle n}
b(k,nie-1){\ Displaystyle B (k, n-1)}
nie-1{\ displaystyle n-1}![n-1](https://wikimedia.org/api/rest_v1/media/math/render/svg/fbd0b0f32b28f51962943ee9ede4fb34198a2521)
Systemy dynamiczne
Można narysować binarny wykres de Bruijna, jak po lewej stronie rysunku, tak aby wyglądał jak obiekt teorii układów dynamicznych , jak atraktor Lorenza pokazany po prawej stronie.
Tę analogię można wyjaśnić w prosty sposób: wykres de Bruijna jest modelem przesunięcia Bernoulliegob(k,nie){\ Displaystyle B (k, n)}
x↦kx mod 1{\ displaystyle x \ mapsto kx \ {\ bmod {\}} 1}![x \ mapsto kx \ {\ bmod \} 1](https://wikimedia.org/api/rest_v1/media/math/render/svg/945ff115b25feb1db3baa4414082b1c5143b1db4)
Przesunięcie Bernoulliego (zwane także funkcją 2x mod 1 lub funkcją diadyczną dla ) jest ergodycznym systemem dynamicznym, który można postrzegać jako operator przesunięcia na liczbie k-adycznej . Trajektorie tego dynamicznego systemu odpowiadają ścieżkom na wykresie de Bruijna, z korespondencją, która wiąże się z każdym rzeczywistym x półotwartego przedziału [0,1 [suma wykresu, która odpowiada pierwszym n cyfr w reprezentacja x w podstawie k. Równoważnie ścieżki na grafie de Bruijna odpowiadają trajektoriom systemu dynamicznego typu skończonego .
k=2{\ displaystyle k = 2}![k = 2](https://wikimedia.org/api/rest_v1/media/math/render/svg/0bd301789e1f25a3da4be297ff637754ebee5f5d)
posługiwać się
Uwagi i odniesienia
-
Nicolaas Govert de Bruijn , „ A Combinatorial Problem ”, Koninklijke Nederlandse Akademie v. Wetenschappen , vol. 49,
1946, s. 758–764
-
Camille Flye Sainte-Marie, „ Pytanie 48 ”, L'Intermediaire des Mathématiciens , vol. 1,
1894, s. 107–110
-
Irving J. Good, „ Normal recurring decimals ”, Journal of the London Mathematical Society , t. 21, n o 3,
1946, s. 167–169 ( DOI 10.1112 / jlms / s1-21.3.167 )
-
Bardziej szczegółową historię można znaleźć w: Jean Berstel i Dominique Perrin , „ The origins of combinatorics on words ”, European Journal of Combinatorics , t. 28 N O 3,2007, s. 996–1022 ( DOI 10.1016 / j.ejc.2005.07.019 , Math Reviews 2300777 , czytaj online )
-
Pavel A. Pevzner , Haixu Tang i Michael S. Waterman, „ An Eulerian path approach to DNA fragment assembly ”, Proceedings of the National Academy of Sciences , t. 98 N O 17
2001, s. 9748–9753 ( PMID 11504945 , PMCID 55524 , DOI 10.1073 / pnas.171285098 , Bibcode 2001PNAS ... 98.9748P )
-
Pavel A. Pevzner i Haixu Tang, „ Fragment Assembly with Double-Barreled Data ”, Bioinformatics / ISMB , vol. 1,
2001, s. 1–9
-
Daniel R. Zerbino i Ewan Birney, „ Velvet: algorytmy for de novo short read assembly using de Bruijn graphs ”, Genome Research , vol. 18 N O 5,
2008, s. 821–829 ( PMID 18349386 , PMCID 2336801 , DOI 10.1101 / gr.074492.107 )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">