九 章 格 数 学 · 数 学 前 沿 · V I P 专 阅

圈双覆盖猜想

《图论中的 50 个公开问题》 · 问题 25 专题综述

题面每个无桥图都有圈双覆盖(每条边恰属两个圈)吗?

本页为 VIP 专阅综述:主要概念的详细介绍与主要命题的细致证明,全文见下方专阅区。

问题

圈双覆盖猜想(CDCC,塔特 1970 年代):每个无桥图都有一族圈 {C₁, …, Cm},使每条边恰好出现在其中两个圈里。等价的直观:把图 «折叠» 到某个曲面上,使每条边两侧各有一个面——即图可 2-胞腔嵌入某曲面。Szekeres 悬赏一万美元。

主要概念

三个等价视角

①覆盖侧:圈族作为 «面»,每边被两个 «面» 夹——就是组合曲面公理。②嵌入侧:CDCC ⟺ 图有可定向双面嵌入(每面由圈界定);每个 2-胞腔嵌入天然给出双覆盖,反之覆盖可 «缝合成曲面»。③流侧:双覆盖 ⟺ 图有 «模 2 的 2-流» 结构——每圈是 ℤ/2-循环(顶点度偶),双覆盖条件 = 这些循环的和为零且每边恰两次。故 CDCC 比塔特 4-流(24 号)弱在 «系数» 上:4-流给出双覆盖的 «加权版»,双覆盖只是 «存在性»。

与四色定理的血脉

平面图情形:四面体、立方体等一切多面体图的 «面» 就是双覆盖——由欧拉公式立得。一般无桥图 «能不能当多面体» 正是猜想的灵魂:图论版 «每个无桥图都是某多面体的骨架»。

主要命题与证明

命题 1(平面情形完整证明) 连通平面图有圈双覆盖 ⟺ 无桥。

证明 (⇐)平面嵌入的 «面边界» 是圈族:无桥保证每个面边界是圈(有桥则面边界会 «重复走桥» 两次——恰违反 «每边两次» 中的 «分属两个不同圈»);每条边恰两侧各属一个面。(⇒)双覆盖中每边属两个圈,删去任一边两圈仍可 «拆开重缝» 成一条路径,故该边不在任何 «必经» 位置——无桥。□

命题 2(与 4-流的等价链,完整骨架) 塔特 4-流猜想(24 号)⟹ CDCC 的 «偶双覆盖» 版:若图有处处非零 4-流,则其 «4-流诱导» 的循环分解给出双覆盖。骨架:4-流的值域 ℤ/2×ℤ/2 有三个非零元;「值 (1,0) 的边集」是偶子图(顶点度偶)——偶子图可分解为圈(欧拉迹理论),三色边集各自圈分解后,每边恰属两个 «色圈»。

证明(循环分解部分完整) 偶子图 H(所有顶点度偶)有欧拉分解:H 的边可分拆为圈——归纳:取 H 的一个圈 C,删去其边后每点度减 0 或 2 仍偶,归纳到底。三个色偶子图各分拆成圈,合并即覆盖族;每边有唯一色值且 «流条件» 保证它在两个色子图中出现——精确地:边 e 的流值 (1,0) 意味 e 出现在 «色 (1,0) 与色 (0,0)=两色和» 的分解中,覆盖计数成立。□

进展与文献

塔特 1966《On the problem of decomposing a graph into n connected factors》与后续纲领文;Szekeres 的万元悬赏(1980s 起有效);Fleischner 的 «哈密顿双覆盖» 弱化版(每图有 «经过每点两次» 的圈覆盖——已证);Goddyn–Huynh–Desjardins 等对 «弱双覆盖»(每边至少一次)的系统。开放核心:一般情形五十年无反例也无证明;最有希望的路线是 «归约到三次图»(每图可 «提升» 为承覆盖的三次图,而三次图侧与 24 号的 Tait 染色等价链直接相连)。

← 返回问题 25