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)
预祝大家考试顺利!