De Bruijnin kaavio
De Bruijn kuvaaja on suunnattu graafi , joka mahdollistaa edustaa pituutta päällekkäisyyksiä välillä kaikkien pituus sanat on tietyn aakkoset . Kaaviot on nimetty matemaatikko Nicolaas Govert de Bruijnin mukaan, joka kuvasi niitä vuonna 1946. Kaaviot on jo kuvattu aiemmin, erityisesti Camille Flye Sainte-Marie vuonna 1894 ja Irving J. Good vuonna 1946.
ei-1{\ displaystyle n-1}
ei{\ displaystyle n}![ei](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
De Bruijn kaavio , jotta on aakkosto , jossa kirjaimet on rakennettu seuraavasti. Kärkipisteet ja ovat bijection kanssa (merkitään sen kanssa) sanan pituus on . Jos ja ovat kaksi kärkeä, on kaari välillä , jos sana, joka saadaan poistamalla ensimmäinen kirjain, on sama kuin sana, joka on saatu poistamalla viimeinen kirjain ; toisin sanoen, jos on kaksi kirjainta ja , ja sana , kuten ja . Kaaren läsnäolo tarkoittaa siis kahden päällekkäisyyttä kahden saman pituisen sanan välillä.
B(k,ei){\ displaystyle B (k, n)}
ei{\ displaystyle n}
AT{\ displaystyle A}
k{\ displaystyle k}
B(k,ei){\ displaystyle B (k, n)}
kei{\ displaystyle k ^ {n}}
ei{\ displaystyle n}
AT{\ displaystyle A}
u{\ displaystyle u}
v{\ displaystyle v}
u{\ displaystyle u}
v{\ displaystyle v}
u{\ displaystyle u}
v{\ displaystyle v}
klo{\ displaystyle a}
b{\ displaystyle b}
x{\ displaystyle x}
u=klox{\ displaystyle u = kirves}
v=xb{\ displaystyle v = xb}![v = xb](https://wikimedia.org/api/rest_v1/media/math/render/svg/59773c2f957a060ba4b23972840b2d848a997510)
Esimerkkejä
Vastakkainen kaavio on rakennettu binäärikirjaimelle pitkiä sanoja varten . Pituus 3 sanaa binary aakkoset ovat:
B(2,3){\ displaystyle B (2,3)}
AT={0,1}{\ displaystyle A = \ {0,1 \}}
ei=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)
.
Esimerkiksi ylhäältä ylöspäin menee kaari, koska pituuden 2 pääte on yhtä kuin pituuden 2 etuliite . Samoin on kaari ylhäältä ylöspäin, koska pituuden 2 pääte on yhtä kuin pituuden 2 etuliite .
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)
Kaavio koostuu pisteistä, yksi kutakin kirjainta kohti. Jokaisesta kärjestä alkaa kaari, joten on kaaria.
B(ei,1){\ displaystyle B (n, 1)}
ei{\ displaystyle n}
ei{\ displaystyle n}
ei2{\ displaystyle n ^ {2}}![n ^ {2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac9810bbdafe4a6a8061338db0f74e25b7952620)
Ominaisuudet
- Jokaisella kaavion kärjellä on lähtevä ja saapuva aste .B(k,ei){\ displaystyle B (k, n)}
k{\ displaystyle k}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
- Järjestys kaavio on viivadiagrammi , että järjestys kaavio :B(k,ei){\ displaystyle B (k, n)}
ei{\ displaystyle n}
B(k,ei-1){\ displaystyle B (k, n-1)}
ei-1{\ displaystyle n-1}![n-1](https://wikimedia.org/api/rest_v1/media/math/render/svg/fbd0b0f32b28f51962943ee9ede4fb34198a2521)
- Eulerin piirit ja hamiltonilaiset vastaavat toisiaan rakentamalla viivakaavion . Nämä piirit ovat de Bruijnin sviittejä .B(k,ei-1){\ displaystyle B (k, n-1)}
B(k,ei){\ displaystyle B (k, n)}![B (k, n)](https://wikimedia.org/api/rest_v1/media/math/render/svg/a78487091d967839c7db971d3282a54612062746)
Dynaamiset järjestelmät
Binaarinen de Bruijn -diagrammi voidaan piirtää kuten kuvan vasemmalle puolelle, niin että se näyttää dynaamisen systeemiteorian kohteelta , kuten oikealla oleva Lorenzin vetovoima .
Tämä analogia voidaan selittää yksinkertaisesti: de Bruijn -graafi on Bernoullin siirtomalliB(k,ei){\ 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)
Bernoullin muutos, jota kutsutaan myös 2x mod 1 -toiminnoksi tai dyadiseksi toiminnoksi , on ergodinen dynaaminen järjestelmä, joka voidaan nähdä k-adic-luvun muutosoperaattorina . Tämän dynaamisen järjestelmän liikeradat vastaavat de Bruijn -graafin polkuja vastaavuudella, joka liittyy puoliavoin välin kullekin todelliselle x: lle [0,1 [graafin summa, joka vastaa ensimmäisen n x: n esitys k-osassa. Vastaavasti de Bruijn -graafin polut vastaavat äärellisen tyyppisen dynaamisen järjestelmän liikeratoja .
k=2{\ displaystyle k = 2}![k = 2](https://wikimedia.org/api/rest_v1/media/math/render/svg/0bd301789e1f25a3da4be297ff637754ebee5f5d)
käyttää
Huomautuksia ja viitteitä
-
Nicolaas Govert de Bruijn , " Kombinatorinen ongelma ", Koninklijke Nederlandse Akademie v. Wetenschappen , voi. 49,
1946, s. 758–764
-
Camille Flye Sainte-Marie, " Kysymys 48 ", L'Intermediaire des Mathématiciens , voi. 1,
1894, s. 107–110
-
Irving J.Good, ” Normal recurring decimals ”, Journal of the London Mathematical Society , voi. 21, n ° 3,
1946, s. 167–169 ( DOI 10.1112 / jlms / s1-21.3.167 )
-
Saat tarkemman historiaa, voi kuulla: Jean Berstel Dominique Perrin , " alkuperä sanojen kombinatoriikan ", European Journal of Combinatorics , vol. 28, n ° 3,2007, s. 996–1022 ( DOI 10.1016 / j.ejc.2005.07.019 , Math Reviews 2300777 , lue verkossa )
-
Pavel A. Pevzner , Haixu Tang ja Michael S. Waterman, “ Eulerian path approach to DNA fragment assembly ”, Proceedings of the National Academy of Sciences , voi. 98, n ° 17,
2001, s. 9748-9753 ( PMID 11504945 , PMCID 55524 , DOI 10,1073 / pnas.171285098 , Bibcode 2001PNAS ... 98.9748P )
-
Pavel A.Pevzner ja Haixu Tang, ” Fragment Assembly with Double-Barreled Data ”, Bioinformatics / ISMB , voi. 1,
2001, s. 1–9
-
Daniel R. Zerbino ja Ewan Birney, " Velvet: algoritmeja de novo lyhytlukemiseen, käyttäen de Bruijn -kuvaajia ", Genome Research , voi. 18, n ° 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;">