De Bruijn'in grafiği
Bir de Bruijn grafiği , belirli bir alfabe üzerindeki tüm uzunluktaki sözcükler arasındaki uzunluk örtüşmelerini göstermeyi mümkün kılan yönlendirilmiş bir grafiktir . Grafikler, 1946'da onları tanımlayan matematikçi Nicolaas Govert de Bruijn'in isimlerini almıştır. Grafikler daha önce, özellikle 1894'te Camille Flye Sainte-Marie ve 1946'da Irving J. Good tarafından daha önce tarif edilmişti.
değil-1{\ displaystyle n-1}değil{\ displaystyle n}
De Bruijn grafik sırası bir alfabe ile birlikte aşağıdaki şekilde harfler imal edilir. Köşeler arasında (etiketlenir) ile eşleşme kelime uzunluğu üzerinde . Eğer ve iki tepe noktaları vardır, bir yoktur yay gelen için ilk harfi çıkarılması ile elde edilen bir kelime varsa son harfi çıkarılması ile elde edilen kelime olarak aynıdır ; diğer bir deyişle, iki harf varsa ve ve bir kelime gibi, ve . Bu nedenle bir yayın varlığı, aynı uzunluktaki iki kelime arasında maksimum örtüşme anlamına gelir.
B(k,değil){\ displaystyle B (k, n)}değil{\ displaystyle n}AT{\ displaystyle A}k{\ displaystyle k}B(k,değil){\ displaystyle B (k, n)}kdeğil{\ displaystyle k ^ {n}}değil{\ displaystyle n}AT{\ displaystyle A}sen{\ displaystyle u}v{\ displaystyle v}sen{\ displaystyle u}v{\ displaystyle v}sen{\ displaystyle u}v{\ displaystyle v}-de{\ displaystyle a}b{\ displaystyle b}x{\ displaystyle x}sen=-dex{\ displaystyle u = balta}v=xb{\ displaystyle v = xb}
Örnekler
Karşıdaki grafik , uzunluktaki sözcükler için ikili bir alfabe üzerine inşa edilmiştir . İkili alfabe üzerinde 3 kelime uzunluğudur:
B(2,3){\ displaystyle B (2; 3)}AT={0,1}{\ displaystyle A = \ {0,1 \}}değil=3{\ displaystyle n = 3}23=8{\ displaystyle 2 ^ {3} = 8}
000, 001, 010, 011, 111, 110, 101, 100{\ displaystyle 000, \ 001, \ 010, \ 011, \ 111, \ 110, \ 101, \ 100}.
Örneğin , uzunluk 2 soneki uzunluk 2 önekine eşit olduğu için yukarıdan yukarıya giden bir yay vardır . Aynı şekilde, üstten giden bir yay vardır top uzunluğu 2 eki çünkü uzunluğu 2 öneki eşittir .
000{\ displaystyle 000}001{\ displaystyle 001}000{\ displaystyle 000}001{\ displaystyle 001}100{\ displaystyle 100}000{\ displaystyle 000}100{\ displaystyle 100}000{\ displaystyle 000}
Grafik , her harf için bir tane olmak üzere köşelerden oluşur. Her köşeden başlangıç yayları, yani yaylar vardır.
B(değil,1){\ displaystyle B (n, 1)}değil{\ displaystyle n}değil{\ displaystyle n}değil2{\ displaystyle n ^ {2}}
Özellikleri
- Bir grafik her köşe sahip giden derecesi ve gelen derece .B(k,değil){\ displaystyle B (k, n)} k{\ displaystyle k} k{\ displaystyle k}
- Sipariş grafiği olan çizgi grafiğidir ve sipariş grafik :B(k,değil){\ displaystyle B (k, n)}değil{\ displaystyle n}B(k,değil-1){\ displaystyle B (k, n-1)}değil-1{\ displaystyle n-1}
- Euler devreleri ve Hamiltoniyenler , çizgi grafiğin inşası ile birbirlerine karşılık gelir . Bu devreler de Bruijn'in süitidir .B(k,değil-1){\ displaystyle B (k, n-1)}B(k,değil){\ displaystyle B (k, n)}
Dinamik sistemler
Şeklin sol tarafındaki gibi bir ikili de Bruijn grafiği çizilebilir, böylece sağda gösterilen Lorenz çekicisi gibi dinamik sistemler teorisinin bir nesnesi gibi görünür .
Bu benzetme basitçe açıklanabilir: de Bruijn grafiği bir Bernoulli kayma modelidirB(k,değil){\ displaystyle B (k, n)}
x↦kx mod 1{\ displaystyle x \ mapsto kx \ {\ bmod {\}} 1}Bernoulli kayması, (aynı zamanda 2x 1 mod fonksiyonu veya diyadik fonksiyonu için bir olan) ergodik dinamik bir sistem , bir bir kaydırma operatörü olarak görülebilir k-adic sayıda . Bu dinamik sistemin yörüngeleri, de Bruijn grafiğindeki yollara karşılık gelir; yarı açık aralığın [0,1 [grafiğin toplamı, yarı açık aralığın her gerçek x'iyle ilişkilendirilir. x'in k tabanındaki gösterimi. Aynı şekilde, de Bruijn grafiğindeki yollar, sonlu tip dinamik bir sistemin yörüngelerine karşılık gelir .
k=2{\ displaystyle k = 2}
kullanım
Notlar ve referanslar
-
Nicolaas Govert de Bruijn , " Bir Kombinatoryal Sorun ", Koninklijke Nederlandse Akademie v. Wetenschappen , cilt. 49,
1946, s. 758–764
-
Camille Flye Sainte-Marie, " Soru 48 ", L'Intermediate des Mathématiciens , cilt. 1,
1894, s. 107–110
-
Irving J. Good, " Normal yinelenen ondalık sayılar ", Journal of the London Mathematical Society , cilt. 21, n o 3,
1946, s. 167–169 ( DOI 10.1112 / jlms / s1-21.3.167 )
-
Daha kesin bir tarih için, şu bilgilere başvurulabilir : Jean Berstel ve Dominique Perrin , " Kombinatoriklerin sözcüklerdeki kökenleri ", European Journal of Combinatorics , cilt. 28, n o 3,2007, s. 996–1022 ( DOI 10.1016 / j.ejc.2005.07.019 , Matematik İncelemeleri 2300777 , çevrimiçi okuyun )
-
Pavel A. Pevzner , Haixu Tang ve Michael S. Waterman, " DNA fragman montajına Eulerian yol yaklaşımı ", Proceedings of the National Academy of Sciences , cilt. 98, n o 17,
2001, s. 9748–9753 ( PMID 11504945 , PMCID 55524 , DOI 10.1073 / pnas.171285098 , Bibcode 2001PNAS ... 98.9748P )
-
Pavel A. Pevzner ve Haixu Tang, " Çift Namlulu Verilerle Parça Birleştirme ", Bioinformatics / ISMB , cilt. 1,
2001, s. 1–9
-
Daniel R. Zerbino ve Ewan Birney, " Velvet: de Bruijn grafikleri kullanarak de novo kısa okuma montajı için algoritmalar ", Genome Research , cilt. 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;">