图的星分解与星覆盖 我们先从“星”这个基本图结构开始。星（star）是一种特殊的树，由一个中心顶点和若干（可以为0）个只与中心相连的叶子顶点组成，记为 \( K_ {1, m} \)。它是结构最简单的树之一。 星分解 定义 ：图 \( G \) 的一个星分解，是指将 \( G \) 的顶点集 \( V(G) \) 划分成若干个子集，使得每个子集在 \( G \) 中诱导出的子图是一个星。注意，这里每个子集内部的边必须恰好构成一个星（包括孤立的单点星 \( K_ {1,0} \) ），不同子集之间的边是允许存在的，但分解只关心顶点集的划分以及每个部分自身的星结构。 目的与背景 ：星分解是图的结构分解的一种。它试图用非常简单的子图（星）来“覆盖”原图的所有顶点，同时要求覆盖是“不相交”的（即顶点划分）。这种分解在算法设计，特别是针对某些图类（如弦图、区间图）的动态规划中可能有应用，因为星的结构极其简单，易于处理。 星覆盖 定义 ：图 \( G \) 的一个星覆盖，是指一个星的集合 \(\{ S_ 1, S_ 2, ..., S_ k \}\)，使得 \( G \) 的每条边都至少被包含在某一个星 \( S_ i \) 的边集中。这里，\( S_ i \) 是 \( G \) 的一个子图，且同构于一个星。与分解不同，星覆盖允许不同的星共享顶点和边，目标是用尽可能少的星来覆盖所有边。 参数 ：图 \( G \) 的 星覆盖数 ，记作 \( \sigma(G) \)，是指覆盖 \( G \) 所有边所需的最少星的数量。这是一个经典的图覆盖参数。 基本性质 ：寻找最小星覆盖等价于寻找一个顶点子集 \( C \)，使得 \( G \) 的每条边都至少有一个端点与 \( C \) 中的某个顶点相关联（但要求更严格：每条边必须整个位于某个以 \( C \) 中顶点为中心的星内）。这与控制集、边覆盖等概念有关联但不同。 星分解与星覆盖的联系与区别 核心区别 ： 分解 是顶点集的 划分 ，每个部分形成星； 覆盖 是边集的 覆盖 （允许重叠），用星来实现。前者是“顶点不相交”的，后者是“可以相交”的。 一个联系 ：任何星分解自然地导出一个星覆盖（将分解中的每个星本身视为覆盖中的一个元素），但反之不然，因为覆盖中的星可能相互重叠。 计算复杂性 判定一个图是否存在顶点集划分为给定数目的星（即星分解）通常是NP困难的，即使在特殊图类中也可能很难。 计算星覆盖数 \( \sigma(G) \) 也是NP困难的。寻找最小星覆盖可以转化为一个集合覆盖问题实例。 与支配集问题的深刻联系 星覆盖可以重新表述如下：在 \( G \) 中找到一个顶点集合 \( D \) （作为星中心的候选），并对 \( D \) 中每个顶点 \( v \) 分配一个星（以 \( v \) 为中心，包含其所有或部分邻居），使得这些星的边并集等于 \( E(G) \)。 这引出了一个 有向星覆盖 的变体：为每条边 \( uv \) 指定一个方向，指向其所属星的中心。那么，所有指向中心的边的集合，就构成了一个 入分支 （in-branching）的森林。研究最小星覆盖与图的有向性质（如最小入分支森林）之间的联系，是一个有趣的方向。 在参数复杂性中的应用 星覆盖数和星分解的存在性是研究图的结构参数（如树宽、团宽）的有用工具。例如，如果一个图具有有界的星覆盖数，可能意味着它具有良好的结构性质，可以设计高效的固定参数可解算法来解决某些NP难问题。 星分解本身作为一种简单的分解，可以作为更复杂分解（如树分解）的初步步骤或特例进行研究。 总结： 星分解 关注如何将图的顶点 划分 成一个个结构简单的星，而 星覆盖 则关注如何用最少的、可以重叠的星来 覆盖 图的所有边。两者都利用“星”这一基本构件来简化对复杂图结构的分析和算法处理，并与支配、定向等经典问题紧密相连，在算法图论和结构图论中占有一席之地。