gpt4 book ai didi

c++ - 将图拆分为 2

转载 作者:搜寻专家 更新时间:2023-10-31 01:40:36 25 4
gpt4 key购买 nike

我们如何将加权图分成 2 个相等的两半(两半包含相同数量的顶点),使得删除边的总和最小?

最佳答案

您正在考虑的问题属于“图形分区”的标题。几乎任何变体都至少是 NP 完全的(除非你的图有一些特殊的属性可以帮助你),所以如果你的图是非常大的,你可能不得不求助于近似启发法。从实用的角度来看,我建议只使用一些现有的库。维基百科页面提供了一个开源包列表,至少其中一些非常复杂。

http://en.wikipedia.org/wiki/Graph_partition

关于c++ - 将图拆分为 2,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29578574/

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