※ 引述《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/cn.aspx?n=bbs/Prob_Solve/M.1421377946.A.097.html ※ 编辑: DJWS (111.250.84.205), 01/16/2015 11:12:52