对于mmm 个符号的nnn 维德·布鲁因有向图记为B(mn)B(m n)B(mn),其中包含mnm^nmn 个节点,每个节点是由mmm 个符号序列组成的长度为nnn 的序列.
对应的边集合定义:如果一个节点对应的序列可以由另一个节点的对应的序列向左平移一位并加上另一个节点得到,那么这两个节点间存在一条有向边.形式化定义如下
具备以下属性:
如果n=1n=1n=1 表示任一节点间存在边相连,因此图中包含m2m^2m2 条边.
每个节点包含mmm 条出边和mmm 条入边.
nnn 维的德·布鲁因图是等价于n−1n-1n−1 维德·布鲁因图的线图,对应的节点结合相同.
每个德·布鲁因图都是欧拉型和哈密顿型,即欧拉路径和哈密顿路径是德布鲁因序列.
在图论中,一个无向图GGG 的线图表示为L(G)L(G)L(G),它表示GGG 的边之间的邻接关系.
对于GGG 中每两条有一个共同顶点的边,在L(G)L(G)L(G) 中它们对应的顶点之间做一条边.