《超立方体（Hypercube）及其相关算法初探》阅读笔记

· · 算法·理论

from 管晏如 2023 年的论文

简述

超立方体，是一种包含 2^n 个节点，2^{n-1}n 条边的无向图，具有高度对称性。

其在数学界研究可以追溯到上世纪八十年代，也曾出现在 2013 年的江苏省选和 2021 年的欧洲初中生信息学竞赛（eJOI）中，但至今不为选手们熟知。

本文梳理和总结了超立方体的性质，并挖掘了其在 OI 中的应用价值。

定义

记号约定

定义 K_n 表示一个 n 个点的完全图。

定义 C_n 表示一个 n 个点 n 条边的环。

定义 P_n 表示一个 n 个点的链。

定义 N(v) 表示无向图中 v 的邻居集合。

定义 N(V)=\bigcup\limits_{v\in V}N(v)。

定义两个集合 A,B 的笛卡尔积 A\times B=\{(x,y)|x\in A,y\in B\}。

定义两个简单无向图 G_1=(V_1,E_1) 与 G_2=(V_2,E_2) 的笛卡尔积 G_1\times G_2=(V,E)，其中 V=V_1\times V_2，E=\{((x,y),(z,w))|x=z,(y,w)\in E_2 或 (x,z)\in E_1,y=w\}。注意这里的两层括号中，外层括号表示的是一条边，内层括号表示的是 V 中的一个点，用二元组表示。

容易发现笛卡尔积具有结合律（如果不考虑内部括号）。

超立方体的直接定义

对于 n\in Z_+，定义无向图 Q_n=\{V,E\}，其中 V=\{0,1,...,2^n-1\}，E=\{(x,y)|popcount(x\oplus y)=1,x,y\in V\}。

也就是说，两个点连边当且仅当它们的编号在二进制下恰好一位不同（*）。

我们称 Q_n 为 n 阶超立方体。

容易发现 \forall x\in V,deg_{Q_n}(x)=n，所以 |E|=\frac12n|V|=2^{n-1}n。

容易发现 Q_1 同构于 K_2，Q_2 同构于 C_4，Q_3 则为一个三维立方体的骨架。

我们称一条连接 x 与 x\oplus 2^k 的边具有“方向” k（共有 n 种不同方向）。

超立方体的归纳定义

使用笛卡尔积的概念对超立方体进行归纳的定义：

Lemma 2.3.1：令 Q_1=K_2,Q_n=Q_{n-1}\times K_2，则这种定义方式与上面所说的直接定义等价。

证明：考虑归纳。假设 Q_{n-1} 已经为一个 n-1 阶超立方体，可用 0 至 2^{n-1}-1 标号使得连边符合（*），那么 Q_n 就可以分成两个完全同构于 Q_{n-1} 的部分 G_0 和 G_1。

令 \forall v\in V_{G_0} 标号为 v，\forall v\in V_{G_1} 标号为 v+2^{n-1}，则容易验证 G_0 和 G_1 内部连边符合（*），而 G_0 与 G_1 之间只有 v 与 v+2^{n-1} 有边，符合（*）。

将上述结论展开，可得 Q_n=K_2\times K_2\times ...\times K_2（共 n 个 K_2）。

结构视图

通过上述定义，我们已经可以获得一种基本的视图方式（即两个 Q_{n-1} 之间有 2^{n-1} 条边相连）。

我们可以选择二进制下任意一位进行分层，也即令 G_{i,k} 为 V_{i,k}=\{v\in V|v在二进制下的第i位=k\} 的导出子图（0\le i<n,k=0,1）。

同时还有推论 Q_n=Q_{n-m}\times Q_m。

以 m=2 为例，Q_n 可以看做 4 个 Q_{n-2} 组成，不同 Q_{n-2} 之间的边为 2^{n-2} 个 Q_2，也就是 C_4。

接下来还有一种视图方式。将 Q_n 中的点 0\le v<2^n 按照 popcount 分为 n+1 层，那么有：

  1. 第 i 层有 (^n_i) 个点；
  2. 只有相邻层之间有边；
  3. 第 i 层每个点向 i-1 层连 i 条边，向 i+1 层连 n=i 条边。

我们称这种方式为球形视图，并约定 S_i 表示第 i 层的点构成的点集。

无向图上的性质

基本性质

  1. 二分图

将所有点按照 popcount 的奇偶性染成黑色和白色，则任意一条边必然连接一对黑点和白点，这说明 Q_n 是连通二分图。

  1. 直径

