作者netsphere (欢迎来下棋 ^_<)
看板C_and_CPP
标题[问题] MINIMUM VERTEX COVER
时间Wed Apr 1 16:38:47 2009
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
1F：推 Fenikso: ． 04/01 16:54
2F：→ Fenikso: ／ / \ ＼ 04/01 16:54
3F：→ Fenikso: ． ． ． ． 04/01 16:54
4F：→ Fenikso: /\ /\ /\ /\ 04/01 16:55
5F：→ Fenikso: .. .. .. .. 04/01 16:56
6F：→ Fenikso:你朋友的算法会先拔掉degree=4的root, 然後是第二层的点 04/01 16:56
7F：→ Fenikso:共5个点. 但是其实只要第二层的四个点就好 04/01 16:57
8F：→ netsphere:谢谢 F大 我知道了 04/01 17:04