※ 引述《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://www.ptt.cc/bbs/Prob_Solve/M.1421377946.A.097.html
※ 編輯: DJWS (111.250.84.205), 01/16/2015 11:12:52