循环图香农容量计算：从独立集、强积到传递算子

1. 项目概述：从图论到信息论的交叉探索

最近在整理一些关于图论在信息论中应用的旧笔记，发现“循环图的强幂独立集计数及其香农容量分析”这个课题，虽然听起来非常理论化，但背后串联起的思路却异常精妙，它完美地展示了如何用一个纯粹的数学结构（图）去刻画并解决一个通信领域的核心限制问题（信道容量）。简单来说，我们想搞清楚：在一个特定的通信场景（用循环图建模）下，当允许信号“叠加”或“组合”发送时（即考虑图的强幂），这个信道理论上最多能无错误地传输多少信息？这个理论极限就是香农容量。

这个问题的核心在于“独立集”。在图论中，独立集是一组互不相邻的顶点集合，放在通信语境下，就代表一组可以同时发送而不会相互干扰的信号。图的“强积”（Strong Product）是一种运算，它能够构建一个描述“允许信号在多个时间槽或维度上组合发送”的扩展图模型。而“传递算子”则是我们分析这个扩展图独立集数量的一个强大代数工具，它帮助我们将复杂的组合计数问题，转化为相对更容易处理的线性代数特征值问题。

如果你对图论、编码理论或者信息论的基础概念有些了解，并且好奇于这些抽象理论如何通过严谨的数学工具落地，计算出那个令人着迷的“容量”数字，那么这次分享或许能给你带来一些启发。整个过程就像是在解一个多层嵌套的谜题：先定义好通信的约束（图），然后构建允许的扩展操作（强积），接着寻找不冲突的信号组合（独立集），最后用代数方法（传递算子）去逼近那个理论的极限（香农容量）。接下来，我们就一步步拆解这个谜题。

2. 核心概念与问题建模

要理解整个分析流程，我们首先需要统一几个关键概念的“语言”。这些概念分别来自图论、组合数学和信息论，将它们准确对应起来是后续所有计算的基础。

2.1 循环图：通信约束的数学模型

循环图 (C_n^k) 是我们整个分析的起点。它由 (n) 个顶点组成，这些顶点可以想象成摆放在一个圆圈上的 (n) 个点。每个顶点与和它距离不超过 (k) 的顶点相连（但排除自身），这里的“距离”是指在圆环上沿着较短弧的方向经过的边数。例如，(C_5^1) 就是一个五边形，每个点只与左右两个邻居相连；而 (C_5^2) 则是一个五顶点的完全图（除了自身不相连），因为每个点与所有其他点距离都小于等于2。

在信息论背景下，循环图完美地建模了一种称为“有干扰信道”的场景。顶点代表可能发送的信号或符号。如果两个顶点之间有边相连，就意味着这两个信号不能同时被使用，否则会在接收端产生混淆或干扰。参数 (k) 直观地表示了干扰的范围。这种模型可以抽象许多实际场景，比如某些频段相近的无线电信号会相互干扰（(k) 表示频带间隔），或者某些在时间上过于接近的脉冲会相互叠加（(k) 表示时间保护间隔）。

2.2 独立集与强积：从单次传输到序列传输

独立集是图 (G) 的一个顶点子集，其中任意两个顶点都不相邻。独立集的大小（包含的顶点数）记为 (\alpha(G))，称为图的独立数。在我们的通信模型中，一个独立集就对应着一组可以“同时”安全发送的信号集合。

然而，香农容量考虑的是渐近的、在多个信道使用后的最大信息率。这就引出了图的积运算。其中，强积（记作 (G \boxtimes H)）是定义两个图 (G) 和 (H) 之间的一种运算。新图的顶点集是 (G) 和 (H) 顶点集的笛卡尔积。对于两个顶点 ((u_1, v_1)) 和 ((u_2, v_2))，它们在强积中有边相连，当且仅当满足以下条件之一：

1. (u_1 = u_2) 且 (v_1) 与 (v_2) 在 (H) 中有边相连；或者
2. (v_1 = v_2) 且 (u_1) 与 (u_2) 在 (G) 中有边相连；或者
3. (u_1) 与 (u_2) 在 (G) 中有边相连，并且(v_1) 与 (v_2) 在 (H) 中有边相连。

