图的收缩与子图运算 1. 基本概念回顾与定义 子图 ：若图H的顶点集和边集分别是图G的顶点集和边集的子集，则称H是G的子图。 生成子图 ：若H是G的子图且包含G的所有顶点，则H是G的生成子图。 收缩运算 ：将图G中的一条边e=(u,v)收缩是指将边e删除，并将顶点u和v合并为一个新顶点w，原与u或v相连的边改为与w相连（若合并后产生自环则删除自环）。收缩操作后得到的图记为G/e。 2. 收缩运算的数学表示与性质 设G=(V,E)，收缩边e=(u,v)后： 新顶点集V' = (V \ {u,v}) ∪ {w}。 新边集E'由E中非e的边修改而来：每条与u或v关联的边改为关联w（保留重边，删除自环）。 性质 ： 收缩操作减少一个顶点和至少一条边（若e是重边则删除多条边）。 若G是连通图，则G/e仍连通。 收缩运算改变图的拓扑结构，可能影响平面性、着色数等参数。 3. 子图运算的分类 顶点删除 ：删除顶点v及其关联的所有边，记为G-v。 边删除 ：删除边e但不删除顶点，记为G-e。 边收缩 ：如前所述，记为G/e。 子式 ：若图H可通过对G进行一系列边删除、顶点删除和边收缩得到，则称H是G的子式。子式关系是图论中的核心概念（如Wagner定理、Robertson-Seymour定理）。 4. 收缩运算与图参数的关系 色数 ：收缩边可能降低或保持色数，例如若e连接两个不同颜色的顶点，收缩后色数可能减少。事实上，有等式χ(G) ≤ χ(G/e) + 1。 连通度 ：收缩边可能增加顶点连通度，例如收缩树中的边会减少顶点数但保持连通性。 生成树计数 ：根据收缩-删除定理（见后），收缩运算与生成树数量直接相关。 5. 收缩-删除定理与应用 定理内容 ：对图G的任意边e（非自环），其生成树数目τ(G)满足递推关系：τ(G) = τ(G-e) + τ(G/e)。 G-e表示删除e后的图，G/e表示收缩e后的图。 证明思路 ：将生成树分为两类：不包含e的生成树（对应G-e的生成树）和包含e的生成树（对应G/e的生成树，因e已固定需收缩）。 应用 ：该定理是计算生成树数量的递归工具，并可推广到Tutte多项式等不变量。 6. 子式与结构图论 子式闭包 ：若图族F在子式运算下封闭（即G∈F且H是G的子式则H∈F），则F可由有限个禁用子式刻画（Robertson-Seymour定理）。 例子 ： 平面图的禁用子式是K₅和K₃,₃（Kuratowski定理的推广）。 可嵌入曲面的图族也有有限禁用子式集。 7. 算法与复杂性 子式检测 ：判断图H是否是G的子式是NP-难问题，但对固定H存在多项式时间算法（Robertson-Seymour定理的算法后果）。 收缩运算的算法实现 ：通过合并顶点邻接表、更新边信息来实现，时间复杂度为O(|E|)。 8. 扩展方向 超图收缩 ：将边收缩推广到超边，合并超边关联的所有顶点。 有向图收缩 ：收缩有向边时需考虑方向性，可能产生多重边或新结构。 张量网络收缩 ：在图论基础上，收缩运算在量子计算和张量网络中有物理应用。 通过以上步骤，收缩与子图运算的核心思想、性质及与其他理论的联系得以系统呈现。下一步可探讨具体子式禁用手法或Tutte多项式等深入主题。