[理工] 107 交大資演 10已刪文

看板Grad-ProbAsk作者dumpling1234 (dumpling)時間5年前 (2019/01/27 03:01)推噓4(4推 0噓 15→)

留言19則, 3人參與討論串1/2 (看更多)

對了板上的答案發現這題沒有答案所以我想來確認一下我寫的方法有沒有問題麻煩有答案或板上的大神們幫我修正 Give a instance for HamEx(G,x) G = (V,E) V = vertex in G E = edge in G 然後加入ㄧ點 h 不屬於 V and 加入ㄧ邊 (h,x) 不屬於 E 建造ㄧ個新的圖為G' = (V + {h}, E + {(h,x)}) 然後可以設計ㄧ演算法: 0 if(HamP(G))return No; //確認有無 HP 1 if (HamP(G')) then return No; //確認有無 x 非頭尾 HP 2 else return Yes; prove correctness: 已經由第0行確認有無 HP in G 所以只需檢查 if there is a HP in G from node u to v so that u,v! = x Claim : if there isn't a hamiltonian path in G' then there is a HP in G from node u to v so that u,v! = x if there isn't a HP in G' 因為 deg(h) =1 所以 h 必定為起始點或終點則不存在有ㄧ條HP的順序為 h,x,........ in G' 則在原圖 G 中不會存在ㄧ條 HP 為 x 為起點或終點換種寫法 if there is a HP in G from node u to v so that u,v = x 所以將存在有ㄧ條HP的順序為 x,........ in G 則可以找到ㄧ條HP的順序為 h,x,........ in G' 所以得證 Time Complexity : O(n^7)+O(1)(加一點和一邊) = O(n^7) 預祝大家考試順利! -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.236.53.144 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1548529277.A.AAE.html

推

FRAXIS

01/27 05:54, 5年前 , 1^F

01/27 05:54, 1^F

我改了一下跟寫了另一種寫法但不知道哪個比較好像好ㄧ些 ※ 編輯: dumpling1234 (36.239.44.204), 01/27/2019 06:26:37 ※ 編輯: dumpling1234 (36.239.44.204), 01/27/2019 06:29:38 ※ 編輯: dumpling1234 (36.239.44.204), 01/27/2019 06:48:38 ※ 編輯: dumpling1234 (36.239.44.204), 01/27/2019 06:56:00 ※ 編輯: dumpling1234 (36.239.44.204), 01/27/2019 07:01:45

→

Leaving

01/27 07:52, 5年前 , 2^F

01/27 07:52, 2^F

→

Leaving

01/27 07:54, 5年前 , 3^F

01/27 07:54, 3^F

→

Leaving

01/27 07:59, 5年前 , 4^F

01/27 07:59, 4^F