基本介紹
德布萊英序列
德布萊英序列
德布萊英序列設n是正整數，N=2 ，一個由數碼0和1組成的循環a₁a₂…a，即，若子序列就是所有可能的N個由數碼0和1組成的有序序列b₁b₂…b，則稱該循環是一個完全循環或德布萊英序列，例如n=1時，循環01;n=2時，循環0011，n=3時，循環00010111和00011101均為德布萊英序列。關於德布萊英序列的主要問題是：對任意正整數n，長為N=2 的德布萊英序列是否存在?若存在，有多少個?德布萊英定理斷言：對每個正整數n，恰存在次冪個長為N=2 的完全循環。事實上，每個長為N=2 的德布萊英序列恰與德布萊英圖G中的一條完全迴路相對應 。
De Bruijn序列的套用與性質簡介
De Bruijn序列是一類重要的非線性移位暫存器序列，它在通信及密碼等領域內有著極為廣泛的套用，複雜度是刻劃這類序列特性的一個重要概念。具有良好偽隨機性質的二元序列廣泛套用於通信、密碼學等多個領域中，例如在流密碼中我們就需要好的二元序列來做為密鑰流。分析和構造具有良好性質的二元序列一直是序列研究中的重要問題。
二元de Bruijn序列是一種特殊的周期為2 的序列，滿足任意一個二元n長向量都在de Brujn序列的一個周期中恰出現一次。 De Bruijn序列具有許多很好的偽隨機性質，在圖論、DNA存儲技術、通信與密碼學中都有重要套用。De Bruijn序列雖然看起來非常簡單，但對它的深入分析卻是非常困難的，尋找de Bruijn序列的新的刻畫和性質，以及尋找新的能更有效地生成更多的de Bruijn序列的算法一直是 de Bruijn序列的研究重點。
德布萊英序列一個二元n階de Bruijn序列s是一個周期為2 的序列，滿足任意一個二元n長向量或n元組，都在S的一個周期中出現恰好一次。
De Bruijn序列具有許多良好的性質：
1)大周期，2 ，它是n階FSR能夠生成的序列的最大周期；
2)平衡性，0和1都出現2 次；
3)n元組平衡性，每個二元n長向量都出現一次；
4)大線性複雜度，它的線性複雜度c(s)滿足2 +n≤c(s)≤2 -1；
德布萊英序列5)De Brujn序列的個數非常多，總個數為。
因此，de Bruijn序列在圖論、DNA排序存儲技術、通信與密碼學等多個領域中都有重要套用 。
德布萊英定理
德布萊英序列
德布萊英序列
德布萊英序列
德布萊英序列
德布萊英序列德布萊英定理是波利亞定理的推廣，若兩置換群A和B分別作用於兩有限集X={x，x，…，x}和Y={y，y，…y}，則可定義冪群B ={(α，β)|α∈A，β∈B}對函式集的作用為。若有，則稱是等價的，記為，~為一等價關係。於是，Y 被分為若干等價類之並，這些等價類稱為函式式樣或函式軌道，德布萊英定理斷言：函式式樣的個數等於
德布萊英序列式中群A的循環指標為
德布萊英序列
德布萊英序列其中β的型為。
哈拉里(F.Harary)推廣了德布萊英定理 。
德布萊英序列設Y為可數集，Y至少含2元，定義權函式為非負整數集；又定義函式f的權
德布萊英序列
德布萊英序列
德布萊英序列
德布萊英序列設k∈R，Y的子集，且|Y|是有限的，。若B(Y)={β(y)|β∈B，y∈Y}，則函式集Y 被冪群B 作用所分出的各個式樣中的函式有等權的充分必要條件是B(Y)=Y，i∈R，若條件B(Y)=Y，滿足i∈R，則可定義式樣F的權為w(F)=w(f)，其中f∈F，記β=β，式中β(y)=β(y)，這裡y∈Y，若權為k的式樣為C個，則式樣依權展開的生成函式為
德布萊英序列於是
德布萊英序列
德布萊英序列式中為A的循環指標，
德布萊英序列
德布萊英序列β的型為。
德布萊英圖
德布萊英序列德布萊英圖是一種重要的圖，是由(0，1)序列衍生的圖.由數碼0和1組成的序列稱為一個(0，1)序列，r稱為該序列的長.長為n-1的(0，1)序列總計2 個.設每個這樣的(0，1)序列(c，c，…，c)與一個頂點p相對應，這裡1≤i≤2 .設每個長為n的(0，1)序列(b，b，…，b，b)與一個起點為(b，b，…，b)、終點為(b，b，…，b)的有向弧相對應.稱具有頂點集{p：i=1，2，…，2 }和上述對應有向弧集的有向圖為一個德布萊英圖，記為G.圖示為G.G為有向連通圖，且每個頂點處恰有兩條入弧和兩條出弧.通過給定有向圖中每一有向弧恰一次的迴路，稱為該圖的一條有向完全迴路.G中的有向完全迴路與長為N=2 的德布萊英序列一一對應，德布萊英(N.G.de Bruijn)證明：G恰有
德布萊英序列條有向完全迴路。
