超立方体图 Q_n 是网络拓扑和组合优化中经常出现的一类结构，它的每个顶点都可以用一个长度为 n 的 0/1 二进制串表示。两个顶点之间有边，当且仅当这两个串在恰好一个位置上不同，也就是汉明距离等于 1。要把这种关系转化为 NumPy 邻接矩阵，最容易出错的地方在于顶点顺序。若按照最后一个二进制位划分顶点集合，0 组和 1 组各自包含一个 Q_{n-1}，而跨组边只连接低 n-1 位完全相同的顶点对。这个观察直接给出了一个干净的分块形式。
设 A_{n-1} 表示 Q_{n-1} 的邻接矩阵，I 表示同阶单位矩阵。按照上述分组排序，Q_n 的邻接矩阵可以写成 [[A_{n-1}, I], [I, A_{n-1}]] 这样的 2×2 分块矩阵。左上角和右下角对应两个子立方体内部的边，右上角和左下角对应两条跨组连接。因为跨组连接只发生在低 n-1 位相等的顶点之间，所以非对角块不是任意置换矩阵，而是单位矩阵。
递归块结构是怎么来的
先看一个具体例子。Q_2 有四个顶点，顺序取为 00、01、10、11。00 与 01、10 相邻；01 与 00、11 相邻；10 与 00、11 相邻；11 与 01、10 相邻。把它写成邻接矩阵，就是如下形式：
# Q_2 的邻接矩阵，顶点顺序为 00、01、10、11
A2 = np.array([
[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 1],
[0, 1, 1, 0]
], dtype=int)
把 Q_1 的邻接矩阵记为 A_1 = [[0, 1], [1, 0]]，单位矩阵记为 I_2。上面的 Q_2 矩阵恰好可以拆成四个 2×2 的块：左上和右下都是 A_1，右上和左下都是 I_2。这不是巧合，而是由分组方式决定的。按最后一位分成两组后，组内的顶点仍然只在一个位上不同，所以组内连接继承 Q_{n-1}；跨组的两个顶点如果低 n-1 位相同，它们恰好只差最后一位，也会相连，因此跨组连接就是一一对应的恒等关系。
把这个结构推广到一般 n，就得到递归式 A_n = [[A_{n-1}, I], [I, A_{n-1}]]。递归基准可以取 Q_0，也就是只有一个顶点、没有边的图，其邻接矩阵为 [[0]]。如果希望只处理到 n=1 以上，也可以从 A_1 开始；但从 Q_0 开始的好处是递归函数更加统一，不需要额外区分第一层。
这里要特别注意顶点顺序。矩阵分块的位置取决于你如何排列二进制串。如果按最高位分组而不是最后一位分组，同样也成立，只是分块方式的解释略有不同。关键是每一轮递归使用同一种分组策略，并且跨组块必须是单位矩阵。如果分组顺序混乱，得到的矩阵可能仍然是某个同构超立方体的邻接矩阵，但行和列的顶点顺序会不一致。
np.block 的分块拼接语义
np.block 接收一个嵌套列表，列表的每一层对应分块矩阵的一行块，而每一个元素对应一个列块。例如 np.block([[A, I], [I, A]]) 会先拿第一行块中的 A 和 I 做水平拼接，再拿第二行块中的 I 和 A 做水平拼接，最后把两行块垂直堆叠。这个行为与数学上的分块矩阵记法几乎一一对应，这也是它适合实现超立方体邻接矩阵的原因。
使用 np.block 时最容易踩的坑是把嵌套列表写成展平列表。比如 np.block([A, I, I, A]) 并不会得到 2×2 分块，而会尝试把四个块水平拼成一行。由于在这个问题中 A 和 I 都是方阵且同阶，展平拼出来的形状会是 2^{n-1} 行、4 × 2^{n-1} 列，显然不是邻接矩阵。另一个常见问题是 dtype 被悄悄改变。默认 np.eye 返回浮点数组，如果 A_{n-1} 是整型，np.block 的结果可能被提升为浮点。邻接矩阵通常只包含 0 和 1，用整型存储可以减少内存并保持后续索引、位运算等操作的直观性。
还有一类错误出现在递归实现时没有保持单位矩阵的阶数。每一层递归的单位矩阵必须与 A_{n-1} 同阶，也就是 2^{n-1}。如果写成固定大小 I_2，在 n=3 时四个块尺寸不一致，np.block 会抛出形状不匹配错误。正确做法是使用 prev.shape[0] 动态生成单位矩阵。
下面给出正确和错误写法的对比：
# 正确：嵌套列表表达 2×2 分块 A = np.block([[prev, eye], [eye, prev]]) # 错误：展平列表会拼接成一行四块 # wrong = np.block([prev, eye, eye, prev])
完整实现与形状验证
把前面的递归结构翻译成 Python 函数并不复杂。递归基返回一个 1×1 的零矩阵，每一层递归先用上一层的邻接矩阵生成对应阶数的单位矩阵，再交给 np.block 完成拼接。代码如下：
import numpy as np
def hypercube_adj(n):
if n < 0:
raise ValueError('n must be non-negative')
if n == 0:
return np.array([[0]], dtype=int)
prev = hypercube_adj(n - 1)
eye = np.eye(prev.shape[0], dtype=int)
return np.block([[prev, eye], [eye, prev]])
实现完成后，应当验证矩阵的几个基本性质。超立方体 Q_n 的邻接矩阵必须是对称的，对角线必须全为零，每一行的和应等于 n，因为每个顶点在 n 个二进制位上各有一条边。下面的循环同时检查形状、对称性、零对角线和行和：
for n in range(1, 6):
A = hypercube_adj(n)
size = 1 << n
assert A.shape == (size, size)
assert np.array_equal(A, A.T)
assert np.all(np.diag(A) == 0)
assert np.all(A.sum(axis=1) == n)
print(f'n={n}, shape={A.shape}, edge_count={A.sum() // 2}')
运行后可以看到，n=1 时得到两个顶点的单边，n=2 时得到正方形的四条边，n=3 时得到立方体的十二条边。随着 n 增大，顶点数和边数按指数增长，但因为邻接矩阵是稠密存储，内存占用为 4^n 个元素。n=10 时矩阵为 1024×1024，约 800 万个元素，使用 int64 大约需要 8MB；n=12 时约为 128MB；再往上就很容易超过普通机器内存。因此 n 较大时，应当考虑稀疏矩阵或边列表表示。
递归构造本身也会产生额外的临时数组。每一层返回时都会创建一个新矩阵，同时保留上一层的矩阵。对于不是特别大的 n，这种开销可以接受；但如果在循环中反复构建多个 n 值，可以显式释放中间变量，或者使用迭代方式逐层扩增，以减少峰值内存。
与 np.kron 方案和稀疏方案的取舍
除了 np.block，另一种常见做法是利用笛卡尔积图的 Kronecker 积公式。超立方体 Q_n 是两个图的笛卡尔积：Q_n = Q_{n-1} □ K_2。对应邻接矩阵可以写成 A_n = A_{n-1} ⊗ I_2 + I_{2^{n-1}} ⊗ A_1，其中 A_1 是 Q_1 的邻接矩阵。用 NumPy 可以这样实现：
def hypercube_kron(n):
if n < 0:
raise ValueError('n must be non-negative')
if n == 0:
return np.array([[0]], dtype=int)
I2 = np.eye(2, dtype=int)
A1 = np.array([[0, 1], [1, 0]], dtype=int)
prev = hypercube_kron(n - 1)
return np.kron(prev, I2) + np.kron(np.eye(2 ** (n - 1), dtype=int), A1)
np.block 和 np.kron 最终都能得到正确的邻接矩阵，但二者的表达重点不同。np.block 直接对应顶点按最后一位分组的排列方式，分块结构清晰，调试时更容易看出矩阵块顺序是否正确。np.kron 则更贴近图论中的笛卡尔积表示，适合需要推广到其他积图或使用矩阵运算推导性质时使用。
从性能上看，两个方案在中小规模下差距不大，因为它们都需要分配新矩阵并复制数据。不过 np.kron 实现中先计算两个 Kronecker 积再相加，理论上会多出两个较大的临时矩阵，峰值内存更高一些。对于 n=12 这种中等规模，这种差异可能变得明显。实际工程中，如果只需要做图遍历、连通性分析或稀疏特征计算，使用 scipy.sparse 的块矩阵构造会更合适。例如用稀疏单位矩阵和稀疏邻接矩阵递归拼接，可以避免稠密矩阵的 4^n 存储压力，但这是另一个话题。
总结来说，如果目标是教学演示、小规模谱分析或快速验证图论性质，用 np.block 递归构造超立方体邻接矩阵是最容易理解和维护的方式。只要把握住嵌套列表结构、单位矩阵阶数和 dtype 三个要点，就能得到完全正确的结果。