De Bruijn grafiği - De Bruijn graph

İçinde grafik teorisi, bir n-boyutlu De Bruijn grafiği nın-nin m semboller bir Yönlendirilmiş grafik sembol dizileri arasındaki örtüşmeleri temsil eder. Var mⁿ köşeler olası tüm uzunluklardan oluşann verilen sembollerin dizileri; aynı sembol bir dizide birden çok kez görünebilir. Eğer setimiz varsa m semboller ${ displaystyle S: = {s_ {1}, noktalar, s_ {m} }}$ o zaman köşeler kümesi:

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

Köşelerden biri, tüm sembollerini bir noktaya sola kaydırarak ve bu köşenin sonuna yeni bir sembol ekleyerek başka bir köşe olarak ifade edilebiliyorsa, o zaman ikincisinin önceki köşeye yönlendirilmiş bir kenarı vardır. Böylece yay seti (yani yönlendirilmiş kenarlar)

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

De Bruijn grafikleri, Nicolaas Govert de Bruijn De Bruijn tarafından bağımsız olarak keşfedildi^[1] ve I. J. İyi.^[2] Çok daha erken, Camille Flye Sainte-Marie^[3] dolaylı olarak özelliklerini kullandı.

Özellikleri

• Eğer ${ displaystyle n = 1}$ daha sonra bir kenar oluşturan herhangi iki köşenin koşulu boş bir şekilde devam eder ve bu nedenle tüm köşeler birbirine bağlanarak toplam ${ displaystyle m ^ {2}}$ kenarlar.
• Her köşe tam olarak ${ displaystyle m}$ gelen ve ${ displaystyle m}$ giden kenarlar.
• Her biri ${ displaystyle n}$boyutlu De Bruijn grafiği, satır digraph of ${ displaystyle (n-1)}$- boyutlu De Bruijn grafiği ile aynı semboller.^[4]
• Her De Bruijn grafiği, Euler ve Hamiltoniyen. Bu grafiklerin Euler döngüleri ve Hamilton döngüleri (çizgi grafik yapısı aracılığıyla birbirine eşdeğer) De Bruijn dizileri.

çizgi grafiği En küçük üç ikili De Bruijn grafiğinin yapısı aşağıda gösterilmektedir. Çizimde görülebileceği gibi, her bir köşe ${ displaystyle n}$boyutlu De Bruijn grafiği, ${ displaystyle (n-1)}$boyutlu De Bruijn grafiği ve her kenar ${ displaystyle n}$boyutlu De Bruijn grafiği, iki kenarlı bir yola karşılık gelir. ${ displaystyle (n-1)}$boyutlu De Bruijn grafiği.

Dinamik sistemler

İkili De Bruijn grafikleri, teorisinden nesnelere benzeyecek şekilde (aşağıda, solda) çizilebilir. dinamik sistemler, benzeri Lorenz çekicisi (aşağıda, sağda):

Bu benzetme titizlikle yapılabilir: n-boyutlu m-sembolü De Bruijn grafiği, Bernoulli haritası

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

Bernoulli haritası (aynı zamanda 2x mod 1 haritası için m = 2) bir ergodik tek olarak anlaşılabilen dinamik sistem vardiya bir m-adic numarası.^[5] Bu dinamik sistemin yörüngeleri De Bruijn grafiğindeki yürüyüşlere karşılık gelir; burada karşılık gelen her bir gerçek x [0,1) aralığında birinciye karşılık gelen tepe noktasına n içindeki rakamlar temel -m temsili x. Aynı şekilde, De Bruijn grafiğindeki yürüyüşler, tek taraflı bir yörüngeye karşılık gelir. sonlu tipin alt kayması.

İki yönlü grafik B (2, 3) de Bruijn dizileri ve bir B (2, 4) dizisi. B (2, 3). her köşe bir kez ziyaret edilirken, B (2,4) 'de her kenar bir kez geçilir.

Buna benzeyen gömüler, ikili De Bruijn grafiklerinin sahip olduğunu göstermek için kullanılabilir. sıra numarası 2^[6] ve sahip oldukları kitap kalınlığı en fazla 5.^[7]

Kullanımlar

• Biraz ızgara ağı topolojiler De Bruijn grafikleridir.
• dağıtılmış hash tablosu protokol Koorde De Bruijn grafiği kullanır.
• İçinde biyoinformatik, De Bruijn grafikleri de novo montaj sıralama bir genetik şifre.^{[8][9][10][11][12]}

Ayrıca bakınız

• De Bruijn dizisi
• De Bruijn torus
• Hamming grafiği
• Kautz grafiği

Referanslar

Dış bağlantılar

• Weisstein, Eric W. "De Bruijn Grafiği". MathWorld.
• Biyoinformatikte De Bruijn Grafiklerini kullanma eğitimi Homolog.us tarafından