作者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/m.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