图的收缩与可平面性 我们来讨论 图的收缩操作 如何影响平面性，以及由此衍生的判定平面性的重要定理。这个概念是理解图的结构与平面性关系的核心。 1. 什么是图的收缩？ 在已讲过的“图的收缩与子图运算”中，我们定义了收缩运算。这里简要回顾： 给定图 \(G\) 和它的一条边 \(e = uv\)， 收缩边 \(e\) 是指将顶点 \(u\) 和 \(v\) 合并成一个新顶点 \(w\)，原来与 \(u\) 或 \(v\) 相连的边改为与 \(w\) 相连（但删除可能因此产生的自环）。 如果 \(H\) 可以通过对 \(G\) 进行一系列边收缩得到，则称 \(H\) 是 \(G\) 的 收缩 （或称 \(G\) 可收缩到 \(H\)）。 收缩不同于删除边或顶点，它减少了顶点数但可能增加其他顶点的度数。 2. 平面图与收缩的关系 关键观察： 如果一个图是平面图，那么对它进行任意边收缩后得到的图仍然是平面图 。 原因直观：在平面嵌入中，将相邻两个顶点“捏合”为一个顶点，不会导致边在平面内交叉（只需局部调整连线）。 因此，平面图类在收缩运算下是 封闭的 。 3. 可平面性的禁用子式刻画 由上述封闭性可得：如果一个图 \(G\) 包含一个 非平面图 的收缩，那么 \(G\) 本身一定是非平面图。 那么反过来问：是否所有非平面图都是因为包含了某个固定的非平面图的收缩？ 经典结论 （Kuratowski 定理，已讲过“图的可平面性与平面图判定”时提到过）： 一个图是可平面的，当且仅当它不包含 \(K_ 5\)（完全图5个顶点）或 \(K_ {3,3}\)（完全二分图两部各3顶点）作为 子式 。 这里“子式”是 图子式 ，指通过删除边/顶点、收缩边所能得到的图。 因此 Kuratowski 定理说： \(K_ 5\) 和 \(K_ {3,3}\) 是两个最小的非平面图，任何非平面图一定包含它们之一的子式 。 其中“包含子式”就包括了“包含作为收缩后得到的图”这种情形。 4. 收缩与可平面性判定的算法意义 由于平面性检测可以在线性时间完成（已讲“图的平面性检测算法”），但 Kuratowski 定理给出了一个结构理由。 当我们怀疑一个图是非平面图时，可以尝试寻找是否能收缩出 \(K_ 5\) 或 \(K_ {3,3}\)。 不过要注意： 收缩边是操作之一，子式还允许删除边和顶点。 如果只允许收缩而不允许删除，则可能得不到 \(K_ 5\) 或 \(K_ {3,3}\)，而是得到它们的细分图？不， 收缩 会减少顶点数，可能会跳过细分结构直接得到目标。但寻找子式一般是收缩与删除混合运用。 5. 收缩临界非平面图 一个概念：如果图 \(G\) 是非平面图，但对任意一条边 \(e\)，收缩 \(e\) 后得到的图却是平面图，则称 \(G\) 是 收缩临界非平面图 。 显然 \(K_ 5\) 和 \(K_ {3,3}\) 是这种图。事实上，它们是仅有的两个边数最少的收缩临界非平面图（不考虑同构）。 这意味着：如果你有一个非平面图，可以通过逐步收缩边，最终得到一个较小的非平面图，直到不能再收缩（否则变平面）为止，这个最终图一定是 \(K_ 5\) 或 \(K_ {3,3}\) 的子式之一。 6. 对偶概念：细分与收缩 在平面性判定中，经常使用“细分”的概念：将一条边中间插入顶点得到更长的路径。 Kuratowski 定理的另一个常见形式是：一个图是非平面图当且仅当它包含 \(K_ 5\) 或 \(K_ {3,3}\) 的 细分 。 收缩 与 细分 在一定程度上互为逆操作：细分是收缩的逆（但需注意收缩会合并顶点，细分是拆分边）。 事实上，包含细分和包含子式在 Kuratowski 定理中等价，因为 \(K_ 5\) 和 \(K_ {3,3}\) 是严格的不允许有度数2顶点的结构。 7. 在图的曲面嵌入中的应用 对更高亏格曲面，也有类似子式刻画：例如，一个图可以嵌入射影平面当且仅当它不包含某个有限禁用子式集合（已讲“图的曲面嵌入”时提过）。 收缩运算 在此类刻画中同样关键，因为曲面嵌入性质在收缩下不一定保持，但“不包含某子式”仍可用于刻画某些曲面的可嵌入性。