团多项式归约到顶点覆盖
深度讲解：团多项式归约到顶点覆盖
核心结论：可在多项式时间把任意团问题实例转化为顶点覆盖实例；原图存在 k - 团 ⇔ 原图的补图存在∣V∣−k|V|-k∣V∣−k大小的顶点覆盖；由此证明顶点覆盖是 NP 完全问题。
一、CLIQUE≤PVertex Cover\boldsymbol{CLIQUE \le_P Vertex\ Cover}CLIQUE≤PVertexCover
团（CLIQUE）问题可以多项式时间 Karp 归约到顶点覆盖（Vertex Cover）问题
符号≤P\boldsymbol{\le_P}≤P释义（沿用 NP 归约定义）
多项式算法输入一组团问题⟨G,k⟩\langle G,k \rangle⟨G,k⟩，输出一组顶点覆盖问题⟨Gˉ,k′⟩\langle \bar G, k' \rangle⟨Gˉ,k′⟩；
原问题GGG有kkk阶团⟺ \iff⟺构造后的Gˉ\bar GGˉ存在k′k'k′大小的顶点覆盖；
推论：若顶点覆盖能多项式求解，则团问题也能多项式求解。
二、Vertex Cover（顶点覆盖）问题定义 + 概念
顶点覆盖问题
输入：给定无向图G=(V,E)G=(V,E)G=(V,E)（VVV顶点集，EEE边集）、正整数kkk
输出：是否能选出顶点子集S⊆VS\subseteq VS⊆V，满足：∣S∣=k|S|=k∣S∣=k，图中任意一条边的两个端点里，至少有一个顶点落在集合SSS中？
通俗理解
集合SSS叫做k - 顶点覆盖：SSS里的顶点 “覆盖住所有边”，每条边至少一头被选中。
例图：顶点1,4{1,4}1,4就是一个合法顶点覆盖：所有边(1-2、1-3、1-4、1-6、4-3、4-5)(1\text{-}2、1\text{-}3、1\text{-}4、1\text{-}6、4\text{-}3、4\text{-}5)(1-2、1-3、1-4、1-6、4-3、4-5)都包含 1 或 4。
补充：判定类问题，给定候选集合SSS，逐条遍历边即可验证是否是点覆盖，因此Vertex Cover ∈ NP。
三、归约构造：CLIQUE → Vertex Cover 定理与双向证明
定理：CLIQUE≤PVertexCover\boldsymbol{CLIQUE \le_P Vertex Cover}CLIQUE≤PVertexCover
归约构造规则（灵魂：补图变换）
给定任意团问题实例：原图G=(V,E)G=(V,E)G=(V,E)、目标团规模kkk
构造补图Gˉ=(V,Eˉ)\boldsymbol{\bar G=(V,\bar E)}Gˉ=(V,Eˉ)：顶点集合和原图完全一致；边取反：
原图GGG两点之间没有边⇒ 补图Gˉ\bar GGˉ两点连边；
原图GGG两点之间有边⇒ 补图Gˉ\bar GGˉ两点无边；
构造顶点覆盖参数：k′=∣V∣−kk' = |V|-kk′=∣V∣−k（总顶点数量减去团目标值kkk）。
核心等价命题
G中存在大小为k的团 ⟺ Gˉ中存在大小为k′=∣V∣−k的顶点覆盖\boldsymbol{G中存在大小为k的团 \iff \bar G中存在大小为k'=|V|-k的顶点覆盖}G中存在大小为k的团⟺Gˉ中存在大小为k′=∣V∣−k的顶点覆盖
方向 1：正向推导⇒\boldsymbol{\Rightarrow}⇒：GGG有kkk阶团⇒Gˉ\Rightarrow \bar G⇒Gˉ存在k′k'k′顶点覆盖
已知：V′⊆VV'\subseteq VV′⊆V是GGG里大小为kkk的团；求证：S=V−V′S=V-V'S=V−V′是Gˉ\bar GGˉ的顶点覆盖，∣S∣=∣V∣−k=k′|S|=|V|-k=k'∣S∣=∣V∣−k=k′
V′V'V′是GGG的团：V′V'V′内部任意两个顶点在原图GGG中必有边相连；
任取补图Gˉ\bar GGˉ里任意一条边(u,v)∈Eˉ(u,v)\in \bar E(u,v)∈Eˉ：由补图定义，(u,v)∉E(u,v)\notin E(u,v)∈/E（原图GGG没有这条边）；
反证：若u,vu,vu,v全都属于V′V'V′，因为V′V'V′是团，u,vu,vu,v在GGG一定有边，和(u,v)∉E(u,v)\notin E(u,v)∈/E矛盾；
⇒u、v\Rightarrow u、v⇒u、v至少一个不在V′V'V′，也就是至少一个在S=V−V′S=V-V'S=V−V′；根据顶点覆盖定义：Gˉ\bar GGˉ每条边至少一个端点在SSS，因此SSS是Gˉ\bar GGˉ的顶点覆盖，∣S∣=∣V∣−k|S|=|V|-k∣S∣=∣V∣−k。
通俗：团的补集 = 补图的顶点覆盖。
方向 2：反向推导⇐\boldsymbol{\Leftarrow}⇐：Gˉ\bar GGˉ有k′k'k′顶点覆盖⇒G\Rightarrow G⇒G存在kkk阶团
已知：V′⊆VV'\subseteq VV′⊆V是Gˉ\bar GGˉ的顶点覆盖，∣V′∣=∣V∣−k|V'|=|V|-k∣V′∣=∣V∣−k；求证：S=V−V′S=V-V'S=V−V′是GGG中大小为kkk的团
∣S∣=∣V∣−∣V′∣=k|S|=|V|-|V'|=k∣S∣=∣V∣−∣V′∣=k，只需证明：SSS中任意两点在原图GGG中必有边；
任取SSS中两点u、vu、vu、v，反证：若u、vu、vu、v在原图GGG没有边，则根据补图定义：(u,v)∈Eˉ(u,v)\in \bar E(u,v)∈Eˉ（补图里存在这条边）；
V′V'V′是Gˉ\bar GGˉ的顶点覆盖，边(u,v)(u,v)(u,v)至少一个端点在V′V'V′，但u、v∈S=V−V′u、v\in S=V-V'u、v∈S=V−V′（都不在V′V'V′），出现矛盾；
⇒u、v\Rightarrow u、v⇒u、v在原图GGG一定有边；SSS内所有点两两互连，因此SSS是GGG的kkk阶团。
通俗：补图顶点覆盖的补集 = 原图的团。
四、复杂度与 NP 完全结论
多项式归约：构造补图仅需要遍历全部顶点对，时间复杂度O(∣V∣2)O(|V|^2)O(∣V∣2)，属于多项式运算，满足≤P\le_P≤P归约要求；
NP 完全推导：
CLIQUE 是 NP 完全问题，且CLIQUE≤PVertex Cover\text{CLIQUE}\le_P \text{Vertex Cover}CLIQUE≤PVertex Cover；
Vertex Cover 本身属于 NP；
⇒顶点覆盖（VertexCover）是NP完全问题\boldsymbol{\Rightarrow 顶点覆盖（Vertex Cover）是NP完全问题}⇒顶点覆盖（VertexCover）是NP完全问题。
五、核心对偶巧思总结
团 ↔ 顶点覆盖在补图下对偶：
原图的团 → 它的补集是补图的点覆盖；
补图的点覆盖 → 它的补集是原图的团；这个变换是 NP 归约经典构造，承接3SAT≤PCLIQUE3SAT\le_P CLIQUE3SAT≤PCLIQUE，形成链条：
3SAT≤PCLIQUE≤PVertexCover\boldsymbol{3SAT\le_P CLIQUE \le_P Vertex Cover}3SAT≤PCLIQUE≤PVertexCover
3SAT、团、顶点覆盖三者全是 NP 完全问题，计算难度等价。