强积的 (m) 次幂 (G^{\boxtimes m}) 就代表了允许信号在 (m) 个时间槽（或 (m) 个维度）上组合发送的扩展信道模型。此时，一个顶点是一个长度为 (m) 的信号序列。边的定义确保了：只要在任何一个维度上，两个序列对应的信号是冲突的（在原图中有边），那么这两个序列整体就是冲突的，不能同时使用。这比另一种常见的积运算——笛卡尔积（要求所有维度都冲突才相连）——约束更严格，更能反映某些实际干扰模型。

那么，(m) 个信道使用后，最多能区分的信号序列数，就是强 (m) 次幂图的独立数 (\alpha(G^{\boxtimes m}))。

2.3 香农容量：理论极限的数学定义

香农容量 (\Theta(G)) 正是对这个渐近性能的度量。它的定义是： [ \Theta(G) = \sup_{m \geq 1} \sqrt[m]{\alpha(G^{\boxtimes m})} ] 这个定义直观上可以这样理解：(\alpha(G^{\boxtimes m})) 是使用 (m) 次信道后能无错误区分的消息数量（假设每条消息对应一个独立的信号序列）。那么每次信道使用能区分的消息数就是 (\alpha(G^{\boxtimes m})^{1/m})。香农容量就是当 (m) 趋向于无穷大时，这个值的上确界。它代表了在允许无限复杂的编码方案下，每个信道使用所能传输的最大比特数的理论上限（因为比特数等于 (\log_2(\Theta(G)))）。

计算 (\Theta(G)) 的难点在于，(\alpha(G^{\boxtimes m})) 通常随着 (m) 增长极其复杂，没有简单的闭式表达式，而且强积运算不保持图的许多易处理性质。因此，我们需要借助更强大的工具——传递算子。

2.4 传递算子：连接组合与代数的桥梁

传递算子（也称为图的“同态密度矩阵”或“分数独立数规划”的算子形式）是 Lovász 在开创性工作中引入的，用于研究香农容量的工具。对于一个图 (G)，其传递算子 (T_G) 是一个作用在某个向量空间上的线性算子。它的一个关键性质是：其算子范数 (|T_G|) 给出了香农容量的一个上界，即 (\Theta(G) \leq |T_G|)。更妙的是，对于许多图，特别是像循环图这样的顶点传递图，这个上界是紧的，也就是说 (\Theta(G) = |T_G|)。

传递算子的具体构造与图的邻接矩阵 (A_G) 密切相关。对于循环图 (C_n^k)，由于其高度的对称性（循环对称性），其邻接矩阵是一个循环矩阵。这种对称性意味着它的传递算子可以在傅里叶基（或者说，在由复数单位根张成的空间上）下被对角化。这使得计算其算子范数 (|T_{C_n^k}|) 转化为一个相对容易处理的特征值问题。本质上，传递算子将寻找最大独立集这个组合优化问题，“松弛”为了一个线性代数中的特征值问题，从而为我们打开了一扇计算香农容量的窗口。

3. 循环图强幂独立集的计数策略

直接计算 (\alpha(G^{\boxtimes m})) 对于稍大的 (m) 和 (n) 来说是不现实的，因为状态空间呈指数级增长。因此，我们的策略不是蛮力枚举，而是利用循环图的代数结构，通过传递算子来分析和逼近这个数量。

3.1 利用对称性进行问题约简

循环图 (C_n^k) 具有循环对称群 (C_n) 的作用。这意味着如果我们旋转图中的所有顶点，图的整体结构保持不变。这种对称性会传递到它的强幂 (C_n^{\boxtimes m}) 上。强幂图继承了底图对称性的直积形式，其对称群是 (m) 个 (C_n) 循环群的直积 ((C_n)^m)。

