楼主:
DLHZ ( )
2020-01-25 15:05:22Q: 如何对input为一无向图G =(E, V)的Hamiltonian path problem
跟Hamiltonian cycle problem互相reduction？
1. 对HP转成HC
如果将一个无向图输入解HP problem的算法是yes
那任意拿掉一个边后输出依然是yes则存在HC
更正: 令G' = (E', V') 其中
V'=V∪{v}
E'=E∪{(v, u)|u∈V}
若G'存在HC则有一cycle路径为v->x->...->y->v
xy之间依然符合HP的性质且经过所有G中的点
代表G中存在一HP x为起点y为终点
2. 对HC转成HP
对要解HP的图G任意挑选图中某一点v
令G' = (E', V') 其中
V'=V∪{v', s, t}
E'=E∪{(v', u)|(v, u)∈E}∪{(s, v), (v, v'), (v', t)}
如果G'存在HP
由于s跟t的degree皆为1
则s跟t必定为起点或终点
考虑从s出发的情况
那t只能由v'前往
所以在走到v'前必须先经过其他所有点
而在经过v'跟t以外的所有点之后能到达v'
代表这个路径也能走回v
所以G'存在HP代表原图G存在HC
作者: NCTUcs 2020-01-25 15:15:00
HP转HC的reduction好像不是这样子吧应该是加上一个点v 将G上所有点和v相连这样只要在G'上包含HC 则代表有一个cycle经过x->v->y则表示G上有一条HP 且path的起终点分别是x和y