图的收缩与子图运算 我们先从最基础的概念开始。图 G 的 子图 是指由 G 的部分顶点和部分边构成的图。更精确地说，图 H 是图 G 的子图，需要满足：H 的顶点集是 G 的顶点集的子集，H 的边集是 G 的边集的子集，并且 H 中的边的端点也必须在 H 的顶点集中。 子图运算主要有几种类型： 顶点子图 ：通过删除原图中的某些顶点（以及与之关联的所有边）得到的子图。 边子图 ：通过删除原图中的某些边（但保留所有顶点）得到的子图，也称为 生成子图 。 现在，我们引入一个更强大的运算： 图的收缩 。收缩运算允许我们通过“合并”顶点来简化图的结构，同时保留重要的拓扑和信息关联。 收缩运算的定义 给定一个图 G 和它的一条边 e = uv（连接顶点 u 和 v 的边）， 收缩边 e 是指将顶点 u 和 v 合并成一个新的顶点 w。这个操作的具体步骤如下： 从图 G 中删除边 e。 将顶点 u 和 v 合并成一个新的顶点，记作 w。 原来与 u 或 v 相连的所有边（除了被删除的 e），现在都与新顶点 w 相连。如果合并前有某条边同时连接 u 和另一个顶点 x，另一条边同时连接 v 和同一个 x，那么在收缩后，这两条边会变成连接 w 和 x 的两条 平行边 。 如果 u 和 v 之间存在除 e 外的其他边（即重边），这些边在收缩后会变成 w 的 自环 。 经过收缩操作后得到的新图，记作 G/e（读作“G 收缩 e”）。 收缩运算的性质与意义 简化结构 ：收缩运算可以减少图的顶点数和边数，是研究图的结构性质（如平面性、连通性）的有力工具。 与子图的关系 ：收缩运算和删除边、删除顶点运算一起，构成了图论中一类非常重要的运算。一个图 H 如果是通过从图 G 中经过一系列（可能是零次）的删除边、删除顶点和收缩边运算得到的，那么 H 被称为 G 的 子式 。子式理论是图论的一个核心分支。 在算法中的应用 ：一个著名的例子是 卡普算法 ，用于求解图的全局最小割。该算法的核心思想就是随机收缩边，直到图只剩下两个顶点，通过分析收缩过程来以高概率找到最小割。 为了让你更深入地理解，我们来看一个具体的例子。 收缩运算示例 考虑一个简单的图 G，它由一个三角形（3个顶点 u, v, t，边为 uv, vt, tu）和一个附加的顶点 x 组成，x 只与顶点 u 相连（边为 xu）。 初始图 G ：顶点集 {u, v, t, x}，边集 {uv, vt, tu, xu}。 操作 ：我们收缩边 e = uv。 过程 ： 删除边 uv。 将顶点 u 和 v 合并成一个新顶点，我们称之为 w。 处理其他边： 边 vt：原来连接 v 和 t，现在变为连接 w 和 t。 边 tu：原来连接 t 和 u，现在变为连接 t 和 w。注意，现在我们有两条边连接 w 和 t（一条来自 vt，一条来自 tu），这就是平行边。 边 xu：原来连接 x 和 u，现在变为连接 x 和 w。 结果图 G/e ：顶点集 {w, t, x}。边集包含：一条边连接 x 和 w，以及两条平行边连接 w 和 t。 通过这个例子，你可以看到收缩如何改变了图的连接关系。接下来，我们可以探讨由收缩和删除运算衍生出的更深刻的概念。 图子式 如前所述，如果图 H 可以通过对图 G 进行一系列以下操作而得到，则称 H 是 G 的 子式 ： 删除边。 删除顶点（及与之相连的边）。 收缩边。 子式关系是图论中一个非常重要的偏序关系。一个里程碑式的定理是 瓦格纳定理 ，它指出：一个图是平面图，当且仅当它不包含完全图 K₅ 或完全二分图 K₃,₃ 作为其子式。这说明了子式运算在刻画图的核心性质（如平面性）方面的强大能力。 细分与拓扑子式 与子式概念紧密相关的还有 细分 运算。对图的一条边进行细分，是指在该边上插入一个新的顶点，从而将一条边变成两条边。如果图 H 可以通过对图 G 的边进行细分（零次或多次）后，再取一个子图而得到，那么 H 被称为 G 的 拓扑子式 。 可以证明，如果 H 是 G 的拓扑子式，那么它一定是 G 的子式，但反之则不必然成立。拓扑子式更强调“嵌入”或“画法”上的包含关系。 总结来说，收缩运算以及由此衍生的子图运算（删除顶点、删除边）是图论中分析和变换图结构的基本工具。它们不仅是定义子式、拓扑子式等高级概念的基础，也在刻画图的禁止结构（如平面图的库拉托夫斯基定理和瓦格纳定理）、设计图算法（如最小割算法）以及研究图的复杂性方面发挥着不可替代的作用。