※ 引述《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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1421342314.A.318.html