图的收缩与子图运算

字数 2128 2025-10-28 11:33:38

图的收缩与子图运算

好的，我们接下来学习图论中的一个重要概念——图的收缩与子图运算。这是理解和构造更复杂图论概念（如图的不变量、图的子式等）的基础操作。

第1步：回顾基础——什么是子图？

在深入“收缩”之前，我们必须先清晰地理解“子图”这个概念，因为收缩操作的结果可以看作是一种特殊的子图。

定义：假设我们有两个图，G = (V, E) 和 H = (V‘, E’)。如果图H的顶点集 V‘ 是图G的顶点集 V 的子集，并且图H的边集 E’ 是图G的边集 E 的子集（并且要求 E‘ 中的边的两个端点都在 V’ 中），那么我们就称 H 是 G 的一个子图。
直观理解：你可以想象从原图G中“拿走”一些顶点和一些边，剩下的部分就是G的一个子图。关键是，拿走的顶点所连接的所有边也必须同时被拿走。
类型：
- 顶点子图/诱导子图：如果我们只选择了一个顶点子集 V‘，并且保留了G中所有连接V’内顶点的边，那么得到的子图称为由V‘诱导的子图，记作 G[V’]。
- 边子图/生成子图：如果我们选择了一个边子集 E‘，并且保留这些边的所有端点，那么得到的子图称为由E’诱导的生成子图。

例子：
考虑一个简单的图G，它是一个三角形（3个顶点，3条边）。那么，任何一条边加上它的两个端点，就构成了G的一个子图（也是诱导子图）。单独的一条边（不含端点）不是子图，单独的一个顶点是子图。

第2步：核心操作——图的边收缩

“收缩”是比“取子图”更复杂的操作，它不仅能简化图，还能改变图的基本结构。

定义：设 e = uv 是图G中的一条边。将边e收缩是指将边e的两个端点u和v合并成一个新的顶点，我们通常称这个新顶点为 w。同时，删除由此产生的所有重边（如果存在）和自环（连接w和w的边）。
操作过程分解：
1. 识别目标：选择图G中的一条边e，连接顶点u和v。
2. 合并顶点：将u和v“粘合”在一起，视为一个全新的顶点w。
3. 处理关联边：
  - 原来与u或v相连的其他边（即除了边e本身），现在都变成与这个新顶点w相连。
  - 如果原来有某个顶点x同时与u和v相连，那么合并后，x将与w有两条边。根据简单图的标准定义（无重边），我们只保留一条。
  - 边e本身在合并后变成了连接w和w的边，即一个自环。根据简单图的标准定义（无自环），我们删除这个自环。
4. 得到结果：经过上述操作得到的新图，记作 G/e（读作“G收缩e”）。
直观理解：想象边e是一根可以收缩的橡皮筋，你拉着它的两端（顶点u和v）使劲拽，直到它们碰在一起变成一个点。原来连接u或v的线（边）自然就都连到了这个新的点上。

例子：
假设图G是一个四边形（4个顶点，4条边：AB, BC, CD, DA）。

我们收缩边BC。
将顶点B和C合并成一个新顶点，叫它X。
原来与B相连的边有AB和BC（BC是要被收缩的边），与C相连的边有BC和CD。
合并后：
- 边AB现在连接A和X。
- 边CD现在连接D和X。
- 边BC收缩后形成自环，删除。
- 边DA保持不变，连接D和A。
最终得到的图G/BC是一个三角形，顶点为A, D, X，边为AX, DX, AD。

第3步：广义概念——图的小子式

当我们连续进行一系列的子图操作（删除顶点、删除边）和收缩操作时，就引出了一个极其重要的概念——图的小子式。

定义：如果图H可以通过对图G进行一系列以下的操作而得到，那么称 H 是 G 的一个小子式：
1. 删除边。
2. 删除顶点（以及与之相连的所有边）。
3. 收缩边。
关键点：这些操作的顺序可以任意。你可以先删除一些边，再收缩一条边，再删除一个顶点……最终如果能得到H，那么H就是G的小子式。
重要性：小子式关系是图论中一个非常重要的偏序关系。它深刻地刻画了图的结构性质。一个著名的例子是库拉托夫斯基定理，它指出：一个图是平面图（可以画在平面上使得边不相交）的充分必要条件是，它既不包含完全图 K₅ 也不包含完全二分图 K₃，₃ 作为其小子式。

例子：
判断图G（一个立方体的骨架图）是否包含一个三角形（K₃）作为小子式。

思路：我们尝试通过操作将G变成一个三角形。
操作：我们可以通过收缩立方体上特定的边，将对立的面“压扁”，最终确实可以得到一个三角形。因此，K₃ 是G的一个小子式。
反之：一个树形结构（无环）永远无法通过收缩边（不会创造新环）得到一个有环的图，所以树不包含任何环图作为小子式。

第4步：总结与联系

子图运算（删除顶点/边）和收缩运算是图论中两种基本的、用于从已知图构造新图的工具。
子图是通过“做减法”来得到更简单的图，它保留了原图局部的部分结构。
收缩是通过“融合”顶点来简化图，它可能改变图的整体连通性等全局性质。
小子式概念将这两种操作结合起来，定义了一种更强大的“简化”关系，是现代图结构理论的核心之一，尤其在研究图的平面性、可嵌入性等拓扑性质时至关重要。

