图的符号哈密顿性与符号圈覆盖 我们来循序渐进地理解“图的符号哈密顿性”这个概念。 第一步：基础概念的回顾与延伸 哈密顿图 ：在之前的“图的路与圈问题”中，我们已了解过，如果一个（无符号的普通）图中存在一个经过每个顶点恰好一次的圈，这个圈被称为哈密顿圈，具有哈密顿圈的图被称为哈密顿图。这是一个经典的存在性问题。 符号图 ：在“图的符号图与结构平衡理论”等词条中，我们已经建立了符号图的概念。一个符号图 Γ = (G, σ) 由一个底层图 G 和符号函数 σ: E(G) → {+1, -1} 构成，为每条边分配一个“正”或“负”的符号。 第二步：符号哈密顿性的定义 “符号哈密顿性”是哈密顿性概念在符号图上的自然推广。但推广的方式不止一种，主要分为两类： 哈密顿符号圈 ：在符号图 Γ 中，如果一个圈 C 是底层图 G 的哈密顿圈，并且我们考虑这个圈上所有边的符号，那么这个圈 C 就称为符号图 Γ 的一个哈密顿符号圈。这里的核心是 存在性 ：符号图 Γ 被称为是 符号哈密顿的 ，如果它至少包含一个哈密顿符号圈。注意，一个符号图可能有多个哈密顿圈，它们的符号和可能是不同的。 平衡的哈密顿符号圈 ：这是在符号图研究中更受关注、也更有趣的概念。在“图的符号圈与平衡性”中，我们学习过一个符号圈是平衡的，当且仅当其所有边的符号乘积为 +1。那么，一个符号图 Γ 被称为是 平衡哈密顿的 ，如果它包含一个 平衡的 哈密顿符号圈。也就是说，这个圈不仅遍历所有顶点，其符号乘积还为 +1。这是一个比普通符号哈密顿性更强的条件，因为它对圈的符号结构有额外约束。 第三步：符号圈覆盖的定义 这个概念建立在“覆盖”和“符号圈”之上。 圈覆盖 ：对于一个普通图 G，一个圈覆盖是指图 G 的一个边不交的圈的集合，使得 G 的 每一条边 都恰好被这些圈中的一个覆盖。如果允许圈共享顶点，但边必须不交。 符号圈覆盖 ：将其推广到符号图 Γ。一个符号圈覆盖是符号图 Γ 的一个边不交的符号圈的集合，使得 Γ 的每一条边都恰好被这些符号圈中的一个覆盖。我们不要求这些符号圈是平衡的，它们可以是平衡的，也可以是不平衡的。 第四步：核心问题与研究动机 将这两个概念结合起来，图论学者关心以下类型的问题： 存在性问题 ：给定一个符号图 Γ，满足什么样的度条件、连通性条件或谱条件，我们能保证它是（平衡）符号哈密顿的？或者，它存在一个符号圈覆盖？例如，人们寻找类似于普通图中 Dirac 定理（最小度 ≥ n/2 保证哈密顿性）在符号图上的类比。 符号圈覆盖的分解 ：能否将一个符号图的边集分解为特定数量的符号圈？例如，一个经典的猜想是：每个边连通度为偶数的 2-边连通符号图，都存在一个符号圈覆盖。这可以看作是普通图中“每个欧拉图可以分解为边不交的圈”在符号图上的非平凡推广。 平衡性的作用 ：平衡性条件如何影响这些存在性？已知一个平衡的符号图（即在结构上等价于一个所有边为正的普通图）在许多性质上与其底层图相似。那么，对于非平衡符号图，（平衡）哈密顿性和符号圈覆盖的存在性是否会变得更加困难或需要更强条件？ 算法与复杂性 ：判定一个给定的符号图是否（平衡）哈密顿的问题是 NP-完全的，因为它已包含经典的哈密顿圈问题作为特例。但研究某些受限图类（如平面符号图、符号完全图）上的多项式时间算法是活跃的方向。 第五步：与已有知识的联系 与 符号图 、 符号圈与平衡性 的联系是根本性的，这是定义的基础。 与 图的连通性 、 边连通度 等概念密切相关，因为连通性是存在圈和覆盖的基本前提。 与 图的路与圈问题 是直接的推广关系，是其符号版本。 与 图的分解 问题相关，因为符号圈覆盖是一种特殊的边分解。 与 图的符号图着色 等问题的联系在于，某些符号圈覆盖的存在性可以用来研究图的着性质和流，通过符号圈覆盖可以构造特定的边符号赋值，从而关联到图的定向和流多项式。 总结来说， 符号哈密顿性与符号圈覆盖 是经典图论中哈密顿圈理论和圈分解理论在符号图模型中的延伸。它研究在边的符号约束下，图中全局循环结构（遍历所有顶点或覆盖所有边）的存在性和分解方式，融合了结构图论、极值图论和组合优化的思想。