[理工] 離散 清大 100 圖論

[houallan5478 (houallan5478)]

https://i.imgur.com/sBrfiCu.jpg

為什麼與maximum independent set 矛盾，可以推得 dominating set ?


請各位大大解惑了!


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.52.4.126 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1572828077.A.779.html
推 ekids1234: 他這個結論是不是有錯阿
→ ekids1234: 噢看錯  "not" greater
→ ekids1234: 我覺得詳解的表達方式有點讓人混淆
→ ekids1234: 後來我的理解是，只要 I 是 independent set，那 I 就
→ ekids1234:                   少打 Max^
→ ekids1234: I 就一定是 dominating set (否則可以成為更大的 Inde)
→ ekids1234: 故，"Minimum" Donminating set 的 Size 一定小於等於
→ ekids1234: Maximum Independent Set 的 Size
→ ekids1234: 雖然我們無法指出一定找的到一個更小的，但假設沒關係
→ ekids1234: 中間有個   Dominating 打錯，見諒
→ houallan5478: 所以詳解是在証
→ houallan5478: 「只要I是最大獨立集，那就一定是支配集。」
→ houallan5478: 因此,既然I是支配集那就一定大於等於最小支配集。
→ houallan5478: 感謝e大解惑 !!!總算了解了!!