[理工] 清大 100 計科 獨立集 支配集

[Astar5566 (一顆星5566)]

http://i.imgur.com/GvJ70dk.jpg

想請問11題

要證明最小支配集點數不會比最大獨立集點數多

這題要怎麼證啊？

這兩個實在太像 有點搞混了

感謝


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.77.91
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485679909.A.6A4.html
推 FRAXIS: Maximal independent set 一定是 dominating set