这个对称性有一个极其重要的推论：在寻找最大独立集时，我们可以利用对称性将问题简化。通常，存在一个最大独立集，其本身在对称群作用下是“一致的”或具有某种规则结构。更具体地说，我们可以将独立集的计数问题与群在顶点集上的轨道联系起来。通过分析群作用下的轨道结构，我们可以将原本在 (n^m) 个顶点上的搜索问题，约简到对少数几个“代表型”配置的分析上。这通常涉及到将序列 ((v_1, v_2, ..., v_m)) 映射到其关于群作用的等价类，并分析在等价类中如何选择顶点才能满足独立集的条件。

3.2 独立集计数与传递算子的关联

Lovász 的经典结论指出，图的香农容量 (\Theta(G)) 等于其Lovász ϑ 函数。而 ϑ 函数可以通过半定规划（SDP）来计算。对于顶点传递图（如循环图），ϑ 函数有一个更简洁的表达式： [ \vartheta(G) = \min_{\lambda, d} \lambda ] 其中 (d) 是一个在图的顶点集上定义的某个正定矩阵，满足一些与图结构相关的约束。这个优化问题的对偶形式恰好与传递算子的范数相关联。

传递算子 (T_G) 可以视为此 SDP 对偶问题中一个可行解对应的算子。计算 (|T_G|) 等价于求解一个特征值最大化问题。对于循环图，由于其邻接矩阵是循环矩阵，它在离散傅里叶变换基下是对角化的。因此，(T_{C_n^k}) 在这个基下也是一个对角算子，其对角元由原图邻接矩阵的特征值通过一个特定的函数关系给出。这个函数关系确保了 (T_G) 保持了图“独立”的性质：如果两个顶点在原图中不相邻，那么 (T_G) 对应的矩阵块满足某种正交性条件。

这样一来，计算 (|T_{C_n^k}|) 就转化为在单位圆上寻找一组复数单位根 ({e^{2\pi i j / n}})，使得由这些单位根通过某个多项式构造出的矩阵的谱半径最大。这个多项式正是由图的干扰规则（参数 (k)）决定的。

3.3 从单次幂到强幂的推广

我们最终的目标是 (\alpha(C_n^{\boxtimes m})) 或至少是它的渐近增长率。传递算子理论的一个强大之处在于它的“乘积性质”。对于强积，有近似的关系（在范数意义下）： [ |T_{G \boxtimes H}| \approx |T_G| \cdot |T_H| ] 更严格地说，Lovász ϑ 函数对强积是乘性的：(\vartheta(G \boxtimes H) = \vartheta(G) \cdot \vartheta(H))。由于对于循环图，我们有 (\Theta(C_n^k) = \vartheta(C_n^k))，因此： [ \Theta(C_n^k) = \vartheta(C_n^k) = |T_{C_n^k}| ] 并且， [ \Theta(C_n^{\boxtimes m}) = [\Theta(C_n^k)]^m = [|T_{C_n^k}|]^m ] 这意味着，虽然精确计算 (\alpha(C_n^{\boxtimes m})) 很难，但它的 (m) 次方根的增长极限，完全由传递算子的一次幂范数所决定。我们的工作重心就从计算复杂的组合数，转移到了计算一个线性算子的范数上，后者对于循环图而言是一个可解的解析问题。

4. 传递算子的具体构造与范数计算

现在，我们进入核心的计算环节：如何为循环图 (C_n^k) 构造传递算子 (T)，并计算其算子范数 (|T|)。

4.1 循环图的邻接矩阵与特征值

设顶点集为 (V = {0, 1, ..., n-1})，模 (n) 加法。邻接矩阵 (A) 是一个 (n \times n) 的循环矩阵，其第一行为： [ [0, \underbrace{1, 1, ..., 1}{k\text{个}}, 0, ..., 0, \underbrace{1, 1, ..., 1}{k\text{个}}] ] 具体地，(A_{0,j} = 1) 当且仅当 (1 \le \min(j, n-j) \le k)。由于 (A) 是循环矩阵，它的特征向量是傅里叶向量 (f_\ell)，其中 (f_\ell(j) = \omega^{j\ell})， (\omega = e^{2\pi i / n})， (\ell = 0, 1, ..., n-1)。对应的特征值为： [ \lambda_\ell = \sum_{d=1}^{k} (\omega^{\ell d} + \omega^{-\ell d}) = 2 \sum_{d=1}^{k} \cos\left(\frac{2\pi \ell d}{n}\right) ] 这些特征值都是实数，并且关于 (\ell) 对称：(\lambda_\ell = \lambda_{n-\ell})。

