图的分数着色与分数团 分数着色是图着色问题的推广，它将经典的顶点着色从整数色数扩展到实数范围。为了理解分数着色，我们需要从经典着色出发，逐步引入分数化的思想。 1. 经典顶点着色的回顾 在传统顶点着色中，每个顶点被分配一种颜色，相邻顶点颜色不同。若用 \( k \) 种颜色能完成着色，则称图是 \( k \)-可着色的。图的色数 \(\chi(G)\) 是满足条件的最小整数 \( k \)。 2. 着色的“独立集覆盖”视角 经典着色可以重新表述为：将顶点集划分成若干独立集（集合内顶点互不相邻），每个独立集对应一种颜色。色数 \(\chi(G)\) 即覆盖所有顶点的独立集的最小数量。 3. 分数着色的定义 分数着色放松了对独立集数量的要求：允许每个顶点被多个独立集“覆盖”，但每个顶点被覆盖的总次数相同（通常归一化为1）。具体地： 设 \(\mathcal{I}\) 是图 \(G\) 所有独立集的集合。 对每个独立集 \(I \in \mathcal{I}\)，分配一个非负权重 \(w_ I\)。 要求对每个顶点 \(v\)，包含 \(v\) 的独立集的权重之和至少为 1（即 \(\sum_ {I \ni v} w_ I \geq 1\)）。 分数色数 \(\chi_ f(G)\) 是所有可行权重分配下，权重总和 \(\sum_ {I} w_ I\) 的最小值。 4. 分数着色的线性规划形式 上述定义可写为线性规划问题： \[ \chi_ f(G) = \min \sum_ {I} w_ I \quad \text{s.t.} \quad \forall v \in V(G), \sum_ {I \ni v} w_ I \geq 1, \ w_ I \geq 0. \] 其对偶问题则与分数团相关。 5. 分数团 分数团是团数的分数化推广。团数 \(\omega(G)\) 是图中最大团的顶点数。分数团数 \(\omega_ f(G)\) 定义为： 对每个顶点 \(v\) 分配非负权重 \(x_ v\)，满足团中顶点权重和不超过 1（即对任意团 \(C\)，有 \(\sum_ {v \in C} x_ v \leq 1\)）。 \(\omega_ f(G)\) 是最大化顶点权重和 \(\sum_ {v} x_ v\) 的值。 由线性规划的对偶性，有 \(\omega_ f(G) = \chi_ f(G)\)。 6. 分数着色的等价刻画：\(a:b\)-着色 分数着色也可通过“多色分配”理解： 一个 \(a:b\)-着色是将 \(a\) 种颜色分配给每个顶点，但每个顶点恰好分配 \(b\) 种颜色（颜色子集），且相邻顶点的颜色子集不相交。 分数色数 \(\chi_ f(G) = \inf \{ a/b \mid G \text{ 存在 } a:b\text{-着色} \}\)。 7. 分数着色的性质 对任意图 \(G\)，有 \(\omega(G) \leq \omega_ f(G) = \chi_ f(G) \leq \chi(G)\)。 分数色数可能是无理数（例如，5-环的 \(\chi_ f(C_ 5) = 2.5\)）。 对于完美图（如二部图、弦图），有 \(\chi_ f(G) = \chi(G)\)。 8. 应用与意义 分数着色在调度问题、资源分配中比经典着色更灵活，能建模共享资源的时间分片。它与图的熵、通信复杂度等领域也有深刻联系。