图的分数团
字数 1028 2025-12-12 18:36:24

图的分数团

我们先从团的概念开始。团是图中的一个顶点子集，其中任意两个顶点都相邻（即两两之间有边连接）。一个图的最大团的大小称为团数。分数团是团概念的推广，它在组合优化、信息论和通信网络中有重要应用。

  1. 团与独立集
    团与独立集是互补概念：一个图 G 的团对应其补图 G̅ 中的一个独立集。因此，团数等于补图的独立数。

  2. 整数线性规划刻画
    对于图 G=(V,E)，定义变量 xᵢ 表示顶点 i 是否属于团（1 是，0 否）。则最大团问题可表示为：

    • 最大化 Σ xᵢ
    • 约束：对于每条非边 (i,j)∉E，有 xᵢ + xⱼ ≤ 1
    • xᵢ ∈ {0,1}
      这是 NP 难的。

  3. 分数松弛
    将 xᵢ ∈ {0,1} 松弛为 xᵢ ≥ 0，即允许变量取非负实数。此时得到分数团问题的最优解称为分数团数，记作 ω_f(G)。由于约束矩阵是全单模的吗？不，一般不是，所以分数解可能严格大于整数解。

  4. 线性规划对偶
    分数团线性规划的对偶问题是分数着色问题：用最少的“分数颜色”分配非负权值给所有团，使得每个顶点被覆盖的总权值至少为 1。分数团数等于分数色数，即 ω_f(G) = χ_f(G)。

  5. 例子：奇圈 C₅
    对 5 个顶点的奇圈 C₅，最大团大小为 2（因为无三角形）。但分数团数可计算如下：
    令所有 xᵢ = 1/2，则对任意非相邻顶点，1/2 + 1/2 = 1 ≤ 1 成立。
    目标函数和 = 5/2 = 2.5，可证明这就是最优解，因此 ω_f(C₅) = 2.5。

  6. 计算与性质
    分数团数可通过线性规划在多项式时间内计算（尽管变量数可能指数级，但可用分离Oracle配合椭球法）。
    显然有 ω(G) ≤ ω_f(G) ≤ χ_f(G) ≤ χ(G)。
    对于完美图，等号成立：ω = χ，且也等于分数版本。

  7. 与稳定集多项式的联系
    考虑图的稳定集多项式（独立集生成函数），分数团与某些解析延拓有关。在某些模型中（如通信网络的最大吞吐量），分数团表示允许时间共享时的最大并发传输组数。

  8. 近似算法与可计算性
    近似最大团是困难的，但分数团给出了一个上界，并可用于分支定界法。此外，分数团可用于设计半定规划松弛，例如在著名的 Lovász ϑ 函数中，有 ω_f(G) ≤ ϑ(G̅) ≤ χ(G)。

  9. 应用举例
    在无线网络中，若顶点表示通信节点，边表示干扰，则一个团中的节点不能同时传输。分数团数则表示在允许时间分割时，最大可能的并发传输容量。

图的分数团 我们先从团的概念开始。团是图中的一个顶点子集，其中任意两个顶点都相邻（即两两之间有边连接）。一个图的最大团的大小称为团数。分数团是团概念的推广，它在组合优化、信息论和通信网络中有重要应用。 团与独立集 团与独立集是互补概念：一个图 G 的团对应其补图 G̅ 中的一个独立集。因此，团数等于补图的独立数。 整数线性规划刻画 对于图 G=(V,E)，定义变量 xᵢ 表示顶点 i 是否属于团（1 是，0 否）。则最大团问题可表示为： 最大化 Σ xᵢ 约束：对于每条非边 (i,j)∉E，有 xᵢ + xⱼ ≤ 1 xᵢ ∈ {0,1} 这是 NP 难的。 分数松弛 将 xᵢ ∈ {0,1} 松弛为 xᵢ ≥ 0，即允许变量取非负实数。此时得到分数团问题的最优解称为分数团数，记作 ω_ f(G)。由于约束矩阵是全单模的吗？不，一般不是，所以分数解可能严格大于整数解。 线性规划对偶 分数团线性规划的对偶问题是分数着色问题：用最少的“分数颜色”分配非负权值给所有团，使得每个顶点被覆盖的总权值至少为 1。分数团数等于分数色数，即 ω_ f(G) = χ_ f(G)。 例子：奇圈 C₅ 对 5 个顶点的奇圈 C₅，最大团大小为 2（因为无三角形）。但分数团数可计算如下： 令所有 xᵢ = 1/2，则对任意非相邻顶点，1/2 + 1/2 = 1 ≤ 1 成立。 目标函数和 = 5/2 = 2.5，可证明这就是最优解，因此 ω_ f(C₅) = 2.5。 计算与性质 分数团数可通过线性规划在多项式时间内计算（尽管变量数可能指数级，但可用分离Oracle配合椭球法）。 显然有 ω(G) ≤ ω_ f(G) ≤ χ_ f(G) ≤ χ(G)。 对于完美图，等号成立：ω = χ，且也等于分数版本。 与稳定集多项式的联系 考虑图的稳定集多项式（独立集生成函数），分数团与某些解析延拓有关。在某些模型中（如通信网络的最大吞吐量），分数团表示允许时间共享时的最大并发传输组数。 近似算法与可计算性 近似最大团是困难的，但分数团给出了一个上界，并可用于分支定界法。此外，分数团可用于设计半定规划松弛，例如在著名的 Lovász ϑ 函数中，有 ω_ f(G) ≤ ϑ(G̅) ≤ χ(G)。 应用举例 在无线网络中，若顶点表示通信节点，边表示干扰，则一个团中的节点不能同时传输。分数团数则表示在允许时间分割时，最大可能的并发传输容量。