4.2 传递算子的定义与矩阵表示

Lovász 在定义 ϑ 函数时，引入了一个与图补图 (\overline{G}) 相关的正交表示概念。对于我们的计算，一个等价的、更易于操作的传递算子定义如下： 考虑所有满足以下条件的 (n \times n) 复矩阵 (M) 的集合：

1. (M) 是半正定矩阵（(M \succeq 0)）。
2. 对于图 (G) 上的每条边 ((i, j))，有 (M_{ij} = 0)。
3. (M_{ii} = 1) 对所有顶点 (i) 成立。

那么，(\vartheta(G) = \max_{M} \sum_{i,j} M_{ij})，其中 (M) 遍历上述集合。这个优化问题的解 (M^*) 具有某种极值性质。

对于循环图 (C_n^k)，由于其顶点传递性，最优解 (M^*) 也必然是循环矩阵。一个循环矩阵完全由它的第一行决定。设第一行为 ((t_0, t_1, ..., t_{n-1}))，其中 (t_0 = 1)（对应条件3），并且对于所有满足 (1 \le \min(j, n-j) \le k) 的 (j)，有 (t_j = 0)（对应条件2，边相连的位置矩阵元为零）。

那么，这个循环矩阵 (M) 在傅里叶基下是对角化的，其第 (\ell) 个特征值为： [ \mu_\ell = \sum_{j=0}^{n-1} t_j \omega^{-j\ell} = 1 + \sum_{j \in S} t_j \omega^{-j\ell} ] 其中 (S) 是那些不与顶点0相邻的顶点索引集合（即距离 (j) 满足 (k < j < n-k) 的 (j)）。

条件1要求 (M) 半正定，即所有特征值 (\mu_\ell \ge 0)。我们的目标是最大化 (\sum_{i,j} M_{ij} = n \cdot \sum_{j} t_j = n \cdot t_0 + n \cdot \sum_{j \in S} t_j)。由于 (t_0=1) 固定，这等价于最大化 (\sum_{j \in S} t_j)。

4.3 优化问题转化为特征值约束

现在问题变成了：在约束 (\mu_\ell = 1 + \sum_{j \in S} t_j \omega^{-j\ell} \ge 0) 对所有 (\ell) 成立的前提下，最大化 (\sum_{j \in S} t_j)。变量是 (t_j (j \in S))。

这是一个线性规划问题，但其约束是无限维的（对所有 (\ell)）。通过离散傅里叶变换的对偶性，可以证明，这个最大值等于以下优化问题的最小值： [ \vartheta(C_n^k) = \min_{\lambda} \lambda ] 其中 (\lambda) 是一个实数，并且存在一组实数系数 (a_j (j \in S))，使得多项式 [ P(x) = \lambda - 1 - \sum_{j \in S} a_j (x^j + x^{-j}) ] 在单位圆 (|x|=1) 上非负，即 (P(e^{i\theta}) \ge 0) 对所有 (\theta) 成立。

这个对偶问题的解 (\lambda^*) 就是 (\vartheta(C_n^k))，也就是我们要求的 (|T|)。这里的多项式 (P(e^{i\theta})) 可以理解为传递算子在频率域上的表示。寻找最优的 (\lambda) 和系数 (a_j)，是一个三角多项式非负优化问题，可以通过半定规划（SDP）或利用特定结构（如循环图的对称性）来求解。

4.4 特定参数下的解析解与数值计算

对于某些特定的 ((n, k))，我们可以得到解析解。例如：

