作者magic83v (R7)
看板Grad-ProbAsk
標題[理工] 108交大資演reduction
時間Wed Feb 13 18:45:40 2019
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1550054743.A.F15.html
1F：推 HungDa: case2應該是A但是我把ab連起來考完才想到吐血02/13 18:51
2F：→ HungDa: case3應該ABCD吧02/13 18:51
3F：→ alen0303: 這題組有++記號 多選幾個選項有搞頭嗎02/13 18:52
4F：→ HungDa: 錯一個選項就整題組錯有唸書跟沒唸書一樣0分哭哭02/13 18:54
5F：→ uttc: 還好有研究去年那題02/13 19:15
能請問你的想法嗎
6F：→ eric131204: 所以這題答案是什02/13 19:16
7F：推 HungDa: 不知道反正我應該說錯了02/13 19:33
※ 編輯: magic83v (27.247.162.70), 02/13/2019 20:45:30
9F：→ uttc: 某位好心人分享的去年的解法 可以參考比對 02/13 21:25
10F：推 FRAXIS: case 2, 因為 (x, y) 不相連，所以 HC 只能有 x - z - y 02/13 23:13
11F：→ FRAXIS: 的情況（y - z - x 是對稱的，因為是 undirectied graph） 02/13 23:14
12F：→ FRAXIS: 所以用 a, b 兩個點來限制是可以的 02/13 23:14
13F：推 Youhao: 只加兩個edge a和b的degree都是1還會形成cycle嗎 02/14 00:06
14F：推 FRAXIS: case 2 至少要加 4 個 edge 吧 02/14 12:01
15F：→ Youhao: 這樣這題多選的意思是要選哪幾個edge要加嗎XD 02/14 13:08
16F：→ magic83v: 清大也沒考reduction qq 02/14 16:35
17F：→ magic83v: F大能請問你邊應該加在哪嗎 02/14 16:36
18F：推 anonimo: 36B/37BC/38ABC 02/15 14:07
19F：推 agag5123: 樓上正解 a,b放進裡面，只能一端流進另一端流出 02/15 14:29
20F：→ agag5123: 所以b) x-a-z-b-y,有漢米爾圖要流過a一定要走x-a-z，那 02/15 14:31
21F：→ agag5123: 表示原本就有圖可以走x-z 02/15 14:32
22F：→ magic83v: 好吧噴光 我的圖完全亂畫一通 02/15 14:32
23F：→ agag5123: c)比較複雜，a,b都要跟xyz相連，保證有漢米爾圖從xyz任 02/15 14:38
24F：→ agag5123: 一點進來時，一定要走a或b，從剩下兩點其中之一出去， 02/15 14:38
25F：→ agag5123: 然後因為還有a或b存在，它非得把剩下的a或b走完，才可 02/15 14:38
26F：→ agag5123: 能能完成漢米爾cycle 02/15 14:38
27F：→ agag5123: 如此一來有路徑成立的話，把a,b拔掉就是對應的漢米爾了 02/15 14:40
28F：推 kkjja90236: 為何錯一個選項就全錯啦 02/18 15:00