理解这些运算，为你今后学习更深入的图论主题，如图的不变量（某些参数在收缩操作下的变化）、图的分解理论以及图子式定理（罗伯逊-西摩定理）奠定了坚实的基础。

图的收缩与子图运算好的，我们接下来学习图论中的一个重要概念—— 图的收缩与子图运算。这是理解和构造更复杂图论概念（如图的不变量、图的子式等）的基础操作。第1步：回顾基础——什么是子图？在深入“收缩”之前，我们必须先清晰地理解“子图”这个概念，因为收缩操作的结果可以看作是一种特殊的子图。定义：假设我们有两个图，G = (V, E) 和 H = (V‘, E’)。如果图H的顶点集 V‘ 是图G的顶点集 V 的子集，并且图H的边集 E’ 是图G的边集 E 的子集（并且要求 E‘ 中的边的两个端点都在 V’ 中），那么我们就称 H 是 G 的一个子图。直观理解：你可以想象从原图G中“拿走”一些顶点和一些边，剩下的部分就是G的一个子图。关键是，拿走的顶点所连接的所有边也必须同时被拿走。类型：顶点子图/诱导子图：如果我们只选择了一个顶点子集 V‘，并且保留了G中所有连接V’内顶点的边，那么得到的子图称为由V‘诱导的子图，记作 G[ V’ ]。边子图/生成子图：如果我们选择了一个边子集 E‘，并且保留这些边的所有端点，那么得到的子图称为由E’诱导的生成子图。例子：考虑一个简单的图G，它是一个三角形（3个顶点，3条边）。那么，任何一条边加上它的两个端点，就构成了G的一个子图（也是诱导子图）。单独的一条边（不含端点）不是子图，单独的一个顶点是子图。第2步：核心操作——图的边收缩 “收缩”是比“取子图”更复杂的操作，它不仅能简化图，还能改变图的基本结构。定义：设 e = uv 是图G中的一条边。将边e收缩是指将边e的两个端点u和v 合并成一个新的顶点，我们通常称这个新顶点为 w。同时，删除由此产生的所有重边（如果存在）和自环（连接w和w的边）。操作过程分解：识别目标：选择图G中的一条边e，连接顶点u和v。合并顶点：将u和v“粘合”在一起，视为一个全新的顶点w。处理关联边：原来与u或v相连的其他边（即除了边e本身），现在都变成与这个新顶点w相连。如果原来有某个顶点x同时与u和v相连，那么合并后，x将与w有两条边。根据简单图的标准定义（无重边），我们只保留一条。边e本身在合并后变成了连接w和w的边，即一个自环。根据简单图的标准定义（无自环），我们删除这个自环。得到结果：经过上述操作得到的新图，记作 G/e （读作“G收缩e”）。直观理解：想象边e是一根可以收缩的橡皮筋，你拉着它的两端（顶点u和v）使劲拽，直到它们碰在一起变成一个点。原来连接u或v的线（边）自然就都连到了这个新的点上。例子：假设图G是一个四边形（4个顶点，4条边：AB, BC, CD, DA）。我们收缩边BC。将顶点B和C合并成一个新顶点，叫它X。原来与B相连的边有AB和BC（BC是要被收缩的边），与C相连的边有BC和CD。合并后：边AB现在连接A和X。边CD现在连接D和X。边BC收缩后形成自环，删除。边DA保持不变，连接D和A。最终得到的图G/BC是一个三角形，顶点为A, D, X，边为AX, DX, AD。第3步：广义概念——图的小子式当我们连续进行一系列的子图操作（删除顶点、删除边）和收缩操作时，就引出了一个极其重要的概念—— 图的小子式。定义：如果图H可以通过对图G进行一系列以下的操作而得到，那么称 H 是 G 的一个小子式：删除边。删除顶点（以及与之相连的所有边）。收缩边。关键点：这些操作的顺序可以任意。你可以先删除一些边，再收缩一条边，再删除一个顶点……最终如果能得到H，那么H就是G的小子式。重要性：小子式关系是图论中一个非常重要的偏序关系。它深刻地刻画了图的结构性质。一个著名的例子是库拉托夫斯基定理，它指出：一个图是平面图（可以画在平面上使得边不相交）的充分必要条件是，它既不包含完全图 K₅ 也不包含完全二分图 K₃，₃ 作为其小子式。例子：判断图G（一个立方体的骨架图）是否包含一个三角形（K₃）作为小子式。思路：我们尝试通过操作将G变成一个三角形。操作：我们可以通过收缩立方体上特定的边，将对立的面“压扁”，最终确实可以得到一个三角形。因此，K₃ 是G的一个小子式。反之：一个树形结构（无环）永远无法通过收缩边（不会创造新环）得到一个有环的图，所以树不包含任何环图作为小子式。第4步：总结与联系子图运算（删除顶点/边）和收缩运算是图论中两种基本的、用于从已知图构造新图的工具。子图是通过“做减法”来得到更简单的图，它保留了原图局部的部分结构。收缩是通过“融合”顶点来简化图，它可能改变图的整体连通性等全局性质。小子式概念将这两种操作结合起来，定义了一种更强大的“简化”关系，是现代图结构理论的核心之一，尤其在研究图的平面性、可嵌入性等拓扑性质时至关重要。理解这些运算，为你今后学习更深入的图论主题，如图的不变量（某些参数在收缩操作下的变化）、图的分解理论以及图子式定理（罗伯逊-西摩定理）奠定了坚实的基础。