作者DJWS (...)
看板Prob_Solve
標題Re: [討論] UVa12615
時間Thu Jan 15 22:54:46 2015
※ 引述《dreamoon (大笨蛋小月唷!)》之銘言：
1F：推 FRAXIS: 題目要求是不是要找一個maximal matching? 01/15 05:21
2F：→ dreamoon: 若把邊當點，大概可以應轉成一般圖的最大獨立集 01/15 19:53
原題我不會解，不過我可以解釋一下支配集和獨立集
獨立集(independent set)：選出一些點，互不相鄰。
最佳化問題是越多越好。
支配集(dominating set)：選出一些點，其餘點皆與之相鄰（所有點皆與之相鄰/重疊）。
最佳化問題是越少越好。
這兩個都是NP-complete，如果考慮權重就是NP-hard。
特殊的圖類才有多項式時間解，例如tree之類的。
-----------
極大獨立集(maximal independent set): 無法再選出一些點的獨立集。
最大獨立集(maximum independent set): 點數最多的獨立集（點數最多的極大獨立集）。
極大獨立集 = 極小支配集。
EDIT: 這句話有誤，請見下一篇回文
這個很好想。拿掉一個點，阿就不支配了。補上一個點，阿就不獨立了。
但是
最大獨立集 != 最小支配集
極大極小都OK了，為什麼最大最小不OK?
簡單來說，最大獨立集肯定是極小支配集，但是不一定剛好是最小支配集。
再來
最大獨立集必是支配集
最小支配集不一定是獨立集
到這裡應該有人覺得很煩了，所以就不再多提了...
-----------
邊獨立集(edge independent set): 上述的點改成邊。 就是匹配(matching)啦。
邊支配集(edge dominating set): 上述的點改成邊。
前者是P，經典的算法例如 Edmonds' blossom algorithm。
後者是NP-hard。
本題是求後者。最小
權重邊支配集。
然後前面介紹的那些極大極小關係，到了這邊也成立。
如果我沒搞錯的話。
-----------
3F：推 FRAXIS: 題目要求是不是要找一個maximal matching?
這題跟極大沒有關係。
再者，最小邊支配集 != 最大邊獨立集(最大匹配)。
除非這題的圖是某種特殊圖類，剛好滿足你說的那樣。這部分我不清楚。
4F：→ dreamoon: 若把邊當點，大概可以應轉成一般圖的最大獨立集
最小邊支配集 != 最大邊獨立集(最大匹配)。
-----------
結論就是不要再肖想獨立集了，除非那是一種特殊的圖類。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.88.58
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1421333690.A.4F6.html
※ 編輯: DJWS (111.250.88.58), 01/15/2015 22:57:59
5F：推 dreamoon: 不過這題顯然就是特殊圖 01/15 23:22
6F：推 dreamoon: 我喜歡FRAXIS所說的用tree decomposition去思考它 01/15 23:24
7F：→ dreamoon: 這樣去思考感覺上比較有系統 01/15 23:24
9F：→ DJWS: 有線性時間算法 01/15 23:48
10F：→ DJWS: 不過我還沒查到reference 01/15 23:48
11F：推 dreamoon: 線性是把tree-width當常數?若是這樣應該就和我的方法 01/15 23:55
12F：→ dreamoon: 差不多 01/15 23:55
※ 編輯: DJWS (111.250.84.205), 01/16/2015 11:13:46