定義n維d進位有向de Bruijn圖是標號圖,記作B(d,n)(d≥2,n≥1),其結點集記作VB(d,n),邊集記作EB (d,n),且
例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的譜。
(1)k是D的一個特徵值;
(2)對於D的任意特徵值λ,均有|λ|≤k。
定理4 設λ是實方陣A的特徵值,則λ是A的特徵值。
定理6 設n維d進位有向de Bruijn圖B(d,n)(d≥2,n≥1)的鄰接矩陣為A,則矩陣A的譜為
定理7 n維d進位有向de Bruijn圖B(d,n)(d≥2,n≥1)的譜為
德布萊英序列
德布萊英序列(de Bruijn sequence)亦稱完全循環,是一類特殊的組合序列,一個循環是一個依圓周順序的序列a
1a
2…a
r,即a
1在a
r之後,且a
2…a
ra
1,…,a
ra
1…a
r-1都是與a
1a
2…a
r相同的循環.設n是正整數,N=2,一個由數碼0和1組成的循環a
1a
2…a
N,即a
i∈{0,1},i=1,2,…,N,若子序列a
ia
i+1…a
i+n-1(i=1,2,…,N)就是所有可能的N個由數碼0和1組成的有序序列b
1b
2…b
n,則稱該循環是一個完全循環或德布萊英序列。例如n=1時,循環01;n=2時,循環0011,n=3時,循環00010111和00011101均為德布萊英序列。
關於德布萊英序列的主要問題是:對任意正整數n,長為N=2的德布萊英序列是否存在?若存在,有多少個?德布萊英定理斷言:對每個正整數n,恰存在
個長為N=2的完全循環,事實上,每個長為N=2的德布萊英序列恰與德布萊英圖G
n中的一條完全迴路相對應(見上文“德布萊英圖”)。