You need to enable JavaScript to run this app.
最新活动
大模型
产品
解决方案
定价
生态与合作
支持与服务
开发者
了解我们

关于图的分数覆盖数与分数填充数相等性的推导问题求助

关于图的分数覆盖数与分数填充数相等性的推导问题求助

大家好,我在处理图论中分数覆盖与分数填充的对偶问题时遇到了瓶颈,想请各位帮忙梳理一下推导过程中的问题:

我已经算出目标图的分数覆盖数为$\frac{5}{2}$,现在需要证明它与分数填充数相等,于是采用了n-fold填充的思路,通过定义各填充的重数$m(i)$,列出了以下约束不等式:

  • $m(1)+m(2) \le n$
  • $m(1)+m(3) \le n$
  • $m(2)+m(3) \le n$
  • $m(2)+m(4) \le n$
  • $m(3)+m(5) \le n$
  • $m(4)+m(5) \le n$

接下来我尝试将所有不等式相加,这里先纠正一下我之前的笔误:正确的加和应该是每个$m(i)$的系数等于它在约束中出现的次数——$m(1)$出现2次,$m(2)$出现3次,$m(3)$出现3次,$m(4)$出现2次,$m(5)$出现2次,所以加和后得到:
$$2m(1)+3m(2)+3m(3)+2m(4)+2m(5) \le 6n$$

随后我将式子变形为:
$$2\sum_{i}m(i) + m(2)+m(3) \le 6n$$
其中我定义$\sum_{i}m(i) = |Y|$(即填充的总重数),代入后得到:
$$2|Y| + m(2)+m(3) \le 6n$$

但这样推导下来只能得到$|Y| \le 3n$,而我期望得到的是$|Y| \le \frac{5n}{2}$,这样分数填充数才能等于$\frac{5}{2}$,与分数覆盖数匹配。问题显然出在$m(2)+m(3)$这一项带来的冗余上,如果没有这一项就能得到正确结果,但我不知道该如何处理这个冗余,或者是不是我的约束条件列错了?

另外我确认分数覆盖数的计算是正确的,满足所有覆盖条件,现在卡在分数填充数的推导环节了,有没有大佬能指点一下问题出在哪里,或者该调整什么推导思路?

备注:内容来源于stack exchange,提问作者nortedor

火山引擎 最新活动