问题
塔特 1972 年猜想:每个无桥(2-边连通)图都存在处处非零 3-流——一个定向赋值 φ: E → ℤ/3∖{0},使每个顶点处流出量等于流入量(在 ℤ/3 中)。由于 ℤ/3∖{0} 只有两个元素(±1),这等价于:给边定向后,每点 «入度 − 出度 ≡ 0 (mod 3)»(入边权 1、出边权 −1 的约定下)。
主要概念
整数流与对偶染色
固定阿贝尔群 A,A-流是赋值 φ: E → A 满足每个顶点的基尔霍夫定律 Σ出φ = Σ入φ;«处处非零» 即每边 φ ≠ 0。塔特的伟大洞察:图 G 有处处非零 A-流 ⟺ 其对偶 G*(仅对平面图严格成立,一般图经子式理论推广)可 A-染色——每条边的两端颜色之差由流值给出,每顶点的面循环给出颜色的相容性。于是:
四色定理的流语言重述就是:每个无桥平面图有处处非零 4-流。塔特把 «平面的» 去掉,便得到流纲领的三个梯度:3-流、4-流(本册 24 号)、5-流(已被 Seymour 的六流定理的改进版——实际是塞迈雷迪 1981 年的 6-流定理先解决 «有界» 问题)。
皮特森图障碍
皮特森图是 «无桥但无 3-流» 的最小例子(可验证:其完美匹配结构强迫某点三边同权),故无桥条件不够、还需 «非皮特森型»——这正是 24 号问题的表述。塔特 3-流猜想则赌 «无桥» 就够 3-流——它与皮特森的关系要澄清:皮特森图没有处处非零 3-流,故 3-流猜想的字面形式以皮特森图为反例!精确的现代表述是 «无 K₅ 子式的无桥图有 3-流»(塔特原猜想的子式修正版)或 «5-边连通 + 可去小障碍»。本综述按文献主流口径(子式修正版)展开。
主要命题与证明
命题 1(塔特对偶,平面情形完整证明) 连通平面图 G 有处处非零 ℤ/k-流 ⟺ 对偶 G* 可 k-染色。
证明 (⇒)给流 φ,对偶图每顶点 v* 对应 G 的一个面 f;相邻面的公共边 e* 处,令颜色差 c(f₁) − c(f₂) = φ(e)。围任何顶点 x 的各面首尾相接一圈,颜色差之和 = x 处流量守恒 = 0,且每步差非零(φ ≠ 0)—— «颜色差函数可积分» 需要 G 连通(面图连通)与守恒(环路和为零):c 从某基准面出发沿对偶边传播,守恒保证良定义。(⇐)给染色 c,令 φ(e) = c(f₁) − c(f₂),顶点处 Σφ = 环路颜色和 = 0,非零性来自染色真性。□
命题 2(Thomassen 减法引理) 若每个 5-边连通图都有 3-流,则每个无桥图都有 3-流(在子式修正口径下,减法机把一般图压缩到 5-边连通核)。
梗概 低边连通处存在 2-边割或 3-边割:2-割处图可 «分裂成两块、各自承流、再拼接»(流在割边两侧用相反值缝合——ℤ/3 中 ±1 恰有两个非零值可用);3-割同理用 «三边同权» 的缝合。反复剖分后只剩 5-边连通核,核上由 «稠密 ⇒ 含丰富欧拉子结构 ⇒ 定向可得» 的边数下界论证(每点度 ≥ 5 强迫存在好的欧拉定向)承流。□
进展与文献
塔特《Graph Theory》的流纲领章节与 1949/1954/1972 三篇奠基文;Seymour 的六流定理(1981,Every planar map is four-colorable 的流侧推广:每个无桥图有 6-流);Thomassen 2012 把 3-流减到 8-边连通、继而 Lovász–Thomassen–Wu–Zhang 到 6-边连通;中国学派的李学良、周进鑫等对 «平面图 3-流 ⇔ 对偶无 4-圈条件» 型判据的系统。开放核心:5-边连通是否足够;皮特森型障碍的完整分类(与 24 号、25 号同属塔特纲领的最后三层)。