作者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/m.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