图的收缩不变量与图子式定理
字数 2192 2025-12-22 00:56:56

图的收缩不变量与图子式定理

好的，我们现在来学习“图的收缩不变量与图子式定理”。这是一个连接图的结构性质与图子式理论的核心概念。

第一步：核心概念的回顾与界定

首先，我们需要明确几个你已经学过的基础概念，它们是理解今天词条的前提：

  1. 图的收缩：这是一种图运算，通过将一条边的两个端点合并为一个新的顶点，并保持与其他顶点的连接关系，从而得到一个新的、更小的图。
  2. 图的子式：如果图H可以通过对图G反复进行删除边、删除孤立顶点、收缩边这三种操作得到，那么我们就称H是G的一个子式。
  3. 不变量：在图论中，一个不变量是一个函数f，它给每个图G分配一个值（通常是数字），使得如果两个图G和H是同构的，那么f(G) = f(H)。也就是说，同构的图拥有相同的函数值。

第二步：什么是收缩不变量？

基于以上概念，我们给出“收缩不变量”的精确数学定义：

定义：对于一个图参数（或函数）f，如果它对任意图G和G通过收缩任意一条边e所得到的图G/e，都满足 f(G) ≥ f(G/e)，那么这个参数f就被称为一个收缩不变量。

关键点解释：

  • “不变量”在这里的语境：这里的“不变量”并非指在同构下不变，而是指在收缩运算下“单调不增”。收缩操作通常会使图的结构变得更简单，因此许多描述图复杂度的参数在收缩后不会增加。
  • 举例说明：考虑图的色数χ(G)。如果我们收缩图G中的一条边，得到图G/e。直观上，收缩可能减少着色所需的颜色（例如，将两个不同颜色的点合并后，新点只需一种颜色）。但绝不可能需要更多颜色，因为你总是可以把G/e的着色方案“拉回”到G上（将合并的顶点赋予同一种颜色）。因此，色数χ是一个收缩不变量，即 χ(G) ≥ χ(G/e)。
  • 其他收缩不变量的例子（你可能已学过）：
    • 团数ω(G)（最大完全子图的大小）。
    • 树宽tw(G)。
    • 亏格γ(G)（嵌入所需曲面的最小亏格）。
    • 奇圈长度作为子式存在性（例如，是否包含K₃, K₅子式与平面性有关）。

第三步：收缩不变量的重要意义

为什么我们要研究收缩不变量？因为它与图的子式关系紧密相连。

性质：如果图参数f是一个收缩不变量，并且f在删除边和顶点时也单调（即删除操作不会使f值增大），那么对于任意的图G和它的子式H，我们有 f(G) ≥ f(H)。

这个性质非常强大。它意味着，如果我们知道图G的某个收缩不变量f的值很大，那么G就不可能包含那些f值更大的图作为其子式。这为我们排除特定子式的存在提供了工具。

第四步：从收缩不变量到图子式定理

图子式理论中的一个核心目标是寻找这样的定理：一个图不包含某个特定图H作为子式，当且仅当它具有某种良好的结构性质。收缩不变量是构建这种“当且仅当”关系的桥梁。

经典案例——平面图与Kuratowski定理的另一种视角：

  • 已知平面图是不包含K₅（5个顶点的完全图）和K₃,₃（完全二分图）作为子式的图。
  • “可平面性”本身可以看作一个（二元）参数：可平面（是/否）。这个参数在收缩下是保持的（收缩一条边不会让一个非平面图变成平面图，但可能让平面图保持平面）。从这个角度看，“可平面性”是一个在子式关系下封闭的图族性质。
  • Kuratowski定理说：一个图是平面图 当且仅当 它不包含K₅或K₃,₃作为子式。这正是一个子式定理的典范。

第五步：罗伯逊-西摩定理——图子式理论的巅峰

这是图论中里程碑式的定理，它深刻地揭示了收缩不变量和子式之间的普遍规律。

