※ 引述《FRAXIS (喔喔)》之銘言： : ※ 引述《DJWS (...)》之銘言： : : 推 FRAXIS: 題目要求是不是要找一個maximal matching? : : 這題跟極大沒有關係。 : : 再者，最小邊支配集 != 最大邊獨立集(最大匹配)。 : : 除非這題的圖是某種特殊圖類，剛好滿足你說的那樣。這部分我不清楚。 : 其實 minimum edge dominating set 的大小是跟 : minimum independent edge dominating set 是一樣的 : 然後 minimum independent edge dominating set 是一個 : minimum maximal matching : http://cgi.di.uoa.gr/~vassilis/co/dominating-sets.pdf : 當然，minimum maximal matching也不好找就是了， : 而且當圖是有weighted的時候，這關係就不存在了。 我前面有一句話有錯： 極大獨立集 = 極小支配集 這句話有錯 這是單向不是雙向。 1. 極大獨立集，必是極小支配集。 2. 極小支配集，不一定是(極小)獨立集。支配集的點可以相鄰，不一定要獨立。 然後你現在提到的是新概念： 獨立支配集(independent dominating set) 支配集的點可以相鄰，不一定要獨立，但是我們只看那些獨立的。 有了這個概念之後，先前的 1. 可以補充成： 3. 極大獨立集，必是極小支配集（極小獨立支配集） 以及根據定義可以知道： 4. 最小的極大獨立集，必是最小獨立支配集 不過這些內容，跟原問題沒有直接關聯。 原問題只是想求支配集。這跟獨立集、獨立支配集完全沒有關聯。更不要說匹配了。 但是由於這題是特殊圖類 partial 2-tree 獨立集、支配集很可能有某種關聯，甚至相同。 不過我沒有仔細去研究。 所以我要引用我前面那篇文的結論： 結論就是不要再肖想獨立集了，除非那是一種特殊的圖類。 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.84.205 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1421377946.A.097.html ※ 編輯: DJWS (111.250.84.205), 01/16/2015 11:12:52