无向图直径的定义是两点间最短距离的最大值。

3. 最大独立集 取所有 $popcount$ 为偶数（或奇数）的点，构成大小为 $2^{n-1}$ 的独立集。 若选出的点个数 $>2^{n-1}$，则根据抽屉原理，一定存在两个被选出的点，除了最低位以外都相同，那么它们相邻，与独立集矛盾。 因此 $Q_n$ 最大独立集大小为 $2^{n-1}$。 4. 最小点覆盖 这里最小点覆盖指选取最少的点覆盖所有边。 取所有 $popcount$ 为偶数（或奇数）的点，构成大小为 $2^{n-1}$ 的点覆盖。 $Q_n$ 上共有 $n2^{n-1}$ 条边，每个点度数为 $n$，则至少需选择 $2^{n-1}$ 个点进行覆盖。 因此 $Q_n$ 最小点覆盖大小也为 $2^{n-1}$。 5. 完美匹配 选择 $n$ 种方向中的任意一种将 $Q_n$ 分为上下两层，则两层之间的边会构成一组完美匹配。 也就是所有 $v$ 和 $v\oplus 2^i$ 进行匹配。 后面将会看到 $Q_n$ 具有哈密尔顿回路，因而在哈密尔顿回路上选择相邻点进行匹配也可以构成完美匹配。 6. 自同构性 将所有点编号同时异或 $\Delta$（$0\le\Delta<2^n$）所得到的仍然是 $Q_n$。 类似的，给定一个长为 $n$ 的排列 $p_0,...,p_{n-1}$，令： $$f(v)=\sum\limits_{i=0}^{n-1}[v 在二进制下第 p_i 位为 1]2^i$$ 则 $f$ 为 $V$ 到 $V$ 的一一映射。将所有点编号作用 $f$ 后仍然是 $Q_n$。 ## 例题 1 [JSOI2013] 超立方体 题意：给出一张 $N$ 个点 $m$ 条边的无向图，判断是否同构于一个超立方体，如果符合则给出一种符合条件（\*）的点标号方式。 $2\le N\le32768$。 ### 做法 1 首先检查点数、边数、度数及连通性等基本性质。 接下来假设 $N=2^n,m=2^{n-1}n$ 且每个点度数均为 $n$。 根据自同构的性质，可以假设任意以点编号为 $0$，并以任意顺序假设 $0$ 的邻居为 $1,2,...,2^{n-1}$。 随后从 $0$ 出发做 BFS，得到其余每个点到 $0$ 最短距离 $dist(0,v)$。 根据 $dist(0,v)$ 进行分层，得到球形视图结构。下面假设改图仍然满足球形视图结构的若干基本特征。 首先 $2\le k\le \lfloor\frac{n}{2}\rfloor$ 时，$\forall v\in S_k$，$v$ 的标号应当为满足 $u\in S_{k-1}\cap N(v)$ 的 $u$ 标号的超集。进一步地，若图合法，则 $v$ 的标号恰好为 $S_{k-1}\cap N(v)$ 的点标号并集（即按位或）。 因此依次令 $k$ 取 $2,3,...,\lfloor\frac{n}{2}\rfloor$，即完成了第 $0$ 至 $\lceil\frac{n}{2}\rceil$ 层的标号。 但是因为这时我们已经按顺序确定了 $2^0\sim2^{n-1}$，所以 $2^n-1$ 的所有邻居顺序不再是任意的了。 可以从每个 $2^i$ 节点出发 BFS，找到最短距离为 $n$ 的点，标为 $2^n-1-2^i$。如果这样的点不止一个，那么显然不符合超立方体的球形结构。 最后检查所有边，才能确定是否是超立方体。 时间复杂度 $O(mn)$。 事实上 $k\ge \lceil\frac{n}{2}\rceil$ 时取 $v$ 标号为 $S_{k-1}\cap N(v)$ 内所有点标号并集仍然是正确的，这样直接从上至下完成标号，时间复杂度 $O(m)$。 ### 做法 2 令 $ans_i$ 表示填写了编号 $i$ 的实际节点。假设我们已经通过上面的方法确定 $ans_0$ 与 $ans_{2^i}$（$0\le i<n$）。接下来按照 $i$ 从小到大确定剩余 $ans_i$。 找到原图中两个 $ans_i$ 的邻居 $x=ans_{j_1},y=ans_{j_2}$，满足 $0\le j_1\neq j_2<i,popcount(j_1\oplus i)=popcount(j_2\oplus i)=1$。 根据假设，$popcount(i)>1$，因此 $j_1,j_2$ 存在。 那么原图中 $ans_i$ 应当是 $x$ 和 $y$ 的公共邻居且尚未被标号。下面证明这样的点是唯一的。 注意到 $j_1,j_2$ 的生成方式为将 $i$ 中某一位 $1$ 改为 $0$。不妨假设是最低两位，则 $i\equiv3(\bmod 4),j_1=i-1,j_2=i-2$。 记 $p=i-3$，则容易发现 $j_1$ 和 $j_2$ 有两个公共邻居：$p+3$ 和 $p$。显然 $p+3$ 已经被确定过，所以 $i=p+3$ 时唯一未填公共邻居。 而因为前面每一步选择都是唯一的，所以如果出现不存在或不唯一的情况说明原图不是超立方体。 时间复杂度 $O(2^nn)=O(m)$。 其实上面的讨论能得到更一般的如下结论： 1. $\forall x,y\in V,x\neq y$，若 $popcount(x\oplus y)=2$，则 $x,y$ 恰好有两个公共邻居，否则没有公共邻居。 1. $Q_n$ 共有 $n!2^n$ 种不同点标号方式满足条件（\*）。 ## 例题 2 [CF1543E] The Final Pursuit 题意：在例题 1 的基础上，再给 $Q_n$ 的每个点染 $n$ 种颜色之一，使得每个点的邻居颜色互不相同。输出染色方案或报告无解。 $1\le n\le 16,2\le \sum2^n\le 2^{16}$。 ### 做法 用 $0$ 到 $n-1$ 表示 $n$ 种颜色，并不妨假设 $Q_n$ 的标号已经符合（\*）。 因为每个点的度数都是 $n$，所以每个点的邻居颜色恰好取遍 $0\sim n-1$。 而每种颜色恰好出现 $\frac{2^n}n$ 次，这说明 $n|2^n$，即 $n=2^k(k\in Z_+)$。若 $n$ 不是 $2$ 的幂则无解。 接下来令染色方案如下： $$col(v)=\bigoplus\limits_{v在二进制下第i位为1}i$$ 则由 $\forall u\in N(v)$，$u$ 取遍 $v\oplus 2^i(0\le i<n)$，所以 $\forall u\in N(v)$，$col(u)$ 取遍 $col(v)\oplus i(0\le i<n=2^k)$。这样 $v$ 的邻居颜色就取遍 $0\sim 2^k-1$ 了。 # 偏序集上的性质 对于集合 $V$ 上的一个关系 $A\subseteq V\times V$，记 $x\preceq y\Leftrightarrow (x,y)\in A$，则我们称 $A$ 为偏序关系，当且仅当 $A$ 具有以下性质： 1. 自反性，即 $\forall x\in V,x\preceq x$； 1. 反对称性，即 $\forall x,y\in V,x\preceq y,y\preceq x\Rightarrow x=y$； 1. 可传递性，即 $\forall x,y,z\in V,x\preceq y,y\preceq z\Rightarrow x\preceq z$。 偏序关系可以记为 $(V,A)$。除了链和空图以外，常见偏序有 $(R,\le),(Z,|)$ 等。 在超立方体上，可以认为 $(V_{Q_n},\subseteq)$ 是一组偏序关系。 为了方便讨论，有时也会把超立方体定点直接看做 $0,1,...,n-1$ 的子集。 不过超立方体本身的边只构成骨架，只有添加所有传递闭包内的边才是严格偏序集。 这里我们重点讨论偏序集 $(2^{[0,1,...,n-1]},\subseteq)$ 上的问题。超立方体的球形结构将会非常重要。 ## 超立方体上的 Dilworth 定理 对于偏序关系 $(V,A)$，称子集 $V'\subseteq V$ 为反链，当且仅当不存在 $x,y\in V',x\neq y$ 满足 $x\preceq y$。 定义最大反链为 $|V'|$ 最大的反链。 称 $V$ 的一种划分 $V_1,V_2,\dots,V_k$ 是链覆盖，当且仅当 $\forall1\le i\le k$，$V_i$ 中的元素 $d_1,d_2,\dots,d_i$ 可以按一定顺序排列满足 $d_1\preceq d_2\preceq \dots\preceq d_i$。 定义最小链覆盖为 $k$ 最小的链覆盖方案。 Dilworth 定理告诉我们，最大反链与最小链覆盖的大小相等。 我们先构造超立方体上的最小链覆盖。 注意到“球形”结构的每一层都构成反链，反链中的元素必然不能位于同一条链上，所以最小链覆盖 $\ge|S_{\lfloor\frac n2\rfloor}|$。 **Lemma 4.3.1**：对于 $0\le i\le n-1$，$S_i$ 与 $S_{i+1}$ 之间构成的二分图有关于点数较少一边的完美匹配。 **证明**：根据之前所述的性质，该图中 $S_i$ 一侧点度数均为 $n-i$，$S_{i+1}$ 一侧度数均为 $i+1$。故这是一个正则二分图，满足 Hall 定理，因而存在关于点数较少一边的完美匹配。 --- 现在我们从第 $\lfloor \frac n2\rfloor$ 层出发，初始时令 $S_{\lfloor\frac n2\rfloor}$ 内每个元素单独构成一条链，然后朝第 $0$ 层方向拓展链。根据 **Lemma 4.3.1**，可以覆盖到上半部分所有点。 同理，从 $\lceil\frac n2\rceil$ 层出发可以覆盖到下半部分所有剩余的点。 $n$ 为奇数时 $S_{\lfloor\frac n2\rfloor}$ 与 $S_{\lceil\frac n2\rceil}$ 存在完美匹配，也可以相连。 于是我们就构造完成了大小为 $|S_{\lfloor\frac n2\rfloor}|$ 的链覆盖。 另一方面，上述覆盖方案中一个反链与每条链都至多只有一个公共元素，所以 $S_{\lfloor\frac n2\rfloor}$ 与 $S_{\lceil\frac n2\rceil}$ 都是取到大小最大值的反链。 ### 最大反链另证 如果只证明最大反链的上界，最小链覆盖是不需要的。 **Theorem 4.3.2（Sperner 定理）**：$(Q_n,\subseteq)$ 的最大反链 $\le C^{\lfloor\frac n2\rfloor}_n$。 **证明**：假设 $Q_n$ 上一个反链 $S=\{v_1,v_2,\dots,v_m\}$，$\forall 1\le i\le m$，$v_i\subseteq \{0,1,\dots,n-1\}$。 令 $F(v_i)=\{\pi|\{\pi_0,\pi_1,\dots,\pi_{v_i-1}\}=v_i\}$，其中 $\pi$ 为 $0$ 到 $n-1$ 的排列。 则由 $S$ 反链的条件，所有 $F(v_i)$ 应当无交 $\Rightarrow\sum\limits_{i=1}^m|F(v_i)|\le n!$。 另一方面，$|F(v_i)|=(n-|v_i|)!(|v_i|)!$，在 $|v_i|=\lfloor\frac n2\rfloor$ 或 $\lceil\frac n2\rceil$ 时取到最小值。 所以 $m\le\frac{n!}{(n-\lfloor\frac n2\rfloor)!\lfloor\frac n2\rfloor!}=C^{\lfloor\frac n2\rfloor}_n$。 --- ## 莫比乌斯反演 对于偏序集 $(V,A)$，记 $\mathscr A=\{f:V\times V\rightarrow R|\forall x,y\in V,f(x,y)\neq 0\Rightarrow x\preceq y\}$。函数 $f$ 也可以看做是大小为 $|V|\times|V|$ 的实数矩阵（这里仅讨论 $|V|$ 有限的情况）。 容易发现全 $0$ 矩阵 $\in\mathscr A$，$I\in\mathscr A$。 **Lemma 4.4.1**：若矩阵 $\alpha\in\mathscr A$ 可逆，则 $\alpha^{-1}\in\mathscr A$。 **证明**：将 $V$ 中元素按拓扑序排列，不妨假设 $\alpha$ 为上三角矩阵。 则 $\alpha$ 可逆说明 $\alpha$ 的主对角线上非 $0$ 且 $\alpha^{-1}$ 也是上三角矩阵。 对于 $\forall x,y\in V,x\npreceq y$，我们希望找到一个合法拓扑序使 $y$ 在 $x$ 前面。这可以通过添加 $y$ 到 $x$ 的边做到。 因而在这种拓扑序下，$x,y$ 被变换到了 $\alpha^{-1}$ 的下三角区，即 $\alpha^{-1}(x,y)=0$。 对于不同 $x\npreceq y$ 拓扑序可能不同但结论相同，所以 $\alpha^{-1}\in\mathscr A$。 --- 记 $(V,A)$ 的特征值矩阵 $Z$ 为 $Z(x,y)=[x\preceq y]$，易得 $Z\in\mathscr A$。根据 **Lemma 4.4.1**，有 $\mu=Z^{-1}\in A$。这里的 $\mu$ 就是我们熟知的莫比乌斯反演。 ### 莫比乌斯矩阵的性质 根据 $Z\times \mu=I$，对于 $x,y\in V$ 有： $$\tag{**} \sum\limits_{x\le z\le y}\mu(z,y)=[x\preceq y]$$ 进一步，$\mu(x,x)=1$，并由 **Lemma 4.4.1** 可知，$x\npreceq y$ 时 $\mu(x,y)=0$。另一种说明方法是：如果不成立，可以固定 $y$，取 $x\npreceq y$ 为满足 $\mu(x,y)\ne 0$ 的极大元，由 $(**)$ 有 $\exist x\prec z\npreceq y,\mu(z,y)\neq 0$，矛盾。 根据 $(**)$ 式，我们可以按照 $dist(x,y)$ 从小到大的顺序填写 $\mu(x,y)$。 $\mu$ 的意义在于对于任意函数 $f:V\rightarrow R$ 若 $g(x)=\sum\limits_{y\preceq x}f(y)$ 则 $f(x)=\sum\limits_{y\preceq x}\mu(y,x)g(y)$。有时直接求解 $f$ 较为困难，可以先求出 $g$ 再用莫反求出 $f$。 一种常见应用是在求解数论函数方面，对应偏序集 $(Z_+,|)$。事实上，如果把 $V$ 限定为某个正整数 $n$ 的所有约数（$n=\prod\limits_{i=1}^k p_i^{a_i}$），那么该偏序集结构同构于 $P_{a_1+1}\times P_{a_2+1}\times\dots\times P_{a_k+1}$。这说明数论在某种意义上是偏序集的特例。 ### 超立方体上的莫比乌斯反演 在超立方体 $Q_n$ 上，注意到集合 $A$ 的传递闭包同构于 $Q_{n-|A|}$，这表明 $\forall A\subseteq B$，有 $\mu(A,B)=\mu(\varnothing,B\backslash A)$。因而我们只要考虑所有的 $\mu(\varnothing,?)$。 按照 $i=1,2,\dots,n$ 的顺序，填写 $\mu(\varnothing,A)(A\in S_i)$。由对称性，得到每一层上的 $\mu(\varnothing,A)$ 都是相等的，不妨记为 $\mu(\varnothing,S_i)$。 根据 $\sum\limits_{j=0}^i(-1)^jC_i^j=0$ 的恒等式（$i>0$），我们容易归纳证明 $\mu(\varnothing,S_i)=(-1)^i$。 一般地，$A\subseteq B$ 时 $\mu(A,B)=(-1)^{|B|-|A|}$。这揭示了我们常用的容斥原理的实质。 # 超立方体包含的子图 ## 环 **Lemma 5.1.1**：$Q_n$ 有哈密尔顿回路。 **证明**： $Q_n$ 上的哈密尔顿回路即格雷码。 简述一种较常见的格雷码构造方法（设 $G_n$ 表示长为 $2^n$ 的格雷码），$G_1=\{0,1\}$。$\forall n\ge 2$，我们令 $G_n$ 为如下序列： $$G_{n-1}(0),G_{n-1}(1),\dots,G_{n-1}(2^{n-1}-1),G_{n-1}(2^{n-1}-1)+2^{n-1},\dots,G_{n-1}(0)+2^{n-1}$$ 如 $G_2=\{0,1,3,2\}$，$G_3=\{0,1,3,2,6,7,5,4\}$。容易确认这样的序列为排列且相邻两项只有一位不同。 ----- 这样在 $Q_n$ 中就能找到任意长度 $<2^n$ 的简单路径了，那简单环呢？ 因为 $Q_n$ 是二分图，所以显然不包含奇环，而对于偶数： **Lemma 5.1.2**：$\forall 4\le len\le 2^n,2|len$，$Q_n$ 中能找到一个简单环 $C_{len}$。 **证明**：令 $l=\frac{len}2$。取 $G_{n-1}$ 的前 $l$ 项 $d_0\sim d_{l-1}$，则 $$d_0,d_1,\dots,d_{l-1},d_{l-1}+2^{n-1},\dots,d_0+2^{n-1}$$ 是一个长为 $len$ 的简单环。 ----- ### 例 3 给定一组 $Q_n$ 上的完美匹配 （称为红边），要求选择另一组完美匹配（称为蓝边）使得红蓝边交替构成哈密尔顿回路。 ### 做法 首先把命题加强为红边连接的两点不要求在 $Q_n$ 上有边相连，即看做给定 $2^{n-1}$ 对点两两配对。记 $v$ 与 $mat_v$ 配对。 考虑归纳，容易得出 $n=2$ 合法。下面假设 $n-1$ 合法。 把 $Q_n$ 分成两层 $Q_{n-1}$ 记为 $G_0$ 和 $G_1$。 令 $S_i=\{v|v\in G_i,mat_v\in G_{i\oplus 1}\}$，$T_i=\{(v,mat_v)|v,mat_v\in G_i\}$。 容易得到 $|S_0|=|S_1|$ 为偶数。首先考虑 $|S_0|>0$ 的情况。 把 $S_0$ 中的点任意两两配对，根据假设，结合 $T_0$ 中的配对，在 $G_0$ 上能得到一个由配对和蓝边交替构成的环 $C_0$。 那么设 $S_0$ 中的配对边在 $C_0$ 上的出现顺序为 $s_0-s_1---s_2-s_3---\dots---s_{i-2}-s_{i-1}---s_0-s_1$。这里 $---$ 表示一条可能经过多个点的路径，$-$ 表示配对。 接着把 $S_1$ 中的点两两配对：$mat_{s_1}$ 与 $mat_{s_2}$、$mat_{s_3}$ 与 $mat_{s_4}$…… 再次根据假设结合 $T_1$ 中的配对，在 $G_1$ 上得到构造 $C_1$。 这时把 $C_0$ 内 $S_0$ 的配对与 $C_1$ 内 $S_1$ 的配对全都断开，再加入原本的 $(v,mat_v)$，即可获得一组 $Q_n$ 上的解。 而如果 $S_0=S_1=\varnothing$，因为最开始 $G_1$、$G_2$ 的划分方向任意，所以对于任意一对 $(v,mat_v)$ 任选异或值为 $1$ 的一位进行分层即可使 $|S_0|>0$。 ## 网格 这里的网格指 $P_{x_1}\times P_{x_2}\times \dots\times P_{x_k}$。 令 $y_i=\lceil\log_2 x_i\rceil$，则 $n\ge \sum y_i$ 时可以沿用格雷码的结果： 网格中的点 $(\alpha_1,\alpha_2,\dots,\alpha_k)$（$\forall 1\le i\le k,0\le \alpha_i<x_i$）对应 $Q_n$ 上 $G_{y_1}(\alpha_1)\sim G_{y_k}(\alpha_k)$ 二进制下顺次拼接的结果。 ### 例 4 [eJOI2021] 抄作业 给定 $n,m$，要给一个 $n\times m$ 的网格填互不相同的非负整数，使得相邻两数在二进制下只有一位不同。另外要求网格上的最大值最小。 $1\le n,m\le 2000$。 ### 做法 将 $n,m$ 放大到最近的 $2$ 的幂是可行的填法，但是最大值很有可能不优。 因为网格嵌入并不要求格雷码首尾合法，因此可以尝试构造长度任意但是只有中间的相邻合法的格雷码序列。在已知 $Q_n$ 哈密尔顿回路时可以做到： **Lemma 5.2.1**：$\forall n\in Z_+$，存在 $0\sim n-1$ 的排列 $p$ 满足 $\forall 1\le i<n,popcount(p_{i-1}\oplus p_i)=1$。 **证明**：设 $n=\sum\limits_{i=1}^k 2^{d_i},0\le d_1<d_2<\dots<d_k$。 构造 $p$ 为以下序列拼接的结果（其中 $G_d+x$ 表示每一项都加 $x$）： $$G_{d_1}\\G_{d_2}+2^{d_1}\\G_{d_3}+2^{d_1}+2^{d_2}\\\vdots\\G_{d_k}+\sum\limits_{i=1}^{k-1}2^{d_i}$$ 为确保序列拼接处合法，可令 $i$ 是偶数时，$G_{d_i}$ 以 $0$ 开头、以 $1$ 结尾，$i$ 是奇数时，$G_{d_i}

