英文
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.图示为G3.Gn为有向连通图,且每个顶点处恰有两条入弧和两条出弧.通过给定有向图中每一有向弧恰一次的回路,称为该图的一条有向完全回路.Gn中的有向完全回路与长为N=2n的德布莱英序列一一对应.德布莱英(de Bruijn,N.G.)证明:Gn恰有
22n-1-n
条有向完全回路.