德布萊英圖

德布萊英圖(de Bruijn graph)是一種重要的圖,是由(0,1)序列衍生的圖。由數碼0和1組成的序列(c1,c2,…,cr)稱為一個(0,1)序列,r稱為該序列的長,長為n-1的(0,1)序列總計2個,設每個這樣的(0,1)序列(c1,c2,…,cn-1)與一個頂點pi相對應,這裡1≤i≤2。設每個長為n的(0,1)序列(b1,b2,…,bn-1,bn)與一個起點為(b1,b2,…,bn-1)、終點為(b2,b3,…,bn)的有向弧相對應,稱具有頂點集{pi:i=1,2,…,2}和上述對應有向弧集的有向圖為一個德布萊英圖,記為Gn。Gn為有向連通圖,且每個頂點處恰有兩條入弧和兩條出弧,通過給定有向圖中每一有向弧恰一次的迴路,稱為該圖的一條有向完全迴路,Gn中的有向完全迴路與長為N=2的德布萊英序列一一對應,德布萊英(N.G.de Bruijn)證明:Gn恰有2的2-n次方條有向完全迴路。

基本介紹

  • 中文名:德布萊英圖
  • 外文名:de Bruijn graph
  • 所屬學科:數學(組合學)
  • 別名:de Bruijn圖
  • 簡介:由(0,1)序列衍生的圖
德布萊英圖的概念,德布萊英圖的鄰接矩陣,de Bruijn圖的譜,德布萊英序列,
定義n維d進位有向de Bruijn圖是標號圖,記作B(d,n)(d≥2,n≥1),其結點集記作VB(d,n),邊集記作EB (d,n),且
,且
如圖1所示:
德布萊英圖
圖1
例1 n維2進位有向de Bruijn圖B(2,n),其中
,且
下面來考察有向de Bruijn圖B(2,n)的鄰接矩陣。顯然,n維2進位有向de Bruijn圖B(2,n)是有2個結點的有向圖,且這2個結點恰是2個長度為n的二進制數,其中每個結點的入度和出度均為2。若將這2個結點依次對應為0,1,2,….2-1,於是,從結點0到結點0與1各有一條有向邊,從結點1到結點2與3各有一條有向邊,…,從結點2-1到結點2-2與2-1各有一條有向邊;而從結點2到結點0與1各有一條有向邊,從結點2+1到結點2與3各有一條有向邊,…,從結點2-1到結點2-2與2-1各有一條有向邊。因此有向de Bruijn圖B(2,n)的鄰接矩陣為
德布萊英圖
另一方面,有向de Bruijn圖B(2,”)的結點和邊的關係如圖3.3.2所示。任取有向de Bruijn圖B(2,,?)的兩個結點T與y,顯然1’與y總是長為n的二進制數0---000.0---001.0---010,…,1-- - 110,1...111中的某一個,於是從圖3.3.2知,從任意結點J‘到任意結點y有且僅有一條長度為n的有向鏈,因而由定理2.5.1得到如下定理。
定理1 設n維2進位有向de Bruijn圖B(2,n)(d≥2,n≥1)的鄰接矩陣為A,則矩陣A的任意i行j列元素均為1,其中i,j=1,2,…,2。
一般地,n維d進位有向de Bruijn圖B(d,n)是有d個結點的有向圖,且每個結點的入度和出度均為d。
定理2 設n維d進位有向dc Bruijn圖B(d,n)(d≥2,n≥1)的鄰接矩陣為A,則矩陣A的任意i行j列元素均為1,其中i,j=1,2,…,d。

de Bruijn圖的譜

求一般圖的譜問題是非常困難的,即使對一些特殊圖類的譜計算也很不容易。de Bruijn圖在計算機磁鼓設計、編碼、VLSI結構設計等領域有著廣泛的套用,同時,de Bruijn圖與超立方體,被認為是真正大型下一代多計算機系統的網際網路。然而,de Bruijn圖的內涵非常豐富,它的許多參數還不十分清楚,下面介紹有向dcBruijn圖B(d,n)(d≥2,n≥1)的譜,該結論是由殷劍宏得出的。
定義 設A是任意n階圖G的鄰接矩陣,矩陣A的特徵多項式稱為圖G的特徵多項式;A的特徵值稱為圖G的特徵值;A的譜稱為圖G的譜。
定理3 設D是有向圖,且
,則:
(1)k是D的一個特徵值;
(2)對於D的任意特徵值λ,均有|λ|≤k。
定理4 設λ是實方陣A的特徵值,則λ是A的特徵值。
定理5
定理6 設n維d進位有向de Bruijn圖B(d,n)(d≥2,n≥1)的鄰接矩陣為A,則矩陣A的譜為
其中d-1與1分別為特徵值0與d的重數。
定理7 n維d進位有向de Bruijn圖B(d,n)(d≥2,n≥1)的譜為
其中d-1與1分別為特徵值0與d的重數。

德布萊英序列

德布萊英序列(de Bruijn sequence)亦稱完全循環,是一類特殊的組合序列,一個循環是一個依圓周順序的序列a1a2…ar,即a1在ar之後,且a2…ara1,…,ara1…ar-1都是與a1a2…ar相同的循環.設n是正整數,N=2,一個由數碼0和1組成的循環a1a2…aN,即ai∈{0,1},i=1,2,…,N,若子序列aiai+1…ai+n-1(i=1,2,…,N)就是所有可能的N個由數碼0和1組成的有序序列b1b2…bn,則稱該循環是一個完全循環或德布萊英序列。例如n=1時,循環01;n=2時,循環0011,n=3時,循環00010111和00011101均為德布萊英序列。
關於德布萊英序列的主要問題是:對任意正整數n,長為N=2的德布萊英序列是否存在?若存在,有多少個?德布萊英定理斷言:對每個正整數n,恰存在
個長為N=2的完全循環,事實上,每個長為N=2的德布萊英序列恰與德布萊英圖Gn中的一條完全迴路相對應(見上文“德布萊英圖”)。

相關詞條

熱門詞條

聯絡我們