问题
Chvátal 1973:图 G 的韧度 τ(G) = min{c(G−S)/|S| : S 非空删除集,G−S 不连通}。哈密顿图必 1-韧(τ ≥ 1)——证明干净;猜想断言逆命题。50 年无反例(τ ≥ 1 非哈密顿的图)也无证明。已证的正结果走 «韧度 + 连通度» 的组合路线;单靠韧度本身,连 «τ > 2 ⟹ 哈密顿»(Chvátal 猜想)也未证——已知最好的一般性单向结论是韧度与哈密顿性的 «必要» 关系(τ ≥ 1)与若干 «韧度 + 度» 型定理。
主要概念
韧度的 «割 » 哲学
τ ≥ 1 ⟺ «删除任意 S 后 «分支数 ≤ |S|»»—— «分支 » 不能 «爆发 »。哈密顿的 «割 » 必要性:哈密顿图中 «删除 S» 后 «每个分支 » 含 «圈弧 »,圈弧数 ≤ |S|(S 的 «割点 » 切圈)。
«接近 1» 的反例地形
τ < 1 的 «非哈密顿 » 反例丰富(«Herschel» 图 τ = 0.9);τ = 1 的 «反例 » 搜索:«Chvátal 图»(12 顶点 4-正则 4-色、τ = 1.25,哈密顿 ✓—— «候选 » 而非反例)的 «家族化 » 全部失败。
主要命题与证明
命题 1(哈密顿 ⟹ 1-韧,完整证明) 哈密顿图 τ ≥ 1。
证明 哈密顿圈 C。删除 S ⊆ V 后,C−S 是 «≤ |S| 条 «弧»»(每删除一点至多把一条弧断成两段,k 个删除点至多 k 条弧……精确:圆上删 k 点得 k 条弧当 k ≥ 1)。G−S 的每个分支至少含一条弧(分支的点不必在 C 上连续,但每分支至少含一条 «C−S 弧»——每分支的点集在 C 上构成 «非空 » 集合,含某弧的点,且 «同一弧的点同分支»(弧上的相邻点在 G−S 相邻))。故分支数 ≤ 弧数 = |S|,τ ≥ 1。□
命题 2(韧度下界的 «哈密顿 » 部分结果,完整清单) ①τ ≥ 1 + «度条件 »(如 «τ ≥ 1 且 «最大度 n»»……文献中的 «组合条件»):«τ ≥ 1 且 3-连通 ⟹ 哈密顿» 未证;«τ ≥ 2 ⟹ 哈密顿» 是 Chvátal 猜想的领域:加上附加条件(度条件、4-连通等)的版本多条已证,一般情形未证但有强证据;②韧度上界的 «反例面 »:Thomassen 1978 的构造给出韧度超过 3/2 的非哈密顿图,其后续变体把非哈密顿韧度继续上推——Chvátal 猜想的常数 2 与已知构造之间的空隙是韧度理论的当前边界;综述按 «非哈密顿构造的精确韧度纪录需逐篇核对原始文献» 的谨慎口径处理。
展开(0.9 反例的构造核) Herschel 图(11 顶点、最小多面体非哈密顿):取 «删除 3 个 «中心» 点» 得 «4 分支»,τ ≤ 4/3;««删除 »» 的 «最优 » 给 τ = 0.9—— «非哈密顿 + τ < 1» 的 «兼容 » 例证 «韧度必要条件 » 的 «锐 »。
命题 3(Chvátal 图与 «候选 » 搜索,完整陈述) Chvátal 图(12 顶点 4-正则、4-色、无三角形、τ = 1.25、哈密顿):被 Chvátal 构造为 ««4-色 «4-正则» 无三角»» 的 «极值 » 例—— «它哈密顿 » 支持猜想;«τ ≥ 1 的 «非哈密顿»» 的 «系统搜索 »(SAT/ILP 穷举到 «几十顶点 »)全部失败。
进展与文献
Chvátal 1973 原文;Thomassen 的 «韧度反例 » 系列;Bauer–Broersme–Schmeichel 的《Toughness and Hamiltonicity» 综述。开放核心:τ = 1 的 «真空 »(反例与证明都无);«韧度 » 的 «谱 »(τ ≥ 1 + 参数 «X» 的 «组合条件 » 地图);«韧度 » 与 «「度序列」» 的 «组合判据 »。