分数支配集
Post
by Anonymous »
在图论中，“分数支配集”是支配集概念的推广，它允许为顶点分配 0 到 1 之间的分数权重，而不是二进制隶属度。这种松弛将支配问题转化为线性规划问题，通常会产生更精确的边界并实现多项式时间计算。
== 定义 ==
令 G = (V, E) 为图表。 “分数支配函数”是一个函数 f: V \to [0, 1]，这样对于每个顶点 v \in V，邻域（图论）|闭邻域 N[v] 上的 f 之和至少为 1：
:\sum_{u \in N[v]} f(u) \geq 1
“分数支配数”\gamma_f(G) 是分数支配函数的最小总权重：
:\gamma_f(G) = \min\left\{\sum_{v \in V} f(v)\right\}
== 属性 ==
对于任意图G，分数支配数满足：
:\gamma_f(G) \leq \gamma(G) \leq \Gamma(G) \leq \Gamma_f(G)
其中 \gamma(G) 是支配数，\Gamma(G) 是上支配数，\Gamma_f(G) 是上分数支配数。
利用强对偶性，可以将分数支配数计算为线性规划的解。
对于任何具有 n 个顶点、最小度 \delta 和最大度 \Delta 的图 G：
:\frac{n}{\Delta + 1} \leq \gamma_f(G) \leq \frac{n}{\delta + 1}
==特定图族的公式==
对于正则图|
:\gamma_f(G) = \frac{n}{k+1}
对于完整的二分图K_{r,s}：
:\gamma_f(K_{r,s}) = \frac{r(s-1) + s(r-1)}{rs - 1}
一些图形类具有 \gamma_f(G) = \gamma(G)：
* 树（图论）|树
* 块图（每个块都完整的图）
* 强弦图
对于图的强乘积 G \boxtimes H：
:\gamma_f(G \boxtimes H) = \gamma_f(G) \cdot \gamma_f(H)
对于图 G \square H 的笛卡尔积（Vizing 猜想，分数版本）：
:\gamma_f(G \square H) \geq \gamma_f(G) \cdot \gamma_f(H)
==计算复杂度==
由于分数支配数可以表示为线性程序，因此可以在多项式时间内计算它，这与 NP 难计算的标准支配数不同。
==变体==
“分数距离 k 支配函数”概括了这一概念，要求对于每个顶点 v，其距离 -k 邻域 N_k[v]（距 v 距离最远 k 的顶点）的总和至少为 1。相应的“分数距离 k 支配数”表示为 \gamma_{kf}(G)。
对于k-正则图和k的特定值，存在精确的公式。例如，对于循环 C_n：
:\gamma_{kf}(C_n) = \frac{n}{2k+1}
一个“有效的分数支配函数”满足
:\sum_{u \in N[v]} f(u) = 1
对于所有顶点 v。 并非所有图都承认有效的分数支配函数。
“分数总支配函数”要求对于每个顶点 v，其开邻域 N(v)（不包括 v 本身）的总和至少为 1。 “分数总支配数”表示为 \gamma_{ft}(G)。
“上分数支配数”\Gamma_f(G) 是所有最小分数支配函数中的最大权重。
==另见==
* 统治集
* 线性规划
* 分数图着色
图论
图不变量
图论中的计算问题
Mobile version