https://imgur.com/Wt5ikwe
對了板上的答案 發現這題沒有答案
所以我想來確認一下我寫的方法有沒有問題
麻煩有答案 或 板上的大神們 幫我修正
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)
預祝大家考試順利!