图的覆盖问题 第一步：基本概念引入 图的覆盖问题研究如何用特定结构的子集"覆盖"图的所有边或顶点。设图G=(V,E)，一个边覆盖是边集E的子集C⊆E，使得G的每个顶点都至少与C中的一条边关联。类似地，点覆盖是顶点集V的子集D⊆V，使得G的每条边都至少与D中的一个顶点关联。覆盖问题的目标是寻找规模最小的覆盖集。 第二步：边覆盖与点覆盖的关联 边覆盖与点覆盖存在对偶关系。对于无孤立点的图，最小边覆盖大小α'(G)与最大匹配大小β(G)满足α'(G)+β(G)=|V|。这是因为从最大匹配出发，对每个未匹配顶点添加一条关联边即可构造边覆盖。点覆盖与最大匹配则有König定理：在二分图中，最小点覆盖大小等于最大匹配大小。 第三步：覆盖的复杂性分类 最小点覆盖是NP难问题，但在二分图等特殊图类中存在多项式算法。边覆盖问题可转化为最大匹配问题，存在多项式时间解法。覆盖问题可扩展为加权版本，其中每个顶点/边有权重，目标是最小化覆盖集的总权重。 第四步：覆盖与支配集的区别 需区分覆盖与支配集：点覆盖要求覆盖所有边（边至少一端在集合中），而支配集要求所有不在集合的顶点都与集合相邻。覆盖问题也可推广到超图，其中超边覆盖需包含每个顶点的超边集合。 第五步：算法与应用 贪心算法可近似最小点覆盖（近似比O(log n)），而带权匹配算法可精确求解边覆盖。覆盖问题在网络监控、电路设计等领域有应用，如选择最少的传感器覆盖所有网络连接。