[理工]

[lienasd126 (迷途の獅子)]

這一題前面有人發問過了，不過還是有點不清楚的地方，
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://www.ptt.cc/bbs/Grad-ProbAsk/M.1633007914.A.BDC.html
※ 編輯: lienasd126 (115.43.138.74 臺灣), 09/30/2021 21:19:23
→ BusterButter: 每條edge至少會被一個cover set裡的vertex給cover
→ BusterButter: 如果那條edge被兩端都是在cover set裡，那對應那條e
→ BusterButter: dge的digit是不是會被加兩次
→ BusterButter: 可是有的edge只有一個端點是在cover set裡面，所以
→ BusterButter: 我們為了讓除了最高位外的digit都被加到2次，才有了
→ BusterButter: m_e （題目裡的y)
謝謝Buster大回答
所以等於說是因為邊集內的edge會產生兩次的探訪，所以為了公平性（？）才有下面的那
塊，那如果是這樣不如可以說這個reduction 的 sum target就是固定的就是那個形是這
樣嗎？
推 jacksoncsie: 推樓上回答
※ 編輯: lienasd126 (39.13.5.135 臺灣), 10/01/2021 09:08:56
→ BusterButter: 與其說是公平性 不如說m_e是為了讓我們定義target方
→ BusterButter: 便而已(除了最高bit 其他都是2)
→ BusterButter: 反正我們的目標是n_v的個數而不是m_e
→ BusterButter: 因為n_v的個數正是vertex cover set的cardinality
嗯嗯，謝謝 Buster大，大概懂了
※ 編輯: lienasd126 (115.43.138.74 臺灣), 10/01/2021 13:51:29
推 joywilliamjo: 可是這題最後算出來是22222啊不是32222
推 joywilliamjo: 啊沒事是我看錯了
推 alex391a: 一個比較直觀一點的講法是
→ alex391a: 今天如果沒有y
→ alex391a: 那符合edge cover的取法結果有
→ alex391a: 311111
→ alex391a: 311112
→ alex391a: 311122
→ alex391a: 311121
→ alex391a: …
→ alex391a: 也就是2^5種
→ alex391a: 那我們有y之後 就可以透過拿某些y來加成
→ alex391a: 322222
→ alex391a: 相對的如果今天怎麼取都會有個地方為0
→ alex391a: 例如312120,310122…
→ alex391a: 那不管怎麼取y
→ alex391a: 都加不到322222
→ alex391a: 也就是找不到三個點可以cover所有edge