德布莱英图

德布莱英图(de Bruijn graph)是一种重要的图，是由(0，1)序列衍生的图。由数码0和1组成的序列(c1，c2，…，cr)称为一个(0，1)序列，r称为该序列的长，长为n-1的(0，1)序列共计2n-1个，设每个这样的(0，1)序列(c1，c2，…，cn-1)与一个顶点pi相对应，这里1≤i≤2n-1。设每个长为n的(0，1)序列(b1，b2，…，bn-1，bn)与一个起点为(b1，b2，…，bn-1)、终点为(b2，b3，…，bn)的有向弧相对应，称具有顶点集{pi：i=1，2，…，2n-1}和上述对应有向弧集的有向图为一个德布莱英图，记为Gn。Gn为有向连通图，且每个顶点处恰有两条入弧和两条出弧，通过给定有向图中每一有向弧恰一次的回路，称为该图的一条有向完全回路，Gn中的有向完全回路与长为N=2n的德布莱英序列一一对应，德布莱英(N.G.de Bruijn)证明：Gn恰有2的2n-1-n次方条有向完全回路1。

德布莱英图的概念定****义n维d进位有向de Bruijn图是标号图，记作B(d，n）(d≥2，n≥1)，其结点集记作VB(d,n)，边集记作EB (d,n)，且

，且

如图1所示：

例1 n维2进位有向de Bruijn图B（2，n），其中

，且

德布莱英图的邻接矩阵下面来考察有向de Bruijn图B（2，n）的邻接矩阵。显然，n维2进位有向de Bruijn图B(2，n)是有2n个结点的有向图，且这2n个结点恰是2n个长度为n的二进制数，其中每个结点的入度和出度均为2。若将这2n个结点依次对应为0，1，2，…．2n-1，于是，从结点0到结点0与1各有一条有向边，从结点1到结点2与3各有一条有向边，…，从结点2n-1-1到结点2n-2与2n-1各有一条有向边；而从结点2n-1到结点0与1各有一条有向边，从结点2n-1+1到结点2与3各有一条有向边，…，从结点2n-1到结点2n-2与2n-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，则矩阵An的任意i行j列元素均为1，其中i，j=1，2，…，2n。

一般地，n维d进位有向de Bruijn图B(d，n)是有dn个结点的有向图，且每个结点的入度和出度均为d。

定理2 设n维d进位有向dc Bruijn图B（d，n）（d≥2，n≥1）的邻接矩阵为A，则矩阵An的任意i行j列元素均为1，其中i，j=1，2，…，dn。

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的特征值，则λk是Ak的特征值。

定理5

定理6 设n维d进位有向de Bruijn图B（d，n）（d≥2，n≥1）的邻接矩阵为A，则矩阵An的谱为

其中dn-1与1分别为特征值0与dn的重数。

定理7 n维d进位有向de Bruijn图B（d，n）（d≥2，n≥1）的谱为

其中dn-1与1分别为特征值0与d的重数2。

德布莱英序列德布莱英序列(de Bruijn sequence)亦称完全循环，是一类特殊的组合序列，一个循环是一个依圆周顺序的序列a1a2…ar，即a1在ar之后，且a2…ara1，…，ara1…ar-1都是与a1a2…ar相同的循环.设n是正整数，N=2n，一个由数码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=2n的德布莱英序列是否存在?若存在，有多少个?德布莱英定理断言：对每个正整数n，恰存在 个长为N=2的完全循环，事实上，每个长为N=2n的德布莱英序列恰与德布莱英图Gn中的一条完全回路相对应(见上文“德布莱英图”)。

本词条内容贡献者为:

任毅如 - 副教授 - 湖南大学