以 1 开头、以 0 结尾。根据 Hypercube 的对称性，这一定可以做到。当然，Lemma 5.1.1 的构造恰有 0,1 相邻，可以直接循环移位。

接着，需要将 p_n 与 p_m 拼到一起，填进网格表。一种方法是如前所述的二进制直接拼接，但是仍然可能不优。

实际上，我们可以在二进制下选择 ⌈\log_2 n⌉ 位填 p_n，余下的 ⌈\log_2 m⌉ 位填 p_m，而不必要是前后缀的拼接。具体最优的选择方式可以通过二维 DP 实现，也可以从最高位开始贪心，每次选择剩余字典序最小的填写。

最后，我们说明这样做的正确性：

Lemma 5.2.2：对于一个合法的方案以及二进制下的某一位 k，两个维度独立。

证明：一个合法的填法为 A(i, j)。

考察 A(i, j), A(i + 1, j), A(i, j + 1), A(i + 1, j + 1)，则它们互不相同，且 A(i, j) 与 A(i + 1, j + 1) 恰为 A(i + 1, j), A(i, j + 1) 在 Hypercube 上的两个公共邻居。

这说明，A(i, j) ⊕ A(i + 1, j) = A(i, j + 1) ⊕ A(i + 1, j + 1)。

进一步地，A(i, j) ⊕ A(i + 1, j) = A(i, k) ⊕ A(i + 1, k)。对于列来说也有类似的结论。

