[問題] MINIMUM VERTEX COVER
minimum vertex cover是NP-Complete的問題 我朋友說他想到一個 P 的辦法解決
我想不到什麼例子反駁他 ..... Orz
請問用下敘的演算法解 minimum vertex cover 問題會有什麼不對的地方嗎?
他的想法有點像是解最小生成樹 大概是像這樣:
========algorithm============
給一個圖G 找G中Degree最大的頂點A 放入minimum vertex cover Set中
將A和A相接的邊去掉 形成新的圖G`
一直重覆 直到圖的總Degree=0
=============================
當然這其中一定有什麼錯誤 要不然這題就不會是NP-C了
希望大大們可以舉一個反例出來 謝謝 :]
http://en.wikipedia.org/wiki/Vertex_cover
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.244.132.1
推
04/01 16:54, , 1F
04/01 16:54, 1F
→
04/01 16:54, , 2F
04/01 16:54, 2F
→
04/01 16:54, , 3F
04/01 16:54, 3F
→
04/01 16:55, , 4F
04/01 16:55, 4F
→
04/01 16:56, , 5F
04/01 16:56, 5F
→
04/01 16:56, , 6F
04/01 16:56, 6F
→
04/01 16:57, , 7F
04/01 16:57, 7F
→
04/01 17:04, , 8F
04/01 17:04, 8F
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
