图的分数路径覆盖 我们先从一个基本概念“路径覆盖”开始。在给定的图 \( G = (V, E) \) 中，一条“路径”是顶点序列 \( v_ 1, v_ 2, \ldots, v_ k \)，其中相邻顶点有边相连。一个“路径覆盖”是指一组（顶点不相交的）路径，使得图的每个顶点恰好出现在其中一条路径中。路径覆盖的目标通常是用尽可能少的路径覆盖所有顶点，这个最少的数量称为图的“路径覆盖数”。 但现实中的优化问题有时允许资源“分割”使用，这就引出了“分数”版本。在“分数路径覆盖”中，我们不再要求每个顶点完全属于一条路径，而是允许将顶点“拆分”，让不同的路径各“覆盖”它的一部分，但覆盖的总和为1。数学上，这通过给每条可能的路径分配一个非负权值来实现。 设 \( \mathcal{P} \) 为图 \( G \) 中所有可能的路径的集合。一个“分数路径覆盖”是一个函数 \( f: \mathcal{P} \rightarrow [ 0, 1] \)，满足对每个顶点 \( v \in V \)，所有经过 \( v \) 的路径的权值之和至少为1：\(\sum_ {P \in \mathcal{P}: v \in P} f(P) \geq 1\)。分数路径覆盖的“大小”是所有路径的权值之和：\(\sum_ {P \in \mathcal{P}} f(P)\)。“分数路径覆盖数” \( \mathrm{fpc}(G) \) 就是所有分数路径覆盖的大小的最小值。 为什么要研究分数版本？因为它常常等价于一个线性规划问题，比整数版本更容易分析和计算，并且为整数路径覆盖数提供下界。 接下来，我们探讨分数路径覆盖与图论中另一个经典概念“点不交路径覆盖”的对偶关系。根据线性规划对偶定理，分数路径覆盖问题的对偶问题涉及给每个顶点分配一个非负权值 \( w(v) \)，使得对任意一条路径 \( P \)，其顶点权值之和不超过1：\(\sum_ {v \in P} w(v) \leq 1\)。对偶问题的目标是最大化所有顶点权值之和 \(\sum_ {v \in V} w(v)\)。这个对偶解可以视为一种“分数独立集”在路径上的限制形式。 有趣的是，在某些特殊图类中，分数路径覆盖数等于整数路径覆盖数。例如，在有向无环图中，根据迪尔沃思定理的推广，最小路径覆盖数等于 \( n - \alpha'(G) \)，其中 \( \alpha'(G) \) 是最大匹配的大小（通过拆点二分图转化）。其分数版本的最优值可以通过线性规划松弛得到，并且由于约束矩阵的全单模性，最优解自动为整数，因此分数值与整数值相等。 但对于一般有向图，情况更复杂。分数路径覆盖与“圈覆盖”有关。实际上，任何分数路径覆盖可以转化为一个“循环覆盖”，其中允许包含圈，然后通过分解定理将其分解为路径和圈的凸组合。这揭示了分数版本与图的有向循环空间结构的联系。 在算法层面，分数路径覆盖可以表述为网络流问题。我们构造一个流网络：将每个顶点拆分为入点和出点，从源点向所有入点连容量1的边，从所有出点向汇点连容量1的边，对于图中的每条有向边 \( (u,v) \)，从 \( u \) 的出点向 \( v \) 的入点连容量1的边。然后，求解最大流。最大流值就是最小路径覆盖的顶点数？不完全是。在整数版本中，最小路径覆盖数等于 \( n - \text{最大流值} \)。在分数版本中，只需允许流是分数，对应的线性规划可以直接求解，其最优值 \( \mathrm{fpc}(G) \) 可以通过多项式时间的线性规划算法得到。 最后，分数路径覆盖与图的“路径图子式”和“树深”等参数也有深刻联系。例如，图的“分数顶点不交路径覆盖数”可以作为图宽度参数的一个度量，用于算法设计和结构图论中。此外，在并发系统调度和资源分配问题中，分数路径覆盖提供了比整数版本更灵活的建模工具，允许任务被部分分配到多条执行路径上，从而优化整体效率。