• 当 (k=1)（即循环图是简单环）：已知 (\Theta(C_n) = \vartheta(C_n) = \frac{n \cos(\pi/n)}{1+\cos(\pi/n)})。对于大的 (n)，这近似于 (n/2)。
• 当 (k \ge \lfloor n/2 \rfloor)：此时图几乎是完全图，独立数 (\alpha=1)，显然 (\Theta=1)。
• 对于较小的 (n) 和 (k)：可以通过求解上述 SDP 精确得到 (\vartheta) 值。例如，利用 Python 的cvxpy或SDPA工具包可以方便地计算。

在实际操作中，我通常采用以下步骤进行数值计算：

1. 定义问题变量：设定变量 (\lambda) 和向量 (a)（维度为 (|S|)）。
2. 构造多项式：对于离散化的角度采样点 (\theta_t = 2\pi t / T, t=0,...,T-1)（(T) 足够大，如 (T=512)），计算 (P(e^{i\theta_t}) = \lambda - 1 - \sum_{j \in S} a_j \cdot 2\cos(j\theta_t))。
3. 建立约束：要求对于所有 (t)，有 (P(e^{i\theta_t}) \ge 0)。这是一个线性不等式约束。
4. 设定目标与求解：目标函数是最小化 (\lambda)，然后调用凸优化求解器求解这个线性规划问题。

注意：由于 (P(e^{i\theta})) 是实值的，约束 (P \ge 0) 是实的。虽然我们是在复数单位圆上定义多项式，但利用欧拉公式和系数 (a_j) 为实数的对称性，可以将其完全转化为实变量的线性约束，这大大简化了计算。

通过求解这个优化问题，我们就能得到 (|T_{C_n^k}| = \vartheta(C_n^k) = \Theta(C_n^k))。这个数值就是循环图 (C_n^k) 的香农容量。

5. 香农容量结果分析与应用启示

得到 (\Theta(C_n^k)) 的数值或解析表达式后，我们需要解读其含义，并理解它在信息论和编码理论中的价值。

5.1 容量结果解读与渐近行为

计算出的 (\Theta(C_n^k)) 是一个介于 1 和 (n) 之间的实数。它代表了每个信道使用所能传输的最大信息量（以可区分信号数的对数量度）。例如，如果 (\Theta = 3.5)，那么 (\log_2(3.5) \approx 1.807) 比特就是每符号的容量上限。

分析 (\Theta) 随着 (n) 和 (k) 的变化趋势很有意义：

• 固定 (k)，增大 (n)：当 (n) 远大于 (k) 时，干扰是局部的。可以预期 (\Theta(C_n^k) \sim n / (2k+1))。这是因为在环上，大约每 (2k+1) 个连续的顶点中，最多只能选一个进入独立集（考虑最密集的 packing）。传递算子的计算通常会给出一个略优于这个简单 packing 上界的值，因为它考虑了非整数（分数）包装的可能性，这正是香农容量可能大于独立数 (\alpha) 的原因。
• 固定 (n)，增大 (k)：随着 (k) 增加，干扰变强，容量 (\Theta) 单调递减。当 (k \ge \lfloor n/2 \rfloor) 时，图变为完全图（除自环），(\Theta=1)，意味着所有信号都两两冲突，每次只能发送一种信号。
• 分数独立数的体现：香农容量 (\Theta) 可能严格大于独立数 (\alpha) 的 (m) 次方根。例如，对于著名的 5-环 (C_5)，(\alpha(C_5)=2)，但 (\Theta(C_5)=\sqrt{5})。这是因为通过使用长的信号序列进行编码，可以达到比简单重复使用独立集更高的效率。传递算子/ϑ 函数捕捉的正是这种“分数”包装的能力。

5.2 在编码理论中的应用含义

香农容量 (\Theta(G)) 不仅是一个理论极限，也对实际编码设计有指导意义：

