※ 引述《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: 若把边当点，大概可以应转成一般图的最大独立集
: 最小边支配集 != 最大边独立集(最大匹配)。
: