作者houallan5478 (houallan5478)
看板Grad-ProbAsk
标题[理工] 离散 清大 100 图论
时间Mon Nov 4 08:41:15 2019
https://i.imgur.com/sBrfiCu.jpg
为什麽与maximum independent set 矛盾，可以推得 dominating set ?
请各位大大解惑了!
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 27.52.4.126 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1572828077.A.779.html
1F：推 ekids1234: 他这个结论是不是有错阿 11/04 11:54
2F：→ ekids1234: 噢看错 "not" greater 11/04 11:55
3F：→ ekids1234: 我觉得详解的表达方式有点让人混淆 11/04 12:56
4F：→ ekids1234: 後来我的理解是，只要 I 是 independent set，那 I 就 11/04 12:57
5F：→ ekids1234: 少打 Max^ 11/04 12:58
6F：→ ekids1234: I 就一定是 dominating set (否则可以成为更大的 Inde) 11/04 12:59
7F：→ ekids1234: 故，"Minimum" Donminating set 的 Size 一定小於等於 11/04 13:00
8F：→ ekids1234: Maximum Independent Set 的 Size 11/04 13:00
9F：→ ekids1234: 虽然我们无法指出一定找的到一个更小的，但假设没关系 11/04 13:02
10F：→ ekids1234: 中间有个 Dominating 打错，见谅 11/04 13:02
11F：→ houallan5478: 所以详解是在证 11/04 14:15
12F：→ houallan5478: 「只要I是最大独立集，那就一定是支配集。」 11/04 14:15
13F：→ houallan5478: 因此,既然I是支配集那就一定大於等於最小支配集。 11/04 14:15
14F：→ houallan5478: 感谢e大解惑 !!!总算了解了!! 11/04 14:15