一道有关覆盖的算法问题??


平面上有n个点，互相之间有连线，现在想提取其中k个点（与这k个点相连的点也会被提取），使平面中的点为空，如何保证k值最小？

[解决办法]
先把这些点按照连通关系分类，然后再对连通的点集合提取最小覆盖。
[解决办法]
最小覆盖集问题，楼主可以参考这方面的资料
[解决办法]
最小覆盖集问题,这是NPC问题，当N很大时，没有最优算法，只能找一个近似算法。
[解决办法]
使用google搜索：
Minimum Vertex cover