1. 性能基准：任何针对该干扰信道模型的编码方案，其码率（每符号传输的比特数）的上限是 (\log_2 \Theta(G))。这为评估编码方案的优劣提供了一个绝对标尺。
2. 结构化编码启发：分析达到容量极限的传递算子解 (M^) 或对偶多项式 (P^)，有时能启发我们构造接近容量的编码。例如，(M^*) 的特征向量可能暗示了最优信号集合在傅里叶域（频域）上的能量分布。
3. 多用户信道建模：循环图模型可以推广到多用户干扰信道。每个顶点代表一个用户的发射符号组合，边表示不可区分的组合。此时，强积的香农容量描述了在允许时间共享和复杂编码下，多用户系统的容量区域边界。

5.3 与其他图参数的关系与比较

理解香农容量与其他图论参数的关系，有助于我们从不同角度把握图的“信息承载能力”：

• 独立数 (\alpha(G))：这是单次使用的容量，显然 (\alpha(G) \le \Theta(G))。
• 分数独立数 (\alpha^*(G))：定义为线性规划松弛的独立数，满足 (\alpha(G) \le \alpha^(G) \le \vartheta(G))。对于循环图，(\alpha^(C_n^k)) 通常有简单的闭式解（如 packing 界），而 (\vartheta) 可能更紧。
• Lovász ϑ 函数 (\vartheta(G))：我们已经知道 (\Theta(G) \le \vartheta(G))，且对于许多图（包括循环图），等号成立。ϑ 函数是可乘的（对强积），且可用 SDP 高效计算，这使其成为研究香农容量的核心工具。
• 图熵：香农容量也与 Körner 定义的图熵有关。图熵给出了在已知部分顶点信息条件下，区分顶点所需的最小比特率，与 (\Theta(G)) 存在对偶关系。

在实际研究中，我常常同时计算这几个参数。对于循环图 (C_n^k)，比较 (\alpha, \alpha^*, \vartheta) 的值，可以直观看出“分数”包装和“序列”编码带来的增益究竟有多大。例如，对于较小的 (n) 和 (k)，可以制作一个对比表格：

实操心得：在计算 ϑ 函数时，利用循环图的对称性至关重要。直接对 n 个变量进行 SDP 求解，当 n 较大时计算量很大。但如果我们预先知道最优解 (M^*) 是循环矩阵，就可以将变量减少到只有第一行的非零元（即集合 S 的大小），这通常只有 O(n) 个变量，并且约束可以转换到傅里叶域，用快速傅里叶变换（FFT）高效计算多项式 (P(e^{i\theta})) 在所有采样点的值，从而将问题规模从 O(n²) 降到 O(n log n)。这是处理对称图问题时一个非常有效的优化技巧。

6. 常见问题与计算实践要点

在实际计算和分析过程中，会遇到一些典型的疑问和挑战。这里我结合自己的经验，总结几个常见问题和处理技巧。

6.1 如何验证传递算子计算结果的正确性？

对于香农容量或 ϑ 函数的计算，交叉验证是关键。可以采用以下方法：

1. 与已知结果对比：对于小图（如 (C_5, C_7, C_9) 等），有文献中记录的结果。确保你的数值解与已知解析解或高精度数值解匹配。
2. 上下界检验：
   • 下界：构造一个具体的编码方案。例如，找到一个较大的独立集 (I_m) in (G^{\boxtimes m})，那么 (\sqrt[m]{|I_m|}) 就是 (\Theta(G)) 的一个下界。你的计算结果应大于等于这个下界。
   • 上界：除了 ϑ 函数，还有其他上界，如“Schrijver's ϑ' function”或“Hoffman bound”。你的结果应小于等于这些上界。如果可能，用多种方法计算上界进行交叉验证。
3. SDP 求解器的可靠性：使用成熟的凸优化求解器（如 MOSEK, SDPA, CVXOPT）。检查求解器返回的状态（status），确保是“最优解”（Optimal），并关注对偶间隙（duality gap）是否足够小（如小于 (10^{-8})）。对于循环图问题，由于结构良好，通常能得到高精度的解。

6.2 当 n 较大时，计算遇到数值困难怎么办？

随着 (n) 增大，SDP 问题的规模（变量数和约束数）线性增长，但计算多项式 (P(e^{i\theta})) 的约束点数量 (T) 也需要相应增加以保证精度，这可能导致计算变慢。

