📚 课程目录第2章图论基础与MaxCut形式化

2. 图论基础与MaxCut形式化

要理解量子算法为什么会被用来求解 MaxCut，先要把“图上的割”这件事说清楚。MaxCut 的问题对象是一张无向图 G=(V,E)，其中 V 是顶点集合，E 是边集合，每条边 {u,v} 没有方向，但可以带一个权重 w_uv。所谓“割”，就是把顶点集合 V 划分成两个互不相交的子集 S 与 V\S，所有一个端点在 S、另一个端点在 V\S 的边称为割边。MaxCut 的目标，就是寻找一种划分，使割边的权重之和最大。

这里有一个容易混淆的细节：割的对象是顶点，被切开的是边。初学者常把“割边”理解成删掉边，其实边并没有被删除，只是被划分“跨过”了。为了后续与量子模型对接，通常给每个顶点分配一个自旋变量 x_i ∈ {+1, −1}，+1 表示属于 S，−1 表示属于另一侧。于是边 {i,j} 成为割边，当且仅当 x_i ≠ x_j，也就是 x_ix_j = −1。据此可以写出 MaxCut 的目标函数：

最大化  C(x) = Σ_{(i,j)∈E} w_ij · (1 − x_i x_j) / 2
约束    x_i ∈ {+1, −1},  i = 1, 2, …, n

式中的 (1 − x_ix_j)/2 是一个“指示器”：两端同侧时取 0，异侧时取 1，正好把“是否割开”翻译成数值。这个形式非常关键，因为它把组合问题变成了一个关于 ±1 变量的二次函数求和，而这正是量子近似优化算法（QAOA）构造代价哈密顿量的出发点。若把最大化改写成最小化，只需取负号，得到等价的最小化形式 −C(x)，这也是后续变分线路中常见的写法。

下面这张图把一张 5 顶点带权图的割结构、变量取值与目标函数贡献放在一起对照，帮助建立“划分—割边—数值”的对应关系。

从计算角度看，MaxCut 的困难来自“组合爆炸”。n 个顶点每个有两种归属，共有 2ⁿ 种划分，但把 S 与 V\S 互换得到的是同一个割，因此本质不同的划分有 2ⁿ⁻¹ 种。n=10 时约 512 种，n=30 时已超过 5 亿种，n=100 时则远超可枚举范围。更严格地说，MaxCut 是NP 难问题：判定“是否存在割值不小于 K 的划分”属于 NP 完全问题，而一般图上的精确求解目前没有已知的多项式时间算法。这意味着随着规模增长，精确算法的最坏情况耗时呈指数上升，工程上必须转向近似或启发式方法。

面对 NP 难，实践中通常有三条路线。其一是精确算法，如分支定界、整数规划，适合中小规模或结构特殊的图，能给出最优性证明，但规模一大就难以承受。其二是近似与启发式，例如经典的 0.878 近似算法（基于半正定规划）、贪心局部搜索、模拟退火等，它们不保证最优，但能在可接受时间内给出较优解。其三是量子与量子—经典混合方法，如 QAOA，用参数化量子线路制备候选划分的叠加态，再由经典优化器调整参数，这正是本课程后续要展开的内容。需要强调的是，量子方法目前并不“解决”了 NP 难，它提供的是在特定硬件与规模下探索高质量解的另一条路径。

在动手实现前，建议先建立一套可复用的形式化流程，把图数据、变量编码和目标函数对齐，避免后续量子线路与经典评估口径不一致。下面给出一个可直接套用的建模清单，以 Python 字典描述图为例：

# 示例：5 顶点带权无向图（权重为教学假设值）
edges = [
    (0, 1, 3), (1, 2, 2), (0, 2, 1),
    (2, 3, 4), (3, 4, 2), (1, 4, 1)
]

def cut_value(bits, edges):
    # bits[i] ∈ {0,1}，0/1 代表两侧；异侧即割边
    total = 0
    for u, v, w in edges:
        if bits[u] != bits[v]:
            total += w
    return total

# 示例划分：顶点 0,1,4 为一侧，2,3 为另一侧
bits = [0, 0, 1, 1, 0]
print(cut_value(bits, edges))   # 输出 9

这段代码刻意用 0/1 编码，而目标函数公式用 ±1 编码，两者是等价的：令 x_i = 1 − 2·bits_i，即可互相转换。实际工程中务必统一口径，否则在把经典解映射到量子测量结果时会出现“割值算反”的低级错误。判断一个候选解好坏时，除了看割值绝对值，还应关注它与总权重之比、与已知上界（如半正定规划松弛解）的差距，以及多次运行之间的稳定性。

建模自检三问：变量是否覆盖全部顶点？每条边是否只计一次？目标函数方向（最大化还是最小化）是否与后续优化器一致？这三点确认无误，再进入量子线路设计。

最后要区分两个常被混用的概念：割的大小指割边数量，割的权重指割边权重之和。无权图里二者一致，带权图里则不同。本课程默认讨论带权形式，无权情形可视为所有 w_ij=1 的特例。把图、割、目标函数与复杂度这四件事串起来，就构成了 MaxCut 的完整形式化基础，也是理解后续量子近似优化为何这样设计代价算符的前提。