图的收缩不变量与收缩临界图
字数 2376 2025-12-24 17:33:59

图的收缩不变量与收缩临界图

我们先从一个具体的图收缩运算开始理解。

  1. 回顾“图的收缩运算”概念：假设我们有一个图 \(G\)。选定一条边 \(e = uv\)，对其进行“收缩”操作，意味着将这条边的两个端点 \(u\) 和 \(v\) 合并成一个新的顶点 \(w\)，原来与 \(u\) 或 \(v\) 相连的边（除了被收缩的边 \(e\) 自身消失）现在都连接到 \(w\) 上。如果这导致出现平行边（多条边连接相同两个顶点）或自环（边连接顶点到自身），通常在简单图讨论中会保留它们，但在某些理论讨论中（如图子式理论）会保留。通过一系列收缩（以及删除边、删除顶点操作）得到的图称为 \(G\) 的子式。

  2. 收缩不变量的定义：这是我们要深入的核心。一个图参数（例如：色数 \(\chi(G)\)，顶点连通度 \(\kappa(G)\)，边连通度 \(\lambda(G)\)，团数 \(\omega(G)\)，独立数 \(\alpha(G)\) 等）被称为是收缩不变量，如果对图 \(G\) 进行任意单次边收缩操作得到的图 \(G/e\)，都满足该参数的值不增加。更形式化地，对于一个图参数 \(f(G)\)，如果对于图 \(G\) 的每条边 \(e\)，都有 \(f(G/e) \le f(G)\)，则称 \(f\) 是收缩不变量。

  3. 为什么“不增加”是重要的：这确保了参数在“简化”图（通过收缩）的过程中不会变大。收缩通常会让图变得更“小”或更“简单”，一个不变量在这种简化操作下保持不增，意味着这个参数衡量了图的某种“复杂度”或“抵抗收缩的能力”。许多重要的图参数都是收缩不变量：

  • 色数 \(\chi(G)\)：将两个顶点合并，新图的染色方案可以自然地导出原图的一个染色方案（将合并前的两个顶点染同色），所以 \(\chi(G/e) \le \chi(G)\)。这是最经典的收缩不变量之一，也是研究如Hadwiger猜想的出发点。
  • 分数色数 \(\chi_f(G)\)：与色数类似，具有不增的性质。
    • 奇围长：图中最短奇圈的长度。收缩边可能缩短奇圈的长度，但不会创造更长的奇圈，因此也是不增的。
  • 某些连通度参数：在一些定义下，边连通度 \(\lambda(G)\) 是收缩不变量。收缩边可能会破坏边割，但不会创造出新的、更小的边割。
  1. 收缩临界图的概念：这是收缩不变量理论中的核心研究对象。给定一个收缩不变量 \(f\) 和一个整数 \(k\)，如果图 \(G\) 满足：
  • \(f(G) \ge k\)，
  • 但是对于 \(G\) 的每一条边 \(e\) 进行收缩，都有 \(f(G/e) < k\)，
    那么我们称图 \(G\) 是 \(f$-$k\)-临界的，或简称为关于参数 \(f\) 的收缩临界图。
  • 换句话说，\(G\) 本身的参数值至少为 \(k\)，但只要你收缩它的任何一条边，这个参数值就会“掉下来”（严格小于 \(k\)）。这意味着 \(G\) 的每一条边对于维持其高参数值都是“关键”的。没有一条边是冗余的。

  1. 最著名的例子：色临界图：当收缩不变量 \(f\) 取为色数 \(\chi\) 时，\(\chi$-$k\)-临界图就是我们熟知的 \(k\)-色临界图。它的定义是：\(\chi(G) = k\)，但收缩（等价地，在顶点着色意义下，删除任何一条边）任意一条边后，新图的色数小于 \(k\)（即等于 \(k-1\)）。这是图着色理论中研究得极为透彻的对象，例如，我们知道 \(k\)-色临界图的最小度至少是 \(k-1\)，并且是块（2-连通，除非是完全图 \(K_2\)）。

  2. 收缩临界图的结构性质：研究收缩临界图的目标，是刻画那些“极小”地具有高参数值的图的结构。这类图通常具有一些很强的限制性性质，例如：

  • 高连通性：为了使得收缩任何一条边都会降低参数值，图本身必须足够“紧密”和“健壮”。因此，收缩临界图通常是高度连通的（顶点连通度和边连通度至少达到某个与参数 \(k\) 相关的下界）。
  • 最小度条件：类似于色临界图的最小度下界，许多收缩临界图也有最小度下界。例如，关于色数的Hadwiger猜想（断言如果 \(\chi(G) \ge k\)，则 \(G\) 包含 \(K_k\) 子式）可以等价地表述为：每个 \(K_k\)-子式临界图（即不含 \(K_k\) 子式，但收缩任何一条边都会产生 \(K_k\) 子式）的色数小于 \(k\)。研究这类临界图的最小度是证明猜想的关键途径之一。
    • 边密度：由于高度连通且没有冗余边，收缩临界图的边数相对于顶点数往往较多。
  1. 收缩临界图与Hadwiger猜想：这是收缩临界图概念最重要的用武之地。Hadwiger猜想（图论中最著名的开放问题之一）断言：如果一个图 \(G\) 的色数 \(\chi(G) \ge k\)，那么 \(G\) 包含完全图 \(K_k\) 作为一个子式。这个猜想等价于：不存在 \(K_k\)-子式临界图（即，不含 \(K_k\) 子式，但收缩任意边后会产生 \(K_k\) 子式的图）的色数达到或超过 \(k\)。因此，研究关于“不含 \(K_k\) 子式”这个性质的收缩临界图（即极小反例的结构），成为进攻Hadwiger猜想的核心策略。人们试图证明这类图具有某些“好”的性质（比如存在一个度数很小的顶点），从而推出矛盾，或者找到不可避免的构型。