• 利用对称性降维：如前所述，强制解为循环矩阵，将变量从 (n^2) 级降到 (n) 级。
• 稀疏采样与自适应细化：不必一开始就用很大的 (T)。可以先在较稀疏的网格（如 (T=64)）上求解，得到粗略解。然后在粗略解中 (P(e^{i\theta})) 接近零的区域（这些通常是活跃约束），进行网格细化，增加采样点，再次求解。这种自适应方法能有效平衡精度和效率。
• 使用频域解析形式：对于循环图，约束 (P(e^{i\theta}) \ge 0) 可以等价地转化为要求某个托普利茨（Toeplitz）矩阵是半正定的。这是一个有限维的 SDP 约束（通过三角多项式的非负性与半定矩阵的等价关系），其规模与多项式次数有关，而与采样点 (T) 无关。这通常是更稳定和高效的方法，但需要用到更专业的优化库或自定义实现。

6.3 强积与笛卡尔积、张量积的区别与选择

在图论中，除了强积（(\boxtimes)），还有两种常见的积：

• 笛卡尔积（(\square)）：((u_1, v_1)) 与 ((u_2, v_2)) 相邻当且仅当 (u_1=u_2) 且 (v_1 \sim v_2)，或(v_1=v_2) 且 (u_1 \sim u_2)。
• 张量积（(\times)）：((u_1, v_1)) 与 ((u_2, v_2)) 相邻当且仅当 (u_1 \sim u_2)且(v_1 \sim v_2)。

它们建模了不同的信道扩展语义：

• 强积：最严格的干扰模型。只要任一维度发生冲突，整体就冲突。这对应于信号在多个维度（如时间、频率）上传输，且任一维度的干扰都会破坏整个信号。这是香农原始定义中使用的积，也是最常见的选择。
• 笛卡尔积：干扰模型较宽松。要求冲突发生在同一个维度，且其他维度完全相同。这可以建模为多个并行、独立信道的组合。
• 张量积：最宽松的干扰模型。要求所有维度同时发生冲突。这在某些特定的组合场景中出现，但与典型信道模型关联较弱。

选择建议：在信息论背景下，除非有特别明确的物理含义指向其他积运算，否则默认使用强积来定义香农容量。这是学术界的标准做法。在阅读文献或对比结果时，务必首先确认对方使用的是哪种图积。

6.4 从理论容量到实际编码的鸿沟

计算出 (\Theta(G)) 后，一个自然的问题是：如何构造一个码率达到 (\log_2 \Theta(G)) 的实用编码？这是一个难题。

• 存在性证明非构造性：香农容量是一个渐近极限，其证明（以及 ϑ 函数的可达性证明）通常是非构造性的，使用了随机编码和典型序列等概率方法。它证明了这样的好码存在，但没有给出具体构造。
• 结构化编码设计：实际中，我们致力于设计具有明确代数或组合结构的、可编解码的码，使其码率接近容量。例如，对于循环图，可以尝试基于群论、拉丁方或低密度奇偶校验（LDPC）码思想的构造。分析传递算子的最优解 (M^*) 有时能提供线索，比如最优解在傅里叶域的能量集中特性可能提示使用某些频率分量作为码字基底。
• 有限块长性能：香农容量是 (m \to \infty) 的极限。对于有限的 (m)，最大码本大小 (\alpha(G^{\boxtimes m})) 可能远低于 ([\Theta(G)]^m)。研究 (\alpha(G^{\boxtimes m})) 对于较小 (m) 的精确值或上下界，对于中短码长的编码设计更有直接指导意义。这通常需要更复杂的组合搜索或整数规划方法。

这个领域最吸引人的地方，恰恰在于理论极限（香农容量）与实际实现（结构化编码）之间的张力。传递算子为我们计算极限提供了一个强有力的工具，而如何跨越鸿沟，设计出逼近这一极限的实用方案，则是留给编码理论学家和工程师们的持久挑战。每一次对特定图模型（如循环图）容量的精确计算，都是向理解这一挑战迈出的坚实一步。