n维超立方体

摘要: n维超立方体的基础性质

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

n 维超立方体可以简单理解为 n 维空间中边长为 1 的正方体。它有很多非常好的性质，因此是大规模互联网络最通用的拓扑结构。

本文我们给出一些 n 维超立方体比较基础的性质。包括 2 部图、边数、哈密顿回路、对称性等。

n维超立方体的定义

$n$ 维超立方体 $Q_{n} = (V(Q_{n}, E(Q_{n})))$ 的定义为：

$$V(Q_{n}) = \{x_{1}x_{2}\cdots x_{n}: x_{i}\in\{0,1\},i=1,2,\cdots,n\}$$

并且若 $x=x_{1}x_{2}\cdots x_{n}, y=y_{1}y_{2}\cdots y_{n}\in V(Q_{n})$，则：

$$xy \in E(Q_{n}) \Leftrightarrow \sum\limits_{i=1}\limits^{n}|x_{i}-y_{i}| = 1$$

---

• 由定义可知，$Q_{n}$ 是简单图，$V(Q_{n})$ 中的元素与分量取值为 0, 1 的 n 维向量一一对应。而后者有 $2^{n}$，因此 $v(Q_{n}) = 2^{n}$。

• 对于两个 n 维的 01 向量 $x$ 和 $y$，当 $x$ 固定，满足 $\sum\limits_{i=1}\limits^{n}|x_{i}-y_{i}| = 1$ 也就是分量仅有一个不同的 $y$ 有 $n$ 个，因此 $Q_{n}$ 为正则图，$\Delta(Q_{n}) = \delta(Q_{n}) = n$。

• 下图所示分别为 $Q_{1}$，$Q_{2}$，$Q_{3}$，$Q_{4}$：

$Q_{n}$ 是 2 部图

证明 (构造)：

令 $X, Y \subset V(Q_{n})$，其中：

$$X = \{x_{1}x_{2}\cdots x_{n}: x_{1} + x_{2} + \cdots + x_{n} \equiv 0 \mod{2}\} \\ Y = \{y_{1}y_{2}\cdots y_{n}: y_{1} + y_{2} + \cdots + y_{n} \equiv 1 \mod{2}\} \\$$

由 $X, Y$ 的定义，$X\cap Y = \varnothing$，由 $Q_{n}$ 的定义，$X\cup Y = V(Q_{n})$。

如果存在 $x=x_{1}x_{2}\cdots x_{n}$ 以及 $x’=x’_{1}x’_{2}\cdots x’_{n}$ 使得 $xx’ \in E(Q_{n})$，则由 $Q_{n}$ 的定义，有 $\sum\limits_{i=1}\limits^{n}|x_{i} - x’_{i}| = 1$，但这与 $X$ 的定义矛盾。因此 $X$ 中的任意两个顶点不存在 $Q_{n}$ 中的边。

类似地可以证明 $Y$ 中也没有任何两点之间有边相连。因此 $Q_{n}$ 为 2 部划分为 $\{X, Y\}$ 的 2 部图。

边数 $\epsilon(Q_{n}) = n2^{n-1}$

在前面的 $X, Y$ 定义下，记 $E_{X}$，$E_{Y}$ 为 $Q_{n}$ 中与 $X$ 关联和与 $Y$ 关联的边集，则：

$$|E_{X}| = n|X| = \epsilon(Q_{n}) \\ |E_{Y}| = n|Y| = \epsilon(Q_{n}) \\$$

另一方面 $|X| = |Y| = \frac{1}{2}v(Q_{n}) = 2^{n-1}$，因此 $\epsilon(Q_{n}) = n2^{n-1}$。

格雷码是 $Q_{n}$ 的一条哈密顿回路

在文章 格雷码 中我们介绍了格雷码的背景以及相关的算法，并用格雷码解决了问题 【DP难题】力扣1611-使整数变为0的最少操作次数。

这里我们从另一个角度看格雷码，也就是 $Q_{n}$ 上的哈密顿回路。首先回顾格雷码的定义。

格雷码是一个二进制数系统，其中两个相邻数的二进制位只有一位不同。这样在码值上下变化过程中，每次只改变一位码，从而传输、读数的错码率最小。

下面我们给出一种在 $Q_{n}$ 上构造哈密顿回路的方法。

当 $n=2$ 时，考虑 $Q_{2}$ 的顶点 $x=x_{2}x_{1}$，$00 \rightarrow 01 \rightarrow 11 \rightarrow 10$ 构成一条哈密顿路，连接首尾顶点形成哈密顿回路。

$Q_{n-1}$ 上存在一条哈密顿路径，记其为 $C_{n-1}$。

• 将 $Q_{n-1}$ 的哈密顿路经 $C_{n-1}$ 过的顶点标号最左端添加 0，形成 $Q_{n}$ 上的一条路 $\pi_{1}$；
• 将 $Q_{n-1}$ 的哈密顿路经 $C_{n-1}$ 过的顶点标号最左端添加 1，形成 $Q_{n}$ 上的另一条路 $\pi_{2}$，反向后得到 $\pi_{3}$；
• 将 $\pi_{1}$ 终点与 $\pi_{3}$ 起点相连，即形成 $Q_{n}$ 上的一条哈密顿路，将其首尾顶点连接，即得哈密顿回路。

下图是由 $Q_{3}$ 的哈密顿路按以上方法构造 $Q_{4}$ 的哈密顿路的示意图。

按上述方法构造的 $Q_{n}$ 的哈密顿回路，可以递归地构造出格雷码：

• 1 位格雷码有两个码字，排雷顺序为 0, 1
• 假设 n 位格雷码的 $2^{n}$ 个码字给定了排列顺序。
• 将 n 位格雷码的码字加前缀 0 后，按顺序书写；将 n 位格雷码的码字加前缀 1 后，按顺序书写，即得 n + 1 位格雷码。

$Q_{n}$ 是顶点可迁的

$G$ 是顶点可迁图

$\forall u, v \in V(G)$，存在 $G$ 的自同构映射 $f \in \mathrm{Aut}(G)$，使得 $f(u) = v$。

对于任意长度为 $n$ 的 01 向量 $x=(x_{1}, x_{2}, \cdots, x_{n})$，定义 $V(Q_{n})$ 上的映射 $f: V(Q_{n}) \rightarrow V(Q_{n})$，$f(u) = u + x$。由线性代数中的结论，这是平移映射，因此是一一映射。

$$(u, v) \in E(Q_{n}) \Leftrightarrow v - u = e_{i} \Leftrightarrow f(v) - f(u) = e_{i} \Leftrightarrow (f(u), f(v)) \in E(Q_{n})$$

因此 $f$ 是 $Q_{n}$ 的一个自同构映射。这样，任取 $u, v \in V(Q_{n})$ 有 $f(u) = v$。

---