总结来说，收缩不变量定义了图参数在简化操作下的行为准则，而收缩临界图则是满足该不变量特定阈值的“极小”图，它们结构强、性质丰富，是研究图参数极值问题和经典猜想（如Hadwiger猜想）的关键对象。

图的收缩不变量与收缩临界图 我们先从一个具体的图收缩运算开始理解。 回顾“图的收缩运算”概念 ：假设我们有一个图 \(G\)。选定一条边 \(e = uv\)，对其进行“收缩”操作，意味着将这条边的两个端点 \(u\) 和 \(v\) 合并成一个新的顶点 \(w\)，原来与 \(u\) 或 \(v\) 相连的边（除了被收缩的边 \(e\) 自身消失）现在都连接到 \(w\) 上。如果这导致出现平行边（多条边连接相同两个顶点）或自环（边连接顶点到自身），通常在简单图讨论中会保留它们，但在某些理论讨论中（如图子式理论）会保留。通过一系列收缩（以及删除边、删除顶点操作）得到的图称为 \(G\) 的 子式 。 收缩不变量的定义 ：这是我们要深入的核心。一个 图参数 （例如：色数 \(\chi(G)\)，顶点连通度 \(\kappa(G)\)，边连通度 \(\lambda(G)\)，团数 \(\omega(G)\)，独立数 \(\alpha(G)\) 等）被称为是 收缩不变量 ，如果对图 \(G\) 进行任意单次边收缩操作得到的图 \(G/e\)，都满足该参数的值不增加。更形式化地，对于一个图参数 \(f(G)\)，如果对于图 \(G\) 的每条边 \(e\)，都有 \(f(G/e) \le f(G)\)，则称 \(f\) 是 收缩不变量 。 为什么“不增加”是重要的 ：这确保了参数在“简化”图（通过收缩）的过程中不会变大。收缩通常会让图变得更“小”或更“简单”，一个不变量在这种简化操作下保持不增，意味着这个参数衡量了图的某种“复杂度”或“抵抗收缩的能力”。许多重要的图参数都是收缩不变量： 色数 \(\chi(G)\) ：将两个顶点合并，新图的染色方案可以自然地导出原图的一个染色方案（将合并前的两个顶点染同色），所以 \(\chi(G/e) \le \chi(G)\)。这是最经典的收缩不变量之一，也是研究如Hadwiger猜想的出发点。 分数色数 \(\chi_ f(G)\) ：与色数类似，具有不增的性质。 奇围长 ：图中最短奇圈的长度。收缩边可能缩短奇圈的长度，但不会创造更长的奇圈，因此也是不增的。 某些连通度参数 ：在一些定义下，边连通度 \(\lambda(G)\) 是收缩不变量。收缩边可能会破坏边割，但不会创造出新的、更小的边割。 收缩临界图的概念 ：这是收缩不变量理论中的核心研究对象。给定一个收缩不变量 \(f\) 和一个整数 \(k\)，如果图 \(G\) 满足： \(f(G) \ge k\)， 但是对于 \(G\) 的 每一条 边 \(e\) 进行收缩，都有 \(f(G/e) < k\)， 那么我们称图 \(G\) 是 \(f\)-\(k\)-临界 的，或简称为关于参数 \(f\) 的 收缩临界图 。 换句话说，\(G\) 本身的参数值至少为 \(k\)，但只要你收缩它的任何一条边，这个参数值就会“掉下来”（严格小于 \(k\)）。这意味着 \(G\) 的每一条边对于维持其高参数值都是“关键”的。没有一条边是冗余的。 最著名的例子：色临界图 ：当收缩不变量 \(f\) 取为色数 \(\chi\) 时，\(\chi\)-\(k\)-临界图就是我们熟知的 \(k\)-色临界图 。它的定义是：\(\chi(G) = k\)，但收缩（等价地，在顶点着色意义下，删除任何一条边）任意一条边后，新图的色数小于 \(k\)（即等于 \(k-1\)）。这是图着色理论中研究得极为透彻的对象，例如，我们知道 \(k\)-色临界图的最小度至少是 \(k-1\)，并且是块（2-连通，除非是完全图 \(K_ 2\)）。 收缩临界图的结构性质 ：研究收缩临界图的目标，是刻画那些“极小”地具有高参数值的图的结构。这类图通常具有一些很强的限制性性质，例如： 高连通性 ：为了使得收缩任何一条边都会降低参数值，图本身必须足够“紧密”和“健壮”。因此，收缩临界图通常是 高度连通的 （顶点连通度和边连通度至少达到某个与参数 \(k\) 相关的下界）。 最小度条件 ：类似于色临界图的最小度下界，许多收缩临界图也有最小度下界。例如，关于色数的Hadwiger猜想（断言如果 \(\chi(G) \ge k\)，则 \(G\) 包含 \(K_ k\) 子式）可以等价地表述为：每个 \(K_ k\)-子式临界图（即不含 \(K_ k\) 子式，但收缩任何一条边都会产生 \(K_ k\) 子式）的色数小于 \(k\)。研究这类临界图的最小度是证明猜想的关键途径之一。 边密度 ：由于高度连通且没有冗余边，收缩临界图的边数相对于顶点数往往较多。 收缩临界图与Hadwiger猜想 ：这是收缩临界图概念最重要的用武之地。 Hadwiger猜想 （图论中最著名的开放问题之一）断言：如果一个图 \(G\) 的色数 \(\chi(G) \ge k\)，那么 \(G\) 包含完全图 \(K_ k\) 作为一个 子式 。这个猜想等价于：不存在 \(K_ k\)-子式临界图（即，不含 \(K_ k\) 子式，但收缩任意边后会产生 \(K_ k\) 子式的图）的色数达到或超过 \(k\)。因此，研究 关于“不含 \(K_ k\) 子式”这个性质的收缩临界图 （即极小反例的结构），成为进攻Hadwiger猜想的核心策略。人们试图证明这类图具有某些“好”的性质（比如存在一个度数很小的顶点），从而推出矛盾，或者找到不可避免的构型。 总结来说， 收缩不变量 定义了图参数在简化操作下的行为准则，而 收缩临界图 则是满足该不变量特定阈值的“极小”图，它们结构强、性质丰富，是研究图参数极值问题和经典猜想（如Hadwiger猜想）的关键对象。