作者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)