17

我有这个问题。我有一个 n 节点图，我想将其拆分为 x 节点和 nx 节点的两个子图，但要受到剩余边数最大化（或最小化被切割边数）的约束。

不确定这是否有意义。不是图论专家，但这是我问题的抽象版本。我应该看看哪些算法可能对我有帮助？

这不是作业问题。虽然我认为有趣的问题！

我计划在 C 中实施。

4

3 回答 3

11

x = n - x 的特殊情况称为最小二分问题并且是 NP-hard。这也使您的问题成为 NP 难题。Wikipedia article on graph partitioning中描述了几种启发式方法，包括局部搜索（例如，从随机切割开始并重复交换减少切割大小的顶点对）和谱方法（例如，计算和阈值第二个特征向量）。如果 n 很小，整数规划也是一种可能。

于 2012-04-17T12:42:38.797 回答
2

也许是对节点的深度优先搜索。我们一次分配一个节点并计算到目前为止的切割次数。如果该数字超过最佳解决方案的数字，则我们中止该数字并回溯。

  1. 给定完整的节点集 S，让 P 和 P' 是节点的集合，初始为空，K 为切割边的数量，初始为 0。
  2. 让 S*, K* 是最知名的解决方案及其切割边数，K* 最初为无穷大。
  3. 选择一个节点 N 开始并将其分配给 S。
  4. 对于每个未分配的节点 M：
    1. 将 M 分配给 S'，并将从 M 到 S 到 K 中的节点的边数相加。
    2. 如果 K > K*，则没有基于此的解决方案会击败最好的解决方案，因此将 M 分配给 S。
    3. 如果 |S| > X，那么集合变得太大了；回溯。
    4. 否则，从 4 递归。
  5. 如果所有节点都已分配且 K < K*，则令 S* = S 且 K* = K。

我一直把它想象成一个 Prolog 类型的算法，但是在 C 中做它应该不会太难。回溯只是意味着取消分配最后分配的节点。

于 2012-04-17T06:08:15.867 回答
0

基本上，您正在查看最小切割问题的修改版本。

一种方法是修改karger 的算法 在 Karger 的算法中，您沿着随机边收缩顶点，直到最终只有两个顶点，其余边代表切割。由于它是随机的，因此您只需多次执行此操作并保持解决方案的边缘最少。

在修改后的版本中，一旦顶点折叠 x 次，您就可以停止折叠并计算出边（在您的情况下，这些将是切口），执行适当的次数，您就有了解决方案。棘手的部分是弄清楚重复计算多少次以将置信度提高到令人满意的极限

于 2012-04-17T06:56:57.873 回答