Re: [討論] UVa12615

看板Prob_Solve作者DJWS (...)時間9年前 (2015/01/15 22:54)推噓3(3推 0噓 5→)

留言8則, 2人參與討論串2/4 (看更多)

※ 引述《dreamoon (大笨蛋小月唷!)》之銘言：

推

FRAXIS

01/15 05:21,

01/15 05:21

→

dreamoon

01/15 19:53,

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。本題是求後者。最小權重邊支配集。然後前面介紹的那些極大極小關係，到了這邊也成立。如果我沒搞錯的話。 -----------

推

FRAXIS

這題跟極大沒有關係。再者，最小邊支配集 != 最大邊獨立集(最大匹配)。除非這題的圖是某種特殊圖類，剛好滿足你說的那樣。這部分我不清楚。

→

dreamoon

最小邊支配集 != 最大邊獨立集(最大匹配)。 ----------- 結論就是不要再肖想獨立集了，除非那是一種特殊的圖類。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.88.58 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1421333690.A.4F6.html ※ 編輯: DJWS (111.250.88.58), 01/15/2015 22:57:59

推

dreamoon

01/15 23:22, , 1^F

01/15 23:22, 1^F

推

dreamoon

01/15 23:24, , 2^F

01/15 23:24, 2^F

→

dreamoon

01/15 23:24, , 3^F

01/15 23:24, 3^F