图的收缩与可去边/可去顶点 我们来循序渐进地学习“图的收缩与可去边/可去顶点”这一概念。理解这个概念，能帮助我们洞察图的结构，特别是与图的连通性、平面性、以及更复杂的“子式”理论相关的重要性质。 第一步：明确“图的收缩”操作 核心定义 ：在图论中，收缩是一种基本的图变换操作。它作用于图的一条边。 操作过程 ：假设我们有一个图 \( G \)，以及它的一条边 \( e = uv \)，即连接顶点 \( u \) 和 \( v \) 的边。 收缩边 \( e \) 是指： 将这条边 \( e \) 移除。 将这条边的两个端点 \( u \) 和 \( v \) 合并成一个新的顶点 \( w \)。 所有原来与 \( u \) 或 \( v \) 相连的边（除了被移除的 \( e \) 本身），现在都与新顶点 \( w \) 相连。 如果这个合并过程产生了 平行边 （连接同一对顶点的多条边）或 自环 （一个顶点连接到自己的边），通常 保留它们 。但在某些特定上下文中（如讨论简单图时），可能会选择去掉这些平行边和自环。 结果图 ：通过收缩边 \( e \) 得到的图，记作 \( G/e \)。 直观理解 ：你可以想象用手捏住边 \( e \) 的两端，把它们“捏”成一个点，这条边本身消失了，原来连接这两个点的其他边现在都连接到这个新的“融合点”上。 第二步：收缩的延伸——“图的子式” 子式定义 ：如果一个图 \( H \) 可以通过对图 \( G \) 进行一系列以下操作得到，则称 \( H \) 是 \( G \) 的一个 子式 ： 删除边 ：移除图的一条边。 删除顶点 ：移除一个顶点及其所连接的所有边。 收缩边 ：即我们第一步定义的收缩操作。 重要性 ：子式关系是图论中一个极其强大的概念。许多深刻的定理（如著名的 Kuratowski 平面图定理、Wagner 定理，以及四大猜想之一的 Hadwiger 猜想）都基于子式理论。它刻画了图的结构中那些“无法通过收缩消除”的固有特征。 第三步：从收缩到“可去边” 基本思想 ：“可去边”是针对某个特定图的性质 \( P \) 来定义的。这条边在某种操作下（通常是收缩）被“去掉”后，不会影响原图是否具有性质 \( P \)。 可收缩边 ：如果对图 \( G \) 的边 \( e \) 进行收缩后得到的图 \( G/e \)，仍然具有性质 \( P \)，则称边 \( e \) 是关于性质 \( P \) 的 可收缩边 。关键在于，我们通过收缩把它“简化”了，但关键性质得以保留。 经典例子——可平面图的收缩 ： 性质 \( P \) ：可平面性（即图能否画在平面上使得边仅在顶点处相交）。 一个重要结论是：对于一个可平面图，收缩任何一条边，得到的 \( G/e \) 仍然是可平面图。因为你可以想象在平面的画法上，把那条边“捏”成一个点，不会引入交叉。 因此， 对于可平面图，每条边都是关于可平面性的“可收缩边” 。这使得我们可以通过不断收缩边来简化一个可平面图，而不破坏其可平面性。 第四步：与“可去边”平行但不同的概念——“可删边” 区分操作 ：务必注意，“可去”通常包含两种主要操作： 收缩 和 删除 。我们上面讨论的是“可收缩边”。另一个概念是“可删边”。 可删边 ：如果删除图 \( G \) 的边 \( e \) 后得到的图 \( G-e \)，仍然具有性质 \( P \)，则称边 \( e \) 是关于性质 \( P \) 的 可删边 。 回到可平面图的例子 ： 删除一条边显然不会破坏可平面性，因为只是移除了一些线。所以， 对于可平面图，每条边也是关于可平面性的“可删边” 。 更复杂的例子——哈密顿图 ： 性质 \( P \) ：哈密顿性（即图中存在一个经过每个顶点恰好一次的圈）。 一条边可能既不是可删边（删了它，哈密顿圈被破坏），也不是可收缩边（收缩它可能改变图的结构，使得哈密顿圈无法对应回来）。在这种情况下，寻找和研究那些是“可去”（无论是删是缩）的边，就成为了分析图结构、设计算法（如寻找哈密顿圈）的重要工具。 第五步：引入“可去顶点” 概念类比 ：“可去顶点”的概念与“可去边”完全平行，但操作对象是顶点。 定义 ： 可删顶点 ：如果删除图 \( G \) 的顶点 \( v \) 及其关联边后得到的图 \( G-v \)，仍然具有性质 \( P \)，则称顶点 \( v \) 是关于性质 \( P \) 的 可删顶点 。 “可收缩顶点” ：这个概念不常见，因为“收缩”的标准操作对象是边。但有时会讨论删除一个顶点并将其邻居“简化”的操作，这更接近于“分解”或“折叠”的概念，并非标准的图收缩。 应用场景 ：在 图着色 问题中，研究“可去顶点”非常有用。 例如，在染色过程中，如果一个顶点的度小于图的色数 \( k \)，那么理论上可以先对图去掉这个顶点进行 \( k \)-着色，然后再因为这个顶点的邻居最多用了 \( k-1 \) 种颜色，总有一种颜色可以给它涂上。从这个角度看，这个顶点是“可删的”（就 \( k \)-可着色性而言）。 更一般地，寻找一系列“可去顶点”的顺序，就引出了 完美消除序 （已讲过）等概念，这对于弦图等特殊图类的识别和着色至关重要。 第六步：总结与意义 核心操作 ：“收缩”是理解图子式和进行图变换的基石。“可去边/可去顶点”是指在 删除 或 收缩 操作下，能保持某个特定图性质不变的边或顶点。 研究价值 ： 简化结构 ：通过反复移除可去边/顶点，可以将一个复杂的图简化，同时保留我们关心的关键性质（如平面性、着色性、哈密顿性等），便于分析和证明。 刻画极小图/临界图 ：如果一个图具有性质 \( P \)，但删除（或收缩） 任何 一条边（或一个顶点）都会失去该性质，那么这个图对于该性质就是 边临界的 （或 顶点临界的 ）。研究临界图是极值图论和结构图论的核心内容之一，它们揭示了保持一个性质所需的最基本结构。 算法设计 ：许多图算法（如平面性检测、着色算法、哈密顿圈搜索）会利用可去边/顶点的思想进行归约或分支，从而设计出更高效的算法。 总之，“图的收缩”是一个基础操作，而“可去边/可去顶点”是基于此操作和删除操作衍生出的、用于分析图在特定性质下的结构稳定性和简化可能性的重要工具。它们是连接图的基本变换与复杂结构性质之间的桥梁。