作者DLHZ (going faster)
看板Grad-ProbAsk
标题[理工] Reduction 107 清大 计科 8
时间Sat Jan 25 15:05:22 2020
Q: 如何对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
---------------------------------------------------
我想问这样的过程是否正确？
还是有那些东西需要说明？
我比较不确定是1. 这样的叙述是否可以
毕竟自己没给教授改过这种东西
不太确定
想听听大家的意见
--
1F：推 godtomanne:alt+f4没有用?9/10 00:18
2F：→ alt:去你妈的 9/10 00:24
3F：嘘 F4:你才没用 9/10 00:25
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 106.1.43.179 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1579935969.A.108.html
4F：推 NCTUcs: HP转HC的reduction好像不是这样子吧 01/25 15:15
5F：→ NCTUcs: 应该是加上一个点v 将G上所有点和v相连 01/25 15:16
6F：→ NCTUcs: 这样只要在G'上包含HC 则代表有一个cycle经过x->v->y 01/25 15:17
7F：→ NCTUcs: 则表示G上有一条HP 且path的起终点分别是x和y 01/25 15:17
8F：→ DLHZ: 喔喔我了解了 那像2. 这样的写法应该就没问题了吧 01/25 15:21
9F：推 NCTUcs: 可能要强调若G'中存在HP 则path的起终点必定分别为s和t 01/25 15:24
已补充。另外，对於x->v->y我做了点修改，感觉比较符合个别的意思。
10F：推 MASAGA: 我个人觉得唯若且若也顺便写一下比较保险 01/25 16:36
单向应该就可以了吧?考量时间上的问题应该只会写出必要的部分。
※ 编辑: DLHZ (106.1.43.179 台湾), 01/25/2020 16:47:57