图的分数支配函数与分数支配数
我将从基本定义出发，逐步介绍分数支配函数、分数支配数，以及相关的性质与算法。
1. 基本背景：支配集与整数支配数
在图 \(G = (V, E)\) 中，一个顶点集合 \(D \subseteq V\) 称为支配集，如果 \(V \setminus D\) 中的每个顶点至少与 \(D\) 中的一个顶点相邻。
整数支配数 \(\gamma(G)\) 是最小支配集的大小。
在整数支配中，每个顶点要么完全属于支配集（赋权值 1），要么完全不属于（赋权值 0）。
2. 分数支配函数的定义
分数支配是整数支配的线性规划松弛形式。
一个分数支配函数是一个映射 \(f: V \to [0, 1]\)，满足对每个顶点 \(v \in V\)：
\[f(N[v]) \ge 1 \]
其中 \(N[v] = \{v\} \cup \{ u \in V \mid uv \in E \}\) 是 \(v\) 的闭邻域，且 \(f(N[v]) = \sum_{u \in N[v]} f(u)\)。
换句话说，每个顶点及其所有邻居的函数值之和至少为 1。
3. 分数支配数
分数支配数 \(\gamma_f(G)\) 定义为所有分数支配函数 \(f\) 的最小总权值：
\[\gamma_f(G) = \min \left\{ \sum_{v \in V} f(v) \;\middle|\; f \text{ 是分数支配函数} \right\}. \]
由于允许权值取 0 到 1 之间的实数，\(\gamma_f(G) \le \gamma(G)\)。
4. 线性规划模型
分数支配数可通过线性规划求解：
\[\begin{aligned} \min &\quad \sum_{v \in V} f(v) \\ \text{s.t.} &\quad \sum_{u \in N[v]} f(u) \ge 1 \quad \forall v \in V, \\ &\quad f(v) \ge 0 \quad \forall v \in V. \end{aligned} \]
其对偶线性规划为：
\[\begin{aligned} \max &\quad \sum_{v \in V} g(v) \\ \text{s.t.} &\quad \sum_{u \in N[v]} g(u) \le 1 \quad \forall v \in V, \\ &\quad g(v) \ge 0 \quad \forall v \in V. \end{aligned} \]
对偶问题可解释为分数包：每个顶点 \(v\) 分配一个非负值 \(g(v)\)，使得每个顶点的闭邻域内总值不超过 1。
由线性规划强对偶定理，原问题与对偶问题最优值相等。
5. 与图的其他参数的关系
- 与整数支配数的关系：显然 \(\gamma_f(G) \le \gamma(G)\)。
- 与分数包数的关系：分数包数 \(\rho_f(G)\) 是上述对偶问题的最大值，因此 \(\gamma_f(G) = \rho_f(G)\)。
- 与最小度的关系：若图 \(G\) 的最小度为 \(\delta\)，则 \(\gamma_f(G) \ge \frac{|V|}{\delta+1}\)，因为每个顶点 \(v\) 的闭邻域包含至少 \(\delta+1\) 个顶点，且每个顶点最多被计数 \(\delta+1\) 次。
6. 计算与性质
- 分数支配数可通过线性规划在多项式时间内计算（即使整数支配是 NP 难的）。
- 正则图的分数支配数：对于 \(\delta\)-正则图，\(\gamma_f(G) = \frac{|V|}{\delta+1}\)，可通过均匀赋值 \(f(v) = \frac{1}{\delta+1}\) 达到最优。
- 完全图 \(K_n\)：\(\gamma_f(K_n) = 1\)，只需给任意一个顶点赋权值 1 即可支配全图。
- 路径与圈：可通过动态规划或递推精确计算。例如，路径 \(P_n\) 的分数支配数为 \(\lceil n/3 \rceil\) 的分数推广，实际为 \(n/3\)（当 \(n \equiv 0 \pmod{3}\)）或略高。
7. 分数全支配与变体
如果将条件改为对每个顶点 \(v\)，其开邻域 \(N(v)\) 的函数值之和至少为 1，则得到分数全支配函数，对应的最小总权值为分数全支配数 \(\gamma_{ft}(G)\)。类似地可定义分数符号支配等变体。
8. 研究意义与应用
分数支配为整数支配提供了更易分析的下界，常用于近似算法分析。在资源分配、传感器网络覆盖等问题中，分数模型允许部分分配资源，比整数模型更灵活。