图论：分割图

Question

我有这个问题。我有一个由n个节点组成的图，我想将其分成两个子图，一个包含x个节点，另一个包含n-x个节点，同时满足保留边数最大化（或者最小化切断的边数）的约束。

不确定是否清楚。虽然不是图论专家，但这是我的问题的抽象版本。我应该查看哪些算法能够帮助我呢？

这不是一道作业题。我认为这是一个有趣的问题！

我计划使用C来实现。

- JoshDG

---

x是一个参数还是你只是在寻找2个子图？如果x不是一个参数，那么你不会只是寻找边数最少的节点并将其从图中割掉吗？ - brianestey

是的。。对不起，我应该表述得更清楚一些。假设x为10，总节点数为25。我想要两个图，一个有10个节点，另一个有15个节点..通过“减少”最少数量的边来实现。 - JoshDG

这绝对是一个有趣的问题。实际上，我最初寻找单个节点的假设是错误的 - 我构建了一个图形，在那里这不成立。祝你好运找到解决方案！ - brianestey

请注意，您所描述的问题不一定有唯一的解决方案。想象一个由四个节点组成的简单正方形图形，并选择x为2。剪切上下边缘并不明显比剪切左右边缘更好。您需要正式定义边缘剪切的优先级（也许基于节点顺序），或以其他方式管理这样一个事实，即存在一组同样正确的解决方案。 - HostileFork says dont trust SE

如果x沒有固定，這就是一個最小割問題，其解決方案是使用最大流。我從未遇到過固定x的問題，也不熟悉任何解決方法。 - Ivaylo Strandjev

你的问题与你计划实现的编程语言无关，对吧？移除 C 标签。 - Jens Gustedt

Answer 1

当 x = n - x 时，这被称为最小二分问题，并且是NP难问题。 这也使得您的问题成为NP难问题。在维基百科关于图分区的文章中描述了几种启发式方法，包括局部搜索（例如，从随机切割开始，并重复交换减少切割大小的顶点对）和谱方法（例如，计算并阈值化第二特征向量）。 如果 n 很小，整数规划也是一种可能性。

- uty

---

哎呀，对于非计算机科学家来说可能太高级了。如果x很小的话，使用遗传算法可能更好？只需取一堆随机的x=10集合，对于图被分成恰好两部分的情况，取最小割的前10％，然后对这些进行多代变异？你认为这样有效吗？还是完全取决于数据集。我想我不妨试试看。 - JoshDG

本地搜索很容易实现：只需从一个简单的版本开始，然后通过进行小的更改来改进它。计算特征向量并不太难，但需要一些数学知识。整数规划很困难，但有免费的库可用。我不太喜欢用遗传算法解决组合问题，但如果你愿意投入足够的计算资源，它们可能比本地搜索更好。 - uty

其实我已经能够编写一个简单的分支定界算法，对于我的特定问题非常有效...不过我还是会接受你的答案，因为它显然是正确的，尽管我不太理解。我会为了好奇心去研究一下特征向量。谢谢！ - JoshDG

Answer 2

也许可以对节点进行深度优先搜索。我们逐个分配节点并计算到目前为止的切割数量。如果该数字超过了最佳解决方案的数字，则我们放弃这个方案并回溯。

1. 给定完整的节点集S，让P和P'成为节点集，最初为空，K为切割边的数量，最初为0。 2. 让S*，K*成为最佳已知解决方案及其切割边数，其中K*最初为无穷大。 3. 选择一个起始节点N并将其分配给S。 4. 对于每个未分配的节点M： a. 将M分配给S'，并将从M到S中节点的边数添加到K中。 b. 如果K > K*，则基于此方案的任何解决方案都不会打败最佳解决方案，因此将M分配给S。 c. 如果|S| > X，则集合已经变得太大，请回溯。 d. 否则，从步骤4开始递归。 5. 如果所有节点都已分配且K < K*，则让S* = S且K* = K。

我一直在想象这是一种Prolog类型的算法，但在C中实现也不难。回溯意味着取消分配最后一个分配的节点。

- Edmund

Answer 3

基本上你正在看一个修改版的最小割问题。

一种方法是修改Karger算法 在Karger算法中，您沿着随机边缩小顶点，直到最终只剩下两个顶点，剩余的边代表割。由于这是随机的，因此您只需多次执行此操作并保留割中边最少的解决方案即可。

在修改后的版本中，一旦顶点被折叠x次，您可以停止折叠并计算出度边数（这些将是您的割），适当地执行多次，就可以得到一个解决方案。棘手的部分是确定重复计算的次数，以增加信心至令人满意的程度。

- AntonioD

---

最小割问题没有固定的“x”（切割一侧的顶点数），并且具有特定的“源”和“汇”。如果您已经想到了最小割问题的简化方法，请在回答中添加。 - amit

我认为对Karger算法进行某种修改可以解决这个问题。在最小割问题中本质上没有汇点和源点，只是一些算法将问题简化为最大流问题。如果我能想出一个处理固定x情况的好的Karger算法修改方法，我会编辑答案（有一种明显的方法，但不确定它是否能给出正确的结果）。 - AntonioD