德布鲁因图 (De Bruijn graph) 与线图 (Line graph)

德·布鲁因图

参考维基百科：https://en.wikipedia.org/wiki/De_Bruijn_graph

对于$m$ 个符号的$n$ 维德·布鲁因有向图记为$B(m, n)$，其中包含$m^n$ 个节点，每个节点是由$m$ 个符号序列组成的长度为$n$ 的序列。

给定$m$ 个符号集合$S=\{s_1,\cdots, s_m\}$，那么对应的节点集合为

$$V=S^{n}=\left\{\left(s_{1}, \ldots, s_{1}, s_{1}\right),\left(s_{1}, \ldots, s_{1}, s_{2}\right), \ldots,\left(s_{1}, \ldots, s_{1}, s_{m}\right),\left(s_{1}, \ldots, s_{2}, s_{1}\right), \ldots,\left(s_{m}, \ldots, s_{m}, s_{m}\right)\right\}$$

对应的边集合定义：如果一个节点对应的序列可以由另一个节点的对应的序列向左平移一位并加上另一个节点得到，那么这两个节点间存在一条有向边。形式化定义如下

$$E=\left\{\left(\left(t_{1}, t_{2}, \ldots, t_{n}\right),\left(t_{2}, \ldots, t_{n}, s_{j}\right)\right): t_{i} \in S, 1 \leq i \leq n, 1 \leq j \leq m\right\}$$

具备以下属性：

• 如果$n=1$ 表示任一节点间存在边相连，因此图中包含$m^2$ 条边。
• 每个节点包含$m$ 条出边和$m$ 条入边。
• $n$ 维的德·布鲁因图是等价于$n-1$ 维德·布鲁因图的线图，对应的节点结合相同。
• 每个德·布鲁因图都是欧拉型和哈密顿型，即欧拉路径和哈密顿路径是德布鲁因序列。

德·布鲁因图如下所示：

线图

参考维基百科：https://en.wikipedia.org/wiki/Line_graph

在图论中，一个无向图$G$ 的线图表示为$L(G)$，它表示$G$ 的边之间的邻接关系。

$L(G)$ 的构造方法如下：

• 对于$G$ 中的每一条边，在$L(G)$ 中对应一个顶点；
• 对于$G$ 中每两条有一个共同顶点的边，在$L(G)$ 中它们对应的顶点之间做一条边。

例如对于一个简单图，构造过程如下：

Contact