那么，对于行 i 可记 H_i = A(i, j) ⊕ A(i + 1, j)，对于列 j 可记 L_j = A(i, j) ⊕ A(i, j + 1)。易见 H_i 和 L_j 均为 2 的幂。

若结论不成立，即存在二进制下某一位 k 和行 i 列 j 使得 H_i = L_j = 2^k，则考察行 i, i + 1 与列 j, j + 1 的交界处：

A(i,j)=A(i+1,j)\oplus 2^k=A(i,j+1)\oplus 2^k=A(i+1,j+1)

矛盾。

Magic Labeling

基于点的 Magic Labeling

对于无向图 G=(V,E)，定义 f:V\rightarrow\{0,1,\dots,|V|-1\} 为一种基于点的 Magic Labeling 当且仅当 f 为一一映射且存在 \Delta 满足 \forall v\in V,\sum\limits_{(u,v)\in E}f(u)=\Delta。

Lemma 6.1.1：n 为奇数时 Q_n 不存在基于点的 Magic Labeling。

证明：如果存在，那么有 |V|\Delta=\sum\limits_{v\in V}deg(v)f(v)\Rightarrow\Delta=\dfrac 12(2^n-1)n，显然 n 为奇数时 \Delta\notin Z，矛盾。

因此容易发现 n=2 时有解，接下来假设 n\ge 4,2|n。

