图的分数边染色 从经典边染色到分数化的动机 在经典图论中，图的 边染色 是指给每条边分配一种颜色，使得相邻边（即共享公共顶点的边）颜色不同。所需最少颜色数称为 边色数 ，记作 \(\chi'(G)\)。但某些场景（如调度、资源分配）中，允许一条边“分时”使用多种颜色可能更合理，这引出了 分数边染色 的概念：允许将多种颜色“分配”给一条边，但相邻边分配的颜色集合不能有交集，且每条边分配的颜色总量为1。 分数边染色的形式化定义 设 \(G=(V,E)\) 是无向图，\(\mathcal{M}\) 表示 \(G\) 中所有匹配的集合。一个 分数边染色 是对每个匹配 \(M \in \mathcal{M}\) 赋予一个非负权值 \(w_ M\)，使得对每条边 \(e \in E\)，包含 \(e\) 的所有匹配的权值之和为 1，即： \[ \sum_ {M: e \in M} w_ M = 1, \quad \forall e \in E. \] 分数边色数 \(\chi' f(G)\) 定义为所有可行染色方案中，权值总和 \(\sum {M} w_ M\) 的最小值。 分数边色数与多重边染色的等价刻画 \(\chi'_ f(G)\) 也可通过图的 多重边染色 来理解：考虑图 \(G\) 的 \(b\) 倍图 \(bG\)（将每条边复制 \(b\) 份），用整数 \(k\) 种颜色正常边染色 \(bG\)，则平均每条边用 \(k/b\) 种颜色。\(\chi'_ f(G)\) 是所有 \(k/b\) 的下确界，即： \[ \chi' f(G) = \inf {b} \frac{\chi'(bG)}{b}. \] 分数边色数的线性规划模型 分数边染色可建模为线性规划：变量 \(w_ M \ge 0\) 对每个匹配 \(M\)，约束为 \(\sum_ {M: e \in M} w_ M \ge 1\)（每条边至少被匹配覆盖“1”次），目标是最小化 \(\sum_ {M} w_ M\)。其对偶问题是 分数边覆盖 ：对每条边 \(e\) 赋权 \(y_ e \ge 0\)，使得每个匹配中边的权值和不超过 1，目标最大化 \(\sum_ {e} y_ e\)。由线性规划强对偶，二者最优值相等。 分数边色数的基本性质与计算 对任意图 \(G\)，有 \(\chi'_ f(G) \ge \Delta(G)\)（最大度），且 \(\chi'_ f(G) \ge \frac{|E|}{\alpha'(G)}\)，其中 \(\alpha'(G)\) 是最大匹配的边数。 对于二分图，\(\chi'_ f(G) = \Delta(G)\)，且可通过多项式时间计算。 一般图中，\(\chi'_ f(G)\) 可通过椭球法在多项式时间内求解（因线性规划规模虽指数级，但存在多项式时间分离预言机）。 与分数色数的对比 分数边染色是分数顶点染色在线图（line graph）上的推广。图 \(G\) 的分数边色数等于其线图 \(L(G)\) 的分数色数，即 \(\chi'_ f(G) = \chi_ f(L(G))\)。 分数边染色与图的分类结构 对于 Petersen 图，\(\Delta=3\)，但 \(\chi'=4\)，而其分数边色数 \(\chi'_ f = 3\)。 分数边色数满足 \(\chi'_ f(G) \in \mathbb{Q}\)，且对有限图分母至多为 \(|V|\)。 与 图的分数团数 的关系：\(\chi'_ f(G) \ge \omega_ f(G)\)，其中 \(\omega_ f(G)\) 是分数团数。