algorithm - 查找所需的最小数量 'central points'

Question

我有一组“n”个节点。函数返回两个节点之间的一种距离，使得 dist(a,c) 可能不是 dist(a,b)+dist(b,c)。基于阈值，我通过边连接某些节点。我希望选择最少数量的节点，以使这些节点的集合及其直接边缘连接的邻居组成整个 n 节点集合。是否可能有最佳解决方案？在纸上涂鸦让我觉得中心性可以提供帮助(程度，亲密度？)。我想到了聚类，但此图中的节点没有属性。如何选择最小节点数？提前致谢

Answer 1

I wish to select the minimum number of nodes such that the set of these nodes and their immediate edge connected neighbours comprise the whole set of n nodes

这是 Dominating Set .

由于我们可以轻松地为所有以 (u,v) 为边的节点定义 d(u,v) = 1，因此我们可以轻松地将 Vertex Cover 减少到您的问题。

因为支配集是NP-Complete ，上面是多项式约简，你的问题也是。

tl;dr:您的问题是 NP 完全问题，并且没有已知的有效解决方案来最佳地解决它。