Lemma 6.1.2：4|n 时 Q_n 不存在基于点的 Magic Labeling。

证明：如果存在，记 F(i)=\sum\limits_{v\in S_i}f(v)。于是在“球形”结构上考虑算两次，能够发现：

F(i-1)\cdot(n-i+1)+F(i+1)\cdot(i+1)=\Delta\cdot|S_i|

代入 i=1 和 i=n-1，有 F_0=F_n\Leftrightarrow F_2=F_{n-2}。进一步有 F_0=F_n\Leftrightarrow F_{2i}=F_{n-2i}。

这说明在 4|n 时 F_0=F_n\Leftrightarrow F_{n/2}=F_{n/2}，所以 f(0)=f(2^n-1)，矛盾。

Theorem 6.1.1：Q_n 存在基于点的 Magic Labeling 当且仅当 n\equiv2(\bmod 4)。

证明：以 n=6 为例，考虑构造一组 6 个长度为 6 的 01 向量使得其线性无关，而且每一维上恰好有 3 个 0 和 3 个 1。

记这六个向量看做二进制数后为 v_0,v_1,\dots,v_5，令 f_u=\bigoplus\limits_{u在二进制下第i位=1}v_i。

因为 v_0\sim v_5 线性无关，所以 f(v) 互不相同，同时还有 \sum\limits_{(u,v)\in E}f(u)=(2^0+2^1+\dots+2^5)\cdot 3，所以这样的 f(v) 为一组合法的 Magic Labeling。

