PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [討論] UVa12615

看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間9年前 (2015/01/16 11:12)推噓0(0推 0噓 0→)

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

※ 引述《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