图的分数染色 首先，分数染色是图论中经典顶点着色问题的推广。在传统顶点着色中，每个顶点被分配一种颜色，相邻顶点颜色不同，目标是使用最少的颜色数（即色数χ(G)）。分数染色则允许一个顶点拥有多种颜色的"分数"，通过线性规划松弛扩展了这一概念。 具体来说，我们考虑颜色集上的非负权值分配。设所有独立集（图中两两不相邻的顶点集合）的集合为ℐ。对每个独立集I∈ℐ，赋予一个非负权值x_ I。分数着色要求对每个顶点v，包含v的所有独立集的权值之和至少为1。分数色数χ_ f(G)定义为所有独立集权值之和的最小值，即最小化∑x_ I。 例如，奇环图C_ 5的色数为3，但分数色数仅为2.5。这是因为我们可以给五个独立集（每条边对应的两个顶点）各赋权0.5，使每个顶点被覆盖1.5次，总权值为2.5。 分数色数也可通过考虑颜色多重集来理解。若每个顶点分配k种颜色（允许重复），要求相邻顶点颜色集不相交，则分数色数是当k趋于无穷时，所需最少颜色数除以k的极限。这种定义与线性规划形式等价。 分数染色与图论其他领域联系紧密。它等价于分数团覆盖的对偶问题，且与图的Hajós构造、完美图理论相关。此外，分数色数可通过线性规划对偶性转化为分数团数，即图中最大团大小的分数推广。 计算分数色数是多项式时间可解的，因为可转化为线性规划。然而，寻找紧凑的分数着色表示仍是研究课题。分数染色在调度理论、资源分配等实际问题中具有应用，提供了比经典着色更灵活的建模工具。