gpt4 book ai didi

algorithm - 断开图中所有顶点的连接 - 算法

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:29:53 24 4
gpt4 key购买 nike

我正在寻找一种算法来找到最小的顶点子集,这样通过从图中删除该子集(以及连接这些顶点的边),所有其他顶点都变得不连接(即该图将没有任何边)。

  • 有这样的算法吗?
  • 如果不是:您能否推荐某种启发式方法来指定顶点。

我对图论有一定的了解,如有不妥之处请见谅。

最佳答案

IIUC,这是经典Minimum Vertex Cover问题,不幸的是,NP Complete .

幸运的是,most intuitive and greedy possible algorithm在这种情况下是最好的。

关于algorithm - 断开图中所有顶点的连接 - 算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31002559/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com