我有一组“ n”个节点。函数返回两个节点之间的距离，使得dist（a，c）可能不是dist（a，b）+ dist（b，c）。基于阈值，我通过边缘连接某些节点。我希望选择最小数量的节点，以使这些节点的集合及其直接相连的邻居构成n个节点的整个集合。有可能找到最佳解决方案吗？在纸上乱涂乱画使我认为中心性会有所帮助（程度，亲密程度？）。我发生了聚类，但是此图中的节点没有属性。如何选择最小节点数？提前致谢
我希望选择最小数量的节点，以使这些节点的集合及其直接边缘连接的邻居构成整个n个节点的集合
这是支配集。
因为我们可以轻松地d(u,v) = 1为（u，v）是边的所有节点进行定义，所以我们可以轻松地为您的问题减少“顶点覆盖率”。
由于Domination-Set是NP-Complete，并且上面是多项式归约，所以您的问题也是如此。
tl; dr：您的问题是NP-Complete，并且没有已知的有效解决方案可以最佳地解决该问题。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句