图的分数着色 图的分数着色是图着色问题的一个自然推广，它将经典的顶点着色概念从整数域扩展到了有理数域。为了理解这个概念，我们需要从经典着色出发，逐步引入分数化的思想。 第一步：回顾经典顶点着色 在图论中，一个（正常）k-顶点着色是指将图G的每个顶点分配k种颜色之一，使得任何相邻的两个顶点（即由一条边连接的顶点）颜色不同。能够对图G进行正常着色的最小颜色数k，称为图G的色数，记作χ(G)。 第二步：引入集合着色概念 为了推广到分数着色，我们首先定义一个更一般的概念：b-重着色。设b是一个正整数。图G的一个b-重着色是指对每个顶点v分配一个大小为b的颜色集合f(v)，并且要求对于任意相邻的两个顶点u和v，它们的颜色集合不相交，即f(u) ∩ f(v) = ∅。这相当于说，每个“颜色类”（由所有包含某种颜色的顶点组成的集合）必须是一个独立集（即集合内任意两点不相邻）。一个b-重着色所使用的总颜色种数，就是所有顶点颜色集合的并集的大小。 第三步：定义分数色数 现在，我们考虑“性价比”：如果我们使用总共c种颜色，完成了对图G的一个b-重着色，那么平均每个顶点“消耗”了 c/b 种颜色。图G的分数色数，记作χ_ f(G)，定义为所有满足上述条件的比值 c/b 的下确界（即最大下界）： χ_ f(G) = inf { c/b | 存在一个使用c种颜色的b-重着色 }。 由于c和b都是正整数，这个下确界实际上是一个有理数。分数色数χ_ f(G)永远不会超过经典色数χ(G)，因为一个经典的k-着色等价于一个b=1, c=k的b-重着色，此时c/b = k。 第四步：分数色数的线性规划刻画 分数色数有一个非常优雅且强大的等价定义，它通过线性规划来描述。考虑图G的所有独立集（包含任意数量的顶点）。我们为每个独立集I分配一个非负的权值w_ I。我们的目标是：找到一组权值{w_ I}，使得对于图G的每一个顶点v，所有包含v的独立集的权值之和至少为1（即 ∑_ {I: v∈I} w_ I ≥ 1）。同时，我们希望所有独立集的权值之和（∑_ I w_ I）尽可能小。这个和的最小值就是图G的分数色数χ_ f(G)。这个定义的直观解释是：我们将“颜色”看作独立的“资源块”，每个顶点需要获得总量为1的资源，这些资源只能来自包含它的独立集。最小总资源量就是分数色数。这个线性规划的对偶问题则对应于分数团数。 第五步：分数色数与分数团数的关系 根据线性规划的对偶定理，分数色数χ_ f(G)等于分数团数ω_ f(G)。分数团数ω_ f(G)是经典团数ω(G)（最大完全子图的大小）的分数化推广。其定义是：找到一组非负权值{w_ v}分配给每个顶点v，使得图G中任意一个独立集（即团在补图中的对应概念）中所有顶点的权值之和不超过1，同时最大化所有顶点权值之和（∑_ v w_ v）。这个最大值就是ω_ f(G)。χ_ f(G) = ω_ f(G) 是图论中一个深刻而优美的对偶性结果。 第六步：分数色数的性质与计算 分数色数具有许多良好的性质。例如，对于任意图G，有 ω(G) ≤ ω_ f(G) = χ_ f(G) ≤ χ(G)。对于二分图，χ_ f(G) = χ(G) = 2。对于奇圈C_ {2n+1}，其经典色数为3，但其分数色数为2 + 1/n。当n趋于无穷大时，分数色数趋于2，这表明分数着色能更精细地区分图的“可着色性”。然而，计算一个一般图的分数色数是NP-难的，但对于某些具有特定结构的图类（如完美图），存在多项式时间算法。 总结来说，图的分数着色通过允许顶点拥有颜色集合并将问题有理数化，提供了一个比经典着色更精细、更强大的工具，用于分析图的结构性质，并与线性规划、对偶理论等领域建立了紧密联系。