De Bruijn grafiği - De Bruijn graph

Olarak grafik teorisi , bir boyutlu De Bruijn ve grafik ait semboller a, yönlendirilmiş grafik sembolleri dizisi arasındaki çakışmaları temsil eder. Verilen sembollerin tüm olası uzunluk dizilerinden oluşan köşeleri vardır ; aynı sembol bir dizide birden çok kez görünebilir. Bir sembol kümesi için köşeler kümesi: ${\görüntüleme stili n}$${\görüntüleme stili m}$${\görüntüleme stili m^{n}}$ ${\görüntüleme stili n}$${\görüntüleme stili m}$${\displaystyle S=\{s_{1},\dots ,s_{m}\}}$

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

Köşelerden biri, tüm sembollerini bir yer sola kaydırarak ve bu köşenin sonuna yeni bir sembol ekleyerek başka bir köşe olarak ifade edilebilirse, o zaman sonraki köşe, eski köşeye yönlendirilmiş bir kenara sahiptir. Böylece yaylar kümesi (yani yönlendirilmiş kenarlar)

$${\displaystyle E=\{((t_{1},t_{2},\dots ,t_{n}),(t_{2},\dots ,t_{n},s_{j})):t_ {i}\in S,1\leq i\leq n,1\leq j\leq m\}.}$$

De Bruijn grafikleri, Nicolaas Govert de Bruijn'den sonra adlandırılsa da , bunlar hem De Bruijn hem de IJ Good tarafından bağımsız olarak keşfedilmiştir . Çok daha önce, Camille Flye Sainte-Marie örtük olarak özelliklerini kullandı.

Özellikler

• Bu durumda, herhangi iki köşenin bir kenar oluşturma koşulu boş olarak geçerlidir ve bu nedenle tüm köşeler bir toplam kenar oluşturacak şekilde bağlanır .${\görüntüleme stili n=1}$${\görüntüleme stili m^{2}}$
• Her tepe noktası tam olarak gelen ve giden kenarlara sahiptir.${\görüntüleme stili m}$${\görüntüleme stili m}$
• Her boyutlu De Bruijn ve grafiktir hattı digraph ait semboller, aynı dizi boyutlu De Bruijn ve grafik.${\görüntüleme stili n}$${\görüntüleme stili (n-1)}$
• Her De Bruijn grafiği Eulerian ve Hamiltonyendir . Bu grafiklerin Euler döngüleri ve Hamilton döngüleri (çizgi grafiği yapısı aracılığıyla birbirine denktir) De Bruijn dizileridir .

En küçük üç ikili De Bruijn grafiğinin çizgi grafiği yapısı aşağıda gösterilmiştir. Olarak resimde görülmektedir, her bir köşe bir kenarına boyutlu De Bruijn ve grafik tekabül boyutlu De Bruijn ve grafik, ve her bir kenar olarak iki kenar yoluna boyutlu De Bruijn ve grafik tekabül boyutlu De Bruijn grafiği. ${\görüntüleme stili n}$${\görüntüleme stili (n-1)}$${\görüntüleme stili n}$${\görüntüleme stili (n-1)}$

dinamik sistemler

İkili De Bruijn grafikleri , Lorenz çekicisi gibi dinamik sistemler teorisindeki nesnelere benzeyecek şekilde çizilebilir :

İkili De Bruijn grafiği

Lorenz çekici

Bu analoji titiz yapılabilir: boyutlu -Symbol De Bruijn ve grafik bir modeldir Bernoulli harita${\görüntüleme stili n}$${\görüntüleme stili m}$

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

Bernoulli harita (aynı zamanda 2x 1 ilk mod için ) bir olduğu ergodik tek olduğu anlaşılabilir dinamik sistem, vites değiştirme a m -adic sayıda . Yazışmalar her gerçek haritalama ile verilir De Bruijn ve grafik, yürür bu dinamik sistem tekabül yörüngeleri aralığında ilk karşılık gelen tepe için basamak tabanı - temsilini . Eşdeğer olarak, De Bruijn grafiğindeki yürüyüşler , sonlu tipte tek taraflı bir alt vardiyadaki yörüngelere karşılık gelir . ${\görüntüleme stili m=2}$${\görüntüleme stili x}$${\görüntüleme stili [0,1)}$${\görüntüleme stili n}$${\görüntüleme stili m}$${\görüntüleme stili x}$

İki B  (2, 3) de Bruijn dizisinin ve bir B  (2, 4) dizisinin yönlendirilmiş grafikleri . B(2,3)'de. her köşe bir kez ziyaret edilirken, B (2,4)'de her kenar bir kez geçilir.

Buna benzer gömmeler, ikili De Bruijn grafiklerinin sıra numarası 2 olduğunu ve kitap kalınlığının en fazla 5 olduğunu göstermek için kullanılabilir.

kullanır

• Bazı grid ağ topolojileri De Bruijn grafikleridir.
• Dağılmış karma tablo protokolü Koorde bir De Bruijn ve grafik kullanır.
• Gelen Biyoinformatik , De Bruijn ve grafikler için kullanılan novo düzeneğinin sekanslama bir okur ve genom .

Ayrıca bakınız

• De Bruijn simit
• Hamming grafiği
• Kautz grafiği

Referanslar

Dış bağlantılar

• Weisstein, Eric W. "De Bruijn Grafiği" . Matematik Dünyası .
• Homolog.us'tan Biyoinformatikte De Bruijn Grafiklerini Kullanma Eğitimi