[理工] 離散 清大 100 圖論

看板Grad-ProbAsk作者 (houallan5478)時間6年前 (2019/11/04 08:41), 編輯推噓1(1推 0噓 13→)
留言14則, 2人參與, 6年前最新討論串1/1
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
推
11/04 11:54, 6年前 , 1F
他這個結論是不是有錯阿
11/04 11:54, 1F
→
11/04 11:55, 6年前 , 2F
噢看錯 "not" greater
11/04 11:55, 2F
→
11/04 12:56, 6年前 , 3F
我覺得詳解的表達方式有點讓人混淆
11/04 12:56, 3F
→
11/04 12:57, 6年前 , 4F
後來我的理解是，只要 I 是 independent set，那 I 就
11/04 12:57, 4F
→
11/04 12:58, 6年前 , 5F
少打 Max^
11/04 12:58, 5F
→
11/04 12:59, 6年前 , 6F
I 就一定是 dominating set (否則可以成為更大的 Inde)
11/04 12:59, 6F
→
11/04 13:00, 6年前 , 7F
故，"Minimum" Donminating set 的 Size 一定小於等於
11/04 13:00, 7F
→
11/04 13:00, 6年前 , 8F
Maximum Independent Set 的 Size
11/04 13:00, 8F
→
11/04 13:02, 6年前 , 9F
雖然我們無法指出一定找的到一個更小的，但假設沒關係
11/04 13:02, 9F
→
11/04 13:02, 6年前 , 10F
中間有個 Dominating 打錯，見諒
11/04 13:02, 10F
→
11/04 14:15, 6年前 , 11F
所以詳解是在証
11/04 14:15, 11F
→
11/04 14:15, 6年前 , 12F
「只要I是最大獨立集，那就一定是支配集。」
11/04 14:15, 12F
→
11/04 14:15, 6年前 , 13F
因此,既然I是支配集那就一定大於等於最小支配集。
11/04 14:15, 13F
→
11/04 14:15, 6年前 , 14F
感謝e大解惑 !!!總算了解了!!
11/04 14:15, 14F
‣ 更多 houallan5478 的文章
文章代碼(AID): #1TltEjTv (Grad-ProbAsk)