--- ## 基于边的 Magic Labeling 对于无向图 $G=(V,E)$，定义 $f:E\rightarrow\{0,1,\dots,|E|-1\}$ 为一种基于边的 Magic Labeling 当且仅当 $f$ 为一一映射且存在 $\Delta$ 满足 $\forall v\in V,\sum\limits_{(u,v)\in E}f(u,v)=\Delta$。 容易发现 $Q_1$ 存在基于边的 Magic Labeling，而 $Q_2$ 不存在。下面默认 $n>2$。 **Lemma 6.2.1**：$n$ 为奇数时 $Q_n$ 上不存在基于边的 Magic Labeling。 **证明**：如果存在，则 $2^n\Delta=m(m-1),m=n2^{n-1}\Rightarrow\Delta=\dfrac n2(n2^{n-1}-1)$。 $n$ 为奇数时 $\Delta\notin Z$，矛盾。 --- **Lemma 6.2.2**：若二分图 $G=(V,E)$ 由两个哈密尔顿回路叠加而成，则存在一种基于边的 Magic Labeling。 **证明**：设 $n=|V|$，则 $n$ 为偶数。设 $G$ 拆分出的两个哈密尔顿回路为 $C_0,C_1$，并不妨设 $C_0$ 依次经过 $0,1,\dots,n-1$。记 $w(v)=\sum\limits_{(u,v)\in E}f(u,v)$。 令 $\forall 0\le 2i<n,f(2i,2i+1)=i,\forall 0<2i\le n,f(2i-1,2i)=n-i$，其中编号 $\bmod n$，那么： $$w(0)=n/2,\\\forall 1\le i<n,2|i,w(i)=n,\\\forall 1\le i<n,2\nmid i,w(i)=n-1$$ 对于 $C_1$，仍然从 $0$ 出发做类似构造，不过原来填 $x$ 就要改为填 $2n-x-1$。 由于 $G$ 是二分图，$w(v)=n$ 的增量为 $2(2n-1)-n$，$w(v)=n-1$ 的增量为 $2(2n-1)-(n-1)$，否则会出现奇环，同时 $w(0)=\dfrac n2+2(2n-1)-\dfrac n2$，所以 $\forall v,w(v)=2(2n-1)$。 --- **Lemma 6.2.3**：$Q_4$ 存在一种基于边的 Magic Labeling。 **证明**：![](https://sy.hhwdd.com/RequireFile.do?fid=RWaZD53r) 上图将 $Q_4$ 拆成了两个哈密尔顿回路。 再用 **Lemma 6.2.2** 即可获得一种填法。 --- **Lemma 6.2.4**：若 $Q_n(2|n)$ 存在一种基于边的 Magic Labeling，则 $Q_{n+2}$ 也存在。 **证明**：根据点的编号 $\bmod 4$ 可把 $Q_{n+2}$ 拆成四个 $Q_n$，记为 $G_0,G_1,G_2,G_3$。 在每个 $G_i$ 内部沿用 $Q_n$ 填法，并对每条方向为 $j$ 的边增加 $d_{i,j}\cdot T$，其中 $d_{i,j}$ 和 $T$ 为待定常数。 对于四个 $G_i$ 之间的每个 $C_4$，考虑这样的填法：（其中 $x$ 和 $y$ 对于不同的 $C_4$ 不同，但是 $x+y$ 都相同） $$G_0(x+y)-x-G_1(x+y+1)-y+1-G_2(x+y+2)-x+1-G_3(x+y+1)-y-G_0$$ 现在为了使方案合法，$d$ 有以下要求： 1. $\forall 0\le j<n$，$d_{i,j}$ 取遍 $\{0,1,2,3\}$。 2. $s_i=\sum\limits_{j=0}^{n-1}d_{i,j}$，则 $s_0-1=s_1=s_2=s_3+1$。 $n=4$ 时有如下可行解： $$\begin{array}{ccccc}&0&1&2&3\\G_0&3&0&2&2\\G_1&2&3&0&1\\G_2&1&2&3&0\\G_3&0&1&1&3\end{array}$$ 对于一般的偶数 $n$，只需要在上面的矩阵右边交替添加 $[0,1,2,3]^T$ 和 $[3,2,1,0]^T$ 即可。 最后我们需要确定 $T$ 和所有 $x,y$，使得所有边标号互不相同。注意到四个 $G_i$ 内部边的标号的并恰好覆盖 $[iT,iT+n2^{n-1}]$，因此考虑取 $4T=|E|_{Q_{n+2}}$ 即 $T=(n+2)2^{n-1}$，可使未使用的标号构成区间 $[iT+n2^{n-1},(i+1)T]$，容易首尾配对（$x$ 与 $y+1$，$x+1$ 与 $y$）完成标号。 --- 综上，我们有： **Theorem 6.2.1**：对于 $n>2$，$Q_n$ 存在一种基于边的 Magic Labeling 当且仅当 $2|n$。 # 总结 本文从超立方体的基本定义出发，阐释了其作为无向图和偏序集时所具备的优美性质，并分析了若干道与之密切相关的信息学竞赛例题。 最后一节详细讨论了超立方体上 Magic Labeling 的构造问题，将数学与算法相结合，展现了超立方体多种结构视图的巧妙应用。 希望本文能让更多选手了解到超立方体这种独特的数学模型并在未来进行更为深入的研究。