[理工] 108交大資演reduction

看板Grad-ProbAsk作者 (R7)時間6年前 (2019/02/13 18:45), 6年前編輯推噓8(8推 0噓 20→)
留言28則, 10人參與, 6年前最新討論串1/1
https://i.imgur.com/jclhMmO.jpg
https://i.imgur.com/VqYEqap.jpg
HC <p HC3 想問一下這題各位的想法 我的想法是只加兩個點 沒辦法轉換到使x.y.z連續 剛好又有給以上皆非... 我就猜e了 這是我的想法 case2 https://i.imgur.com/whg0aom.jpg
case3 https://i.imgur.com/ACg4kkm.jpg
我直觀想覺得應該要多個點才能做到 怕明天也考類似的又不會寫想搞懂 感謝各位 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.247.162.70 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1550054743.A.F15.html
推
02/13 18:51, 6年前 , 1F
case2應該是A但是我把ab連起來考完才想到吐血
02/13 18:51, 1F
→
02/13 18:51, 6年前 , 2F
case3應該ABCD吧
02/13 18:51, 2F
→
02/13 18:52, 6年前 , 3F
這題組有++記號 多選幾個選項有搞頭嗎
02/13 18:52, 3F
→
02/13 18:54, 6年前 , 4F
錯一個選項就整題組錯有唸書跟沒唸書一樣0分哭哭
02/13 18:54, 4F
→
02/13 19:15, 6年前 , 5F
還好有研究去年那題
02/13 19:15, 5F
能請問你的想法嗎
→
02/13 19:16, 6年前 , 6F
所以這題答案是什
02/13 19:16, 6F
推
02/13 19:33, 6年前 , 7F
不知道反正我應該說錯了
02/13 19:33, 7F
※ 編輯: magic83v (27.247.162.70), 02/13/2019 20:45:30
→
02/13 21:24, 6年前 , 8F
02/13 21:24, 8F
→
02/13 21:25, 6年前 , 9F
某位好心人分享的去年的解法 可以參考比對
02/13 21:25, 9F
推
02/13 23:13, 6年前 , 10F
case 2, 因為 (x, y) 不相連，所以 HC 只能有 x - z - y
02/13 23:13, 10F
→
02/13 23:14, 6年前 , 11F
的情況（y - z - x 是對稱的，因為是 undirectied graph）
02/13 23:14, 11F
→
02/13 23:14, 6年前 , 12F
所以用 a, b 兩個點來限制是可以的
02/13 23:14, 12F
推
02/14 00:06, 6年前 , 13F
只加兩個edge a和b的degree都是1還會形成cycle嗎
02/14 00:06, 13F
推
02/14 12:01, 6年前 , 14F
case 2 至少要加 4 個 edge 吧
02/14 12:01, 14F
→
02/14 13:08, 6年前 , 15F
這樣這題多選的意思是要選哪幾個edge要加嗎XD
02/14 13:08, 15F
→
02/14 16:35, 6年前 , 16F
清大也沒考reduction qq
02/14 16:35, 16F
→
02/14 16:36, 6年前 , 17F
F大能請問你邊應該加在哪嗎
02/14 16:36, 17F
推
02/15 14:07, 6年前 , 18F
36B/37BC/38ABC
02/15 14:07, 18F
推
02/15 14:29, 6年前 , 19F
樓上正解 a,b放進裡面，只能一端流進另一端流出
02/15 14:29, 19F
→
02/15 14:31, 6年前 , 20F
所以b) x-a-z-b-y,有漢米爾圖要流過a一定要走x-a-z，那
02/15 14:31, 20F
→
02/15 14:32, 6年前 , 21F
表示原本就有圖可以走x-z
02/15 14:32, 21F
→
02/15 14:32, 6年前 , 22F
好吧噴光 我的圖完全亂畫一通
02/15 14:32, 22F
→
02/15 14:38, 6年前 , 23F
c)比較複雜，a,b都要跟xyz相連，保證有漢米爾圖從xyz任
02/15 14:38, 23F
→
02/15 14:38, 6年前 , 24F
一點進來時，一定要走a或b，從剩下兩點其中之一出去，
02/15 14:38, 24F
→
02/15 14:38, 6年前 , 25F
然後因為還有a或b存在，它非得把剩下的a或b走完，才可
02/15 14:38, 25F
→
02/15 14:38, 6年前 , 26F
能能完成漢米爾cycle
02/15 14:38, 26F
→
02/15 14:40, 6年前 , 27F
如此一來有路徑成立的話，把a,b拔掉就是對應的漢米爾了
02/15 14:40, 27F
推
02/18 15:00, 6年前 , 28F
為何錯一個選項就全錯啦
02/18 15:00, 28F
‣ 更多 magic83v 的文章
文章代碼(AID): #1SO_LNyL (Grad-ProbAsk)