[問題] MINIMUM VERTEX COVER

[netsphere (歡迎來下棋 ^_<)]

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
推 Fenikso:                  ．
→ Fenikso:              ／ /  \ ＼
→ Fenikso:            ．  ．  ． ．
→ Fenikso:            /\  /\  /\ /\
→ Fenikso:            ..  ..  .. ..
→ Fenikso:你朋友的算法會先拔掉degree=4的root, 然後是第二層的點
→ Fenikso:共5個點. 但是其實只要第二層的四個點就好
→ netsphere:謝謝 F大 我知道了