(相关资料图)

1、 德布莱英图(de Bruijn graph)是一种重要的图，是由(0，1)序列衍生的图。

2、由数码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。

3、设每个长为n的(0，1)序列(b1，b2，…，bn-1，bn)与一个起点为(b1，b2，…，bn-1)、终点为(b2，b3，…，bn)的有向弧相对应，称具有顶点集{pi：i=1，2，…，2n-1}和上述对应有向弧集的有向图为一个德布莱英图，记为Gn。

4、Gn为有向连通图，且每个顶点处恰有两条入弧和两条出弧，通过给定有向图中每一有向弧恰一次的回路，称为该图的一条有向完全回路，Gn中的有向完全回路与长为N=2n的德布莱英序列一一对应，德布莱英(N.G.de Bruijn)证明：Gn恰有2的2n-1-n次方条有向完全回路。

本文到此分享完毕，希望对大家有所帮助。