algorithm - 二进制 De-Bruijn 序列中的零和一的总和

Question

我需要证明/反对是否在每个二进制 De-Bruijn 序列中都存在等量的 0 和 1。从我用 n=3 和 n=2 做的几个例子中，我看到序列中有相同数量的 0 和 1，但我真的不知道为什么……我不知道如何将它与 De 联系起来-Bruijn seq。规则

Answer 1

De-Bruijn 序列 B(k, n) 由 k 个符号上的 n 维 De-Bruijn 图的哈密顿路径构成。等价地，一个 (n-1) 维 De-Bruijn 图的欧拉循环。

我们检查 B(2, n)。

引理:每个 De-Bruijn 图都是欧拉图。DB(n) 是平衡的。这是因为我们可以取任何顶点，它是一个长度为 (n − 1) 的序列，删除最后一位，然后在前面添加 0 或 1，这样每个顶点的 in-degree = 2。类似地，我们得到每个顶点的出度 = 2。由于所有顶点的度数都是偶数，通过欧拉，图存在欧拉圈。

我们通过从任何顶点开始执行循环来构造 B(2, n)，添加相应的位/符号，这些位/符号在我们遍历每条边时移入。

假设:DB(2, n)中1的个数等于0的个数。

我们在上面注意到图中每个顶点的出度等于二。这意味着，对于每个顶点，我们必须在序列中记录一个 1 和一个 0。等价地，我们在序列中记录等量的1和0。

由于欧拉循环恰好使用一条边一次，并且恰好访问一个顶点 k=2 次，因此它遵循 DB(2, n) 中 1 的位数等于 0 的位数。