图的分解 图的分解是图论中研究如何将一个给定的图分割成若干满足特定条件的子图的理论。这些子图通常具有较简单的结构，从而有助于分析原图的性质。 基本概念 定义 ：一个图 \( G \) 的 分解 是指将其边集划分成若干子集 \( E_ 1, E_ 2, ..., E_ k \)，使得每个子集 \( E_ i \) 所诱导的 生成子图 \( G_ i \)（即顶点集仍为 \( G \) 的全部顶点）都具有某种期望的性质。 核心思想 ：图的分解旨在“分而治之”，通过研究一系列结构更简单、更易于处理的子图来理解复杂原图的整体性质。最常见的分解是要求每个子图都是一类特定的图，例如完全图、路径、圈、匹配或森林。 常见分解类型 图的分解可以根据对子图的要求分为多种类型，以下是几种经典的分解： 森林分解 ：将图 \( G \) 分解成若干个边不相交的 森林 （即无环图）的并。一个重要的结论是，任何图 \( G \) 的 边色数 等于其 色指数 ，根据维津定理，它等于 \( G \) 的 最大度 \( \Delta(G) \) 或 \( \Delta(G) + 1 \)。将图 \( G \) 的边集用 \( \Delta(G) \) 种颜色进行正常边着色，实际上就是将 \( G \) 分解成了 \( \Delta(G) \) 个 匹配 （每个匹配是一种颜色的边集），而匹配是一种特殊的森林。更一般地， 纳什-威廉姆斯定理 指出，将一个图分解成至少 \( k \) 个森林是可能的，当且仅当对于图的每一个非空顶点子集，其诱导子图的边数不超过 \( k(|S|-1) \)。 路径分解 ：将图 \( G \) 的边集分解成若干条 路径 ，使得每条边恰好出现在一条路径中。一个著名的问题是 图的路覆盖 问题，即寻找最少数量的顶点不相交（或边不相交）的路径，使得它们覆盖图的所有顶点（或边）。这与图的奇度数顶点数量密切相关。 圈分解 ：将图 \( G \) 的边集分解成若干个 圈 （循环）。一个重要的必要条件是图 \( G \) 中每个顶点的度数为偶数（即 \( G \) 是欧拉图）。对于连通图，这个条件（每个顶点度为偶数）同时也是该图可进行圈分解的充分条件。 分解的应用与扩展 图的分解理论不仅具有理论价值，在实际中也有广泛应用，并衍生出更深入的概念。 图的自同构群 ：图的分解，特别是那些具有对称性的分解，与图的 自同构群 （所有保持图结构的顶点置换构成的群）的研究密切相关。一个对称的分解可能在该群的作用下保持不变。 设计理论 ：图分解是组合设计理论的基石。例如，一个 斯坦纳三元系 可以看作是完全图 \( K_ n \) 的一个分解，其中每个子图都是三角形（即 \( K_ 3 \)）。更一般地， 区组设计 中的许多概念都可以用完全图的特定子图分解来表述。 树分解 ：这是图分解的一个非常重要的现代扩展，但它分解的不是边集，而是整个图的结构。 树分解 将一个图“嵌入”到一个树状结构中，其“宽度”（即树节点所包含的原图顶点集的大小的最大值减一）定义了图的 树宽 。树宽是衡量一个图与树的“相似程度”的指标，在算法设计和图的结构性质研究中至关重要，特别是对于 NP难 问题，许多问题在树宽有界的图上存在高效算法。