罗伯逊-西摩定理主要包含两部分：

  1. 子式有限性定理：对于任意给定的有限图H，不包含H作为子式的所有图，其子式集合是良拟序的。简单但不严格地说，任何一个“不包含H子式”的图族中，不存在一个无限序列，使得每个图都不是前一个图的子式。这保证了在这样的图族中，任何收缩不变量都有有限多个极值点。
  2. 结构定理：对于任意给定的有限图H，不包含H作为子式的图，其结构可以被清晰地描述。大致上，这样的图可以通过将一些“几乎可以嵌入在某个固定曲面上的图”和少量“例外顶点”沿着树状结构（称为“树分解”）粘合而成。这里的“固定曲面”由H决定。

第六步：收缩不变量在图子式定理中的角色

罗伯逊-西摩定理的结构性结论，为证明关于收缩不变量的普遍性定理铺平了道路。一个重要的推论是：

对于任意一个在子式关系下单调的图参数（即收缩和删除操作不会使其增大的参数，也就是我们讨论的收缩不变量，若考虑删除操作则常称为子式单调参数），如果它在某个不包含固定子式H的图族上是无界的（即可以取任意大的值），那么它必然在所有图的集合上也是无界的。

换句话说，任何一个“性质良好”（子式单调）的参数，如果存在一个“障碍”（比如某个图H）能将其值限制在一定范围内，那么这个参数的值在任何图中都有一个由该“障碍”决定的绝对上界。

总结：
“图的收缩不变量”是一类在收缩运算下值不会增加的图参数（如色数、树宽、亏格）。它们与“子式”概念天然契合。图子式定理（以罗伯逊-西蒙定理为代表）则深刻地指出，任何一个不包含某固定子式H的图族，其结构都是高度规整的，并且任何子式单调参数（收缩不变量）在该族图上的行为都受到H的严格制约。因此，收缩不变量是理解和刻画图在子式关系下结构分类的关键工具和度量标准。

