我有这个问题。我有一个 n 个节点的图，我想将其分成 x 个节点和 n-x 个节点的两个子图，但要遵守剩余边数最大化(或最小化被切割的边数)的约束。
不确定这是否有意义。不是图论专家，但这是我的问题的抽象版本。我应该研究哪些算法可能对我有帮助？
这不是作业问题。我认为这是个有趣的问题!
我计划在 C 中实现。
最佳答案
x = n - x 的特殊情况称为最小二分问题并且是 NP-hard。这也使您的问题成为 NP-hard。维基百科关于 graph partitioning 的文章中描述了几种启发式方法。 ，包括局部搜索(例如，从随机切割开始并重复交换减少切割大小的顶点对)和谱方法(例如，计算和阈值第二个特征向量)。如果 n 很小，整数规划也是可能的。
关于algorithm - 图论 : Splitting a Graph，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10185773/