作者ajnightmare (阿华田)
看板NTUBIME100HW
标题[演算] hamiltonian problem & longest path problem
时间Sun May 24 15:25:28 2009
说明问题
hamiltonian problem
input:图形G(V,E),和G上的两点x,y
output:是否有一条G上的路径从x到y经过G的每个vertex恰好一次
longest path problem
input:图形G(V,E),和G上的两点x,y
output:一条G上从x到y最长的路径只经过G上的每个点最多一次(simple path)
hamiltonian problem can be reduced to longest path problem
1.转换的演算法
hamitonian problem的input是图形G(V,E),和G上的两点x,y
相对应longest path problem也一样
longest path problem的output所给的path若有V-1长
则hamitonian problem的output为是
反之为否
2.转换的演算法时间
input转换需O(1)
output转换是O(V)
3.正确性
若longest path有V-1的长度,则会经过每个点恰好一次
即为hamiltonian path
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.7.59
※ 编辑: ajnightmare 来自: 58.114.208.7 (06/18 22:27)