之前不少读者看到 DNF 三个字母第一反应是游戏《地下城与勇士》。但在这篇文章里DNF 是理论计算机科学中的 Disjunctive Normal Form也就是析取范式。更准确地说我们讨论的是无歧义析取范式的最优表示问题以及一个和它有着微妙联系、名字看起来像“两个不相关话题强行拼在一起”的图论猜想Alon-Saks-Seymour 猜想。这两条线交叉起来恰恰是布尔函数复杂度与图结构之间的经典故事边集的覆盖、划分对应 DNF 中项的结构图的色数又和布尔函数的某些复杂度下界有关。本文将用尽量通俗的方式把这些概念串起来并给出可直接运行的小规模 Python 验证实验。无论你是对组合数学感兴趣的研究生还是想补一补理论功底的工程师都可以跟着这篇文章走一遍。1. 背景DNF 撞名背后的两个世界1.1 析取范式不是游戏术语在布尔逻辑中一个布尔函数接受 n 个布尔变量输出 0 或 1。比如常见的“三个变量中至少两个为真”就是一个布尔函数。我们通常用两种标准形式来表示一个布尔函数CNF合取范式多个子句做“与”运算每个子句内部是“或”关系DNF析取范式多个合取项做“或”运算每个合取项内部是一组文字的“与”关系。一个“文字”是指变量本身或它的否定比如 x 和 ¬x。一个“合取项”是若干个文字的合取比如 x ∧ y ∧ ¬z。一个 DNF 就是若干合取项的析取f(x, y, z) (x ∧ y) ∨ (¬x ∧ z)这条式子的意思是当 x 和 y 都为真或者 x 为假且 z 为真时f 输出 1。在数字电路综合、SAT 求解、规则系统、决策列表等场景中DNF 都大量出现。它的优点是直观缺点是同一个函数可能有很多种不同大小的 DNF因此“最小 DNF”是一个很自然的优化问题。1.2 无歧义 DNF 是什么普通 DNF 允许一个赋值让多个合取项同时为真。比如g(x, y, z) (x ∧ y) ∨ (y ∧ z)当 x1、y1、z1 时两个合取项都为真这并不违反 DNF 的定义。但“无歧义 DNF”要求更严格对于任意让函数值为 1 的赋值有且只有一个合取项为真。也就是说各个合取项的满足集合两两不相交。这个约束看似苛刻却让 DNF 具备了某些好的结构性质。比如在概率近似正确学习、布尔函数复杂度下界、伪随机性与组合设计研究中无歧义 DNF 都经常作为一类特殊的表示模型出现。1.3 图论为什么会“乱入”很多人觉得图论和布尔公式是两门课但组合数学中有一类基本操作就是“用结构覆盖图”。把一张图的边集划分成若干完全二部图这在很大程度上等同于把一个布尔函数拆成若干合取项的并。理解这种对应关系是进入 Alon-Saks-Seymour 猜想的前提。某种意义上本文是在回答三个问题无歧义 DNF 的最优表示为什么困难图的 biclique 划分如何对应 DNF 的结构Alon-Saks-Seymour 猜想说了什么它为什么错得很有价值。2. 无歧义 DNF定义与判定方法2.1 形式化定义设有一个关于 n 个布尔变量 x1, x2, ..., xn 的布尔函数 f。一个合取项 T 可以写成T (∧_{i∈P} xi) ∧ (∧_{j∈N} ¬xj)其中 P 和 N 是不相交的变量下标集合分别表示 T 要求哪些变量为真、哪些变量为假。一个 DNF 是无歧义的如果对于任意赋值 a ∈ {0,1}^n满足 f(a)1 时恰好只有一个合取项在 a 上为真。两个合取项 T1 和 T2 互斥当且仅当存在某个变量 xkT1 要求 xk 为真而 T2 要求 xk 为假或者反过来。因为此时没有任何赋值能同时满足两个项。这个判定条件非常便宜只需检查项与项之间是否存在“正负冲突”。于是“判断一个 DNF 是否无歧义”可以在多项式时间内完成。2.2 一个可运行的小例子我们用 Python 实现上述判定规则。下面这一段只依赖 Python 标准库可以直接复制运行。def terms_conflict(t1, t2): 判断两个合取项是否互斥。 t1, t2 都是 dict 类型形如 {变量下标: True/False} True 表示该变量以正文字出现False 表示以负文字出现。 common set(t1.keys()) set(t2.keys()) for var in common: if t1[var] ! t2[var]: return True return False def is_unambiguous(dnf): 判断一个 DNF 是否无歧义。 dnf 是 list每个元素是一个 dict{变量下标: True/False}。 n len(dnf) for i in range(n): for j in range(i 1, n): if not terms_conflict(dnf[i], dnf[j]): return False, (i, j) return True, None # 示例 1f (x ∧ y) ∨ (¬x ∧ z) dnf1 [ {0: True, 1: True}, # x ∧ y {0: False, 2: True}, # ¬x ∧ z ] print(is_unambiguous(dnf1)) # (True, None) # 示例 2g (x ∧ y) ∨ (y ∧ z) dnf2 [ {0: True, 1: True}, # x ∧ y {1: True, 2: True}, # y ∧ z ] print(is_unambiguous(dnf2)) # (False, (0, 1))运行结果应该是(True, None) (False, (0, 1))第一个 DNF 无歧义因为第一个项要求 x 为真第二个项要求 x 为假二者必然互斥。第二个 DNF 有歧义因为当 x1、y1、z1 时两个项同时为真。2.3 最优无歧义 DNF 问题给定一个布尔函数的真值表我们希望找到项数最少或者文字总数最少的无歧义 DNF。这比普通最小 DNF 更复杂因为不仅要覆盖所有输出为 1 的赋值还要求覆盖用的“项”两两互斥。小规模时可以用暴力搜索先枚举所有可能的合取项再寻找一组两两互斥且覆盖整个真值表的项。枚举空间随 n 指数增长因此只适合 n≤4 或 n≤5 的情况。不过这种小规模搜索对建立直觉很有帮助。这个问题的价值在于无歧义 DNF 相当于把函数的 1 集合划分成若干个“立方体”立方体之间不能相交。它天然是一种不相交覆盖这与图的边划分问题在结构上完全一致。下面我们就进入图论那一侧。3. 为什么图论会出现在这里3.1 用 DNF 描述图的边集给定一个无向简单图 G(V,E)其中 V 是顶点集合E 是边集合。我们定义一个布尔函数 f_G对于顶点集合 S⊆V设它的指示向量为 x∈{0,1}^{|V|}当 S 诱导的子图中至少存在一条边时f_G(x)1。这个函数显然可以写成一个自然 DNF每条边 (u,v) 对应一个合取项 xu ∧ xv。f_G(x) ∨_{(u,v)∈E} (xu ∧ xv)但这个 DNF 通常不是无歧义的。比如三角形 K3 的三条边对应的三个项在三个顶点都为 1 时三者为真。普通 DNF 并不介意这种重叠但无歧义 DNF 需要把这些边重新组织成“互不重叠”的块。3.2 完全二部图与 biclique完全二部图 K_{A,B} 是指顶点被分成两个非空集合 A 和 B且 A 中每个顶点都与 B 中每个顶点相连A 内部和 B 内部没有边。在文献中K_{A,B} 也常被叫作 biclique即二部团。一个重要操作是把图 G 的边集覆盖或划分成若干 biclique。biclique 覆盖允许 biclique 之间的边有重叠目标是让每个 biclique 的边集并起来等于 E(G)biclique 划分要求每个 biclique 的边集互不相交所有 biclique 的边集并起来恰好等于 E(G)。显然划分比覆盖更难做到因为一旦重叠就不符合要求。来看两个具体例子C4也就是 4 个顶点的环它本身就是 K_{2,2}所以最小 biclique 划分数是 1K44 个顶点的完全图需要 3 个 biclique 才能划分完 6 条边。3.3 从划分到项的直觉对应如果 E(G) 可以被划分成 m 个 biclique那么每个 biclique 对应一个合取项把这个 biclique 两个端点集合中的所有变量都写成正文字。这种 DNF 使用的项数等于 m比逐条边写项的 |E| 更紧凑。不过需要注意这里的 DNF 未必是无歧义的。两个 biclique 如果共享某个顶点就可能出现一个赋值同时命中两个项。要构造无歧义 DNF通常还需要引入辅助变量或更精细的文字设计。所以严格的结论是biclique 划分数与某种带冲突约束的 DNF 规模之间存在深刻联系但“直接一一对应”只是一种直观理解不能当作定理使用。真正引导研究者去思考的是 Alon-Saks-Seymour 猜想所关心的那座桥梁。4. Alon-Saks-Seymour 猜想从线性上界到反例4.1 猜想的陈述Alon、Saks 和 Seymour 在研究图覆盖问题时提出了一个猜想如果图 G 的边集可以被划分成 m 个完全二部图那么 G 的色数 χ(G) 不超过 m 的线性阶。更流行的表述是χ(G) ≤ m 1其中 χ(G) 是图 G 的色数也就是给顶点染色、使得相邻顶点颜色不同所需的最少颜色数。猜想的边界情况是容易验证的当 m1 时G 是一个完全二部图的子图一定是二部图所以 χ(G)≤2当 m|E| 时每一条边单独作为一个 biclique那么普通边贪心染色给 χ(G)≤|E|1。真正的问题是在 m 很小时色数是否仍被一个关于 m 的线性函数控制4.2 为什么这个猜想很有吸引力如果猜想成立会带来很强的结构结论一张图的边集如果可以分成很少的 biclique那这图一定可以用很少的颜色正确染色。这相当于说“biclique 划分数小”意味着“图的可着色性强”。从算法角度看色数一般很难计算但如果我们能估计 biclique 划分数就能给色数提供一个有效上界。更重要的是这会给无歧义 DNF 的复杂度研究带来工具DNF 的合取项数量对应划分的块数色数又对应某种布尔函数复杂度参数两者之间的不等式可以把看似无关的下界问题互相转化。这也是为什么这个猜想在 2012 年被证伪之前吸引了大量组合数学家的关注。4.3 反例Huang-Sudakov 的工作2012 年Huang 和 Sudakov 给出了决定性的反例。他们构造了一张图 G其边集可以被划分成 m 个完全二部图但色数不是线性的而是达到了大约 m 的 6/5 次方χ(G) ≥ m^{6/5}更精确的叙述中往往还有对数因子我们不在这里纠结细节。关键是这个反例说明 Alon-Saks-Seymour 猜想的原始线性上界是错的。有趣的是他们使用的构造工具不是完全随机的图而是结合了图论、线性代数和概率方法。这种“随机但带代数结构”的构造后来成为证明各种下界的常见范式。4.4 猜想失败之后剩下了什么猜想虽然被证伪但这个问题并没有结束。反过来可以问biclique 划分数为 m 的图其色数最大能到多少也就是说我们需要求最大可能的 χ(G) 关于 m 的增长阶已知下界是超线性的 m^{6/5} 量级后续又有工作进一步改进了构造把差距拉大。但精确的指数级究竟是多少仍然是一个开放问题。这个问题在组合数学中属于“色数 vs 结构覆盖数”这一大家族与很多经典猜想都有联系。对无歧义 DNF 而言这种反例构造同样有启示它说明“合取项很少”并不自动意味着“布尔函数的复杂度很低”。看似结构简单的划分也可能编码出非常复杂的真值表行为。5. 用 Python 做小规模实验理论文章容易让人越读越抽象所以我用 Python 写了一个小工具输入一张小图自动计算它的色数和最小 biclique 划分数。由于算法是穷举只适合顶点数不超过 6 或 7 的小图但它能帮助我们直观理解 m 和 χ(G) 的关系。5.1 实验目标我们要验证三个小例子C4自身是 K_{2,2}所以 m1χ2K4m3χ4C5m3χ3。可以看到后两个都满足 χ≤m1这也解释了为什么原始猜想看起来“挺合理”。5.2 计算色数先实现一个简单的回溯染色算法。对 n≤7 的图来说效率足够。def chromatic_number(n, edges): adj [[False] * n for _ in range(n)] for u, v in edges: adj[u][v] adj[v][u] True best n color [-1] * n def dfs(i, k): nonlocal best if k best: return if i n: best min(best, k) return used set() for j in range(n): if adj[i][j] and color[j] ! -1: used.add(color[j]) for c in range(k): if c not in used: color[i] c dfs(i 1, k) color[i] -1 if k 1 best: color[i] k dfs(i 1, k 1) color[i] -1 dfs(0, 0) return best这个算法从 0 开始分配颜色始终使用最小的未用颜色来尝试新的颜色槽是一种典型的回溯染色。5.3 枚举所有 biclique接下来枚举图里所有可能作为划分块的 biclique。一个 biclique 由两个不相交的非空顶点集合 A 和 B 决定并且要求 A 中每个顶点与 B 中每个顶点都相连。def all_bicliques(n, edges): edge_set set(tuple(sorted(e)) for e in edges) result set() vertices range(n) for mask_a in range(1, 1 n): A [i for i in vertices if (mask_a i) 1] if not A: continue remaining ((1 n) - 1) ^ mask_a sub remaining while sub: B [i for i in vertices if (sub i) 1] ok True for a in A: for b in B: if tuple(sorted((a, b))) not in edge_set: ok False break if not ok: break if ok: es frozenset(tuple(sorted((a, b))) for a in A for b in B) result.add(es) sub (sub - 1) remaining return list(result)这里用整数掩码表示顶点集合。枚举顺序是先选 A再在剩余顶点中枚举 B。由于 A 和 B 顺序互换会得到同一个边集最终用 set 去重。5.4 递归求最小划分当我们有了所有候选 biclique就可以用递归搜索求最小划分数。核心策略是每次找到一条尚未被覆盖的边尝试用所有包含它的 biclique 去覆盖然后继续递归。def biclique_partition_number(n, edges): edge_set set(tuple(sorted(e)) for e in edges) bics all_bicliques(n, edges) edge_to_bics {} for e in edge_set: edge_to_bics[e] [] for idx, es in enumerate(bics): for e in es: edge_to_bics[e].append(idx) best len(edges) covered set() edge_list list(edge_set) def dfs(cnt): nonlocal best if cnt best: return target None for e in edge_list: if e not in covered: target e break if target is None: best min(best, cnt) return for idx in edge_to_bics[target]: es bics[idx] if es covered: continue covered | es dfs(cnt 1) covered - es dfs(0) return best由于每个候选 biclique 的边集之间不能重叠递归深度不会超过边数所以适合小图暴力验证。5.5 运行与结果说明把上面的函数组合起来对三个图分别调用if __name__ __main__: c4 [(0, 1), (1, 2), (2, 3), (3, 0)] k4 [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)] c5 [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)] for name, graph in [(C4, c4), (K4, k4), (C5, c5)]: chi chromatic_number(4 if name ! C5 else 5, graph) m biclique_partition_number(4 if name ! C5 else 5, graph) print(f{name}: m{m}, chi{chi}, chi m1: {chi m 1})预期输出C4: m1, chi2, chi m1: True K4: m3, chi4, chi m1: True C5: m3, chi3, chi m1: True小图上的现象都符合猜想但这并不能说明什么因为反例构造需要把图做得非常大m 和顶点数一起增长才能让色数超过线性上界。6. 常见误区与高频问题问题现象或误区具体说明解决思路把 DNF 当成游戏《地下城与勇士》本文 DNF 是析取范式属于布尔逻辑看上下文理论计算机科学、编译原理、电路设计中的 DNF 一定指析取范式混淆 biclique 覆盖与 biclique 划分覆盖允许边重叠划分要求边集两两不相交在阅读论文时先看原文用的是 cover 还是 partition以为反例说明猜想“完全关闭”Huang-Sudakov 否定了线性上界但色数与 m 的最佳上界仍然开放不要认为“证明了错”就等于“没问题了”把色数当成补图的团数图 G 的色数不等于补图中最大团的大小虽然二者有对偶关系但不能画等号用最小编制染色定义来理解色数用最大团来理解补图以为最小 DNF 一定无歧义