图的收缩不变量与图子式定理 好的，我们现在来学习“图的收缩不变量与图子式定理”。这是一个连接图的结构性质与图子式理论的核心概念。 第一步：核心概念的回顾与界定 首先，我们需要明确几个你已经学过的基础概念，它们是理解今天词条的前提： 图的收缩 ：这是一种图运算，通过将一条边的两个端点合并为一个新的顶点，并保持与其他顶点的连接关系，从而得到一个新的、更小的图。 图的子式 ：如果图H可以通过对图G反复进行 删除边、删除孤立顶点、收缩边 这三种操作得到，那么我们就称H是G的一个 子式 。 不变量 ：在图论中，一个 不变量 是一个函数f，它给每个图G分配一个值（通常是数字），使得如果两个图G和H是同构的，那么f(G) = f(H)。也就是说，同构的图拥有相同的函数值。 第二步：什么是收缩不变量？ 基于以上概念，我们给出“收缩不变量”的精确数学定义： 定义 ：对于一个图参数（或函数）f，如果它对任意图G和G通过收缩任意一条边e所得到的图G/e，都满足 f(G) ≥ f(G/e) ，那么这个参数f就被称为一个 收缩不变量 。 关键点解释 ： “不变量”在这里的语境 ：这里的“不变量”并非指在同构下不变，而是指在 收缩运算下“单调不增” 。收缩操作通常会使图的结构变得更简单，因此许多描述图复杂度的参数在收缩后不会增加。 举例说明 ：考虑图的 色数χ(G) 。如果我们收缩图G中的一条边，得到图G/e。直观上，收缩可能减少着色所需的颜色（例如，将两个不同颜色的点合并后，新点只需一种颜色）。但绝不可能需要更多颜色，因为你总是可以把G/e的着色方案“拉回”到G上（将合并的顶点赋予同一种颜色）。因此， 色数χ是一个收缩不变量 ，即 χ(G) ≥ χ(G/e)。 其他收缩不变量的例子 （你可能已学过）： 团数ω(G) （最大完全子图的大小）。 树宽tw(G) 。 亏格γ(G) （嵌入所需曲面的最小亏格）。 奇圈长度 作为子式存在性（例如，是否包含K₃, K₅子式与平面性有关）。 第三步：收缩不变量的重要意义 为什么我们要研究收缩不变量？因为它与图的 子式关系 紧密相连。 性质 ：如果图参数f是一个收缩不变量，并且f在删除边和顶点时也单调（即删除操作不会使f值增大），那么对于任意的图G和它的子式H，我们有 f(G) ≥ f(H) 。 这个性质非常强大。它意味着，如果我们知道图G的某个收缩不变量f的值很大，那么G就不可能包含那些f值更大的图作为其子式。这为我们 排除特定子式 的存在提供了工具。 第四步：从收缩不变量到图子式定理 图子式理论中的一个核心目标是寻找这样的定理： 一个图不包含某个特定图H作为子式，当且仅当它具有某种良好的结构性质 。收缩不变量是构建这种“当且仅当”关系的桥梁。 经典案例——平面图与Kuratowski定理的另一种视角 ： 已知 平面图 是不包含K₅（5个顶点的完全图）和K₃,₃（完全二分图）作为 子式 的图。 “可平面性”本身可以看作一个（二元）参数：可平面（是/否）。这个参数在收缩下是保持的（收缩一条边不会让一个非平面图变成平面图，但可能让平面图保持平面）。从这个角度看， “可平面性”是一个在子式关系下封闭的图族性质 。 Kuratowski定理说：一个图是平面图 当且仅当 它不包含K₅或K₃,₃作为子式。这正是一个子式定理的典范。 第五步：罗伯逊-西摩定理——图子式理论的巅峰 这是图论中里程碑式的定理，它深刻地揭示了收缩不变量和子式之间的普遍规律。 罗伯逊-西摩定理主要包含两部分 ： 子式有限性定理 ：对于任意给定的有限图H，不包含H作为子式的所有图，其 子式集合 是良拟序的。简单但不严格地说，任何一个“不包含H子式”的图族中，不存在一个无限序列，使得每个图都不是前一个图的子式。这保证了在这样的图族中，任何收缩不变量都有有限多个极值点。 结构定理 ：对于任意给定的有限图H，不包含H作为子式的图，其结构可以被清晰地描述。大致上，这样的图可以通过将一些“几乎可以嵌入在某个固定曲面上的图”和少量“例外顶点”沿着树状结构（称为“树分解”）粘合而成。这里的“固定曲面”由H决定。 第六步：收缩不变量在图子式定理中的角色 罗伯逊-西摩定理的结构性结论，为证明关于 收缩不变量 的普遍性定理铺平了道路。一个重要的推论是： 对于任意一个在子式关系下单调的图参数（即收缩和删除操作不会使其增大的参数，也就是我们讨论的收缩不变量，若考虑删除操作则常称为 子式单调参数 ），如果它在某个不包含固定子式H的图族上是无界的（即可以取任意大的值），那么它必然在 所有图 的集合上也是无界的。 换句话说， 任何一个“性质良好”（子式单调）的参数，如果存在一个“障碍”（比如某个图H）能将其值限制在一定范围内，那么这个参数的值在任何图中都有一个由该“障碍”决定的绝对上界 。 总结 ： “图的收缩不变量”是一类在收缩运算下值不会增加的图参数（如色数、树宽、亏格）。它们与“子式”概念天然契合。 图子式定理 （以罗伯逊-西蒙定理为代表）则深刻地指出，任何一个不包含某固定子式H的图族，其结构都是高度规整的，并且任何子式单调参数（收缩不变量）在该族图上的行为都受到H的严格制约。因此，收缩不变量是理解和刻画图在子式关系下结构分类的关键工具和度量标准。