Re: [討論] UVa12615
看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間10年前 (2015/01/16 01:18)推噓0(0推 0噓 0→)留言0則, 0人參與討論串3/4 (看更多)
※ 引述《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的時候，這關係就不存在了。
: → dreamoon: 若把邊當點，大概可以應轉成一般圖的最大獨立集
: 最小邊支配集 != 最大邊獨立集(最大匹配)。
: -----------
: 結論就是不要再肖想獨立集了，除非那是一種特殊的圖類。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.170.195.149
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1421342314.A.318.html
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
