作者lienasd126 (迷途の狮子)
看板Grad-ProbAsk
标题[理工]
时间Thu Sep 30 21:18:32 2021
这一题前面有人发问过了，不过还是有点不清楚的地方，
https://i.imgur.com/igWRlSb.jpg
因为就vertex cover的定义是包含图形所有边的最小点集，
那麽我们在找点的时候只要看是否有包含所有边，
那如题目所述的v1, v3, v4就好了，而对应到的是 x1, x3, x4，
那表格中的 yi 是为什麽产生的？ 这方面有点不太懂 ？？？
另外我有上网查过了，如
https://reurl.cc/GbEg2D
这里也是用m_ei去做表示，但是就是也不知道为什麽会还需要这个变数，
如果只是为了凑後面变数的2，好像变得很硬要，可以请各位大神解释，为什麽要有下面
的变数，谢谢～
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 115.43.138.74 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1633007914.A.BDC.html
※ 编辑: lienasd126 (115.43.138.74 台湾), 09/30/2021 21:19:23
1F：→ BusterButter: 每条edge至少会被一个cover set里的vertex给cover09/30 23:33
2F：→ BusterButter: 如果那条edge被两端都是在cover set里，那对应那条e09/30 23:34
3F：→ BusterButter: dge的digit是不是会被加两次09/30 23:34
4F：→ BusterButter: 可是有的edge只有一个端点是在cover set里面，所以09/30 23:36
5F：→ BusterButter: 我们为了让除了最高位外的digit都被加到2次，才有了09/30 23:36
6F：→ BusterButter: m_e （题目里的y)09/30 23:36
谢谢Buster大回答
所以等於说是因为边集内的edge会产生两次的探访，所以为了公平性（？）才有下面的那
块，那如果是这样不如可以说这个reduction 的 sum target就是固定的就是那个形是这
样吗？
7F：推 jacksoncsie: 推楼上回答09/30 23:41
※ 编辑: lienasd126 (39.13.5.135 台湾), 10/01/2021 09:08:56
8F：→ BusterButter: 与其说是公平性 不如说m_e是为了让我们定义target方10/01 13:04
9F：→ BusterButter: 便而已(除了最高bit 其他都是2)10/01 13:04
10F：→ BusterButter: 反正我们的目标是n_v的个数而不是m_e10/01 13:04
11F：→ BusterButter: 因为n_v的个数正是vertex cover set的cardinality 10/01 13:05
嗯嗯，谢谢 Buster大，大概懂了
※ 编辑: lienasd126 (115.43.138.74 台湾), 10/01/2021 13:51:29
12F：推 joywilliamjo: 可是这题最後算出来是22222啊不是32222 10/01 14:01
13F：推 joywilliamjo: 啊没事是我看错了 10/01 14:03
14F：推 alex391a: 一个比较直观一点的讲法是 10/07 09:20
15F：→ alex391a: 今天如果没有y 10/07 09:20
16F：→ alex391a: 那符合edge cover的取法结果有 10/07 09:20
17F：→ alex391a: 311111 10/07 09:20
18F：→ alex391a: 311112 10/07 09:20
19F：→ alex391a: 311122 10/07 09:20
20F：→ alex391a: 311121 10/07 09:20
21F：→ alex391a: … 10/07 09:20
22F：→ alex391a: 也就是2^5种 10/07 09:20
23F：→ alex391a: 那我们有y之後 就可以透过拿某些y来加成 10/07 09:20
24F：→ alex391a: 322222 10/07 09:20
25F：→ alex391a: 相对的如果今天怎麽取都会有个地方为0 10/07 09:20
26F：→ alex391a: 例如312120,310122… 10/07 09:20
27F：→ alex391a: 那不管怎麽取y 10/07 09:20
28F：→ alex391a: 都加不到322222 10/07 09:20
29F：→ alex391a: 也就是找不到三个点可以cover所有edge 10/07 09:20