[理工] 104 台大電機 離散

[cschenptt (chen)]

104台大電機 6.

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

因為題目是問cut edges 有s
所以是否代表可以一次切多條邊，若可以
設兩個分量僅靠兩條邊相連接，一次切斷那兩條邊
則符合 各分量的deg和 仍維持奇數
因此 存在 切邊集

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

因為我的想法若對 則會和解答不同
故上來討教

還請各位大神幫我看一下

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.173.172.121
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484936604.A.4F6.html
→ AkariAkaza: 你再確認一下bridge的定義，你的圖那樣會有cycle那就
→ AkariAkaza: 不是bridge了
→ hypnos135g: 1.不用糾結s 你考慮兩條(以上)就沒考慮到一條的情況
→ hypnos135g: 2.若同時切斷兩條bridge 會形成超過兩個components