[理工] 104 台大電機 離散

看板Grad-ProbAsk作者 (chen)時間9年前 (2017/01/21 02:23), 編輯推噓0(004)
留言4則, 2人參與, 最新討論串1/1
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

01/21 08:11, , 1F
你再確認一下bridge的定義,你的圖那樣會有cycle那就
01/21 08:11, 1F

01/21 08:11, , 2F
不是bridge了
01/21 08:11, 2F

01/21 10:00, , 3F
1.不用糾結s 你考慮兩條(以上)就沒考慮到一條的情況
01/21 10:00, 3F

01/21 10:00, , 4F
2.若同時切斷兩條bridge 會形成超過兩個components
01/21 10:00, 4F
文章代碼(AID): #1OWbMSJs (Grad-ProbAsk)