图形理论：分割图形

我有这个问题。我有一个包含n个节点的图，我想将其分解为x个节点和n-x个节点的两个子图，但需要约束剩余边数最大化（或最小化切割边的数量）。图形理论：分割图形

不知道这是否合理。不是一个图论的人，但这是我的问题的抽象版本。我应该看看哪些算法可以帮助我？

这不是一个家庭作业问题。虽然我觉得有趣的问题！

我打算在C中实现。

来源

2012-04-17 JoshDG

x是一个参数还是只是寻找2个子图？如果x不是一个参数，是不是只需要寻找具有最少边数的节点并将其从图中删除？ – brianestey 2012-04-17 05:53:14

是的..抱歉，我应该让这个更清楚。假设x是10，总节点是25.我需要两个图，一个有10个节点，另一个有15个，通过“切割”最少数量的边。 – JoshDG 2012-04-17 05:54:56

绝对是一个有趣的问题。实际上，我关于寻找单个节点的第一个假设是错误的 - 我想出了一个不正确的图。祝你找到解决方案！ – brianestey 2012-04-17 06:06:51

其中x = n-x称为最小二等分问题并且是NP难度的特殊情况。这也使得你的问题非常困难。在维基百科文章graph partitioning中描述了几种启发式算法，包括局部搜索（例如，开始于随机剪切并反复交换减少剪切大小的顶点对）和频谱方法（例如计算和阈值第二特征向量）。如果n很小，整数编程也是一种可能。

来源

2012-04-17 12:42:38 uty

这就是答案。 – 2012-04-17 12:49:09

哎呀。对于非计算机科学家来说，可能太高级了。如果x很小，使用遗传算法可能会更好吗？只需取一堆x = 10的随机集合，对于图分成两部分的情况，就最小切割而言，取前10％，然后将这些变为一代？你认为这可能有效吗？或者，它完全取决于数据集。我想我也可以尝试一下。 – JoshDG 2012-04-17 15:29:29

本地搜索很容易实现：只需从剪辑开始，并尝试通过稍作更改来改进。计算特征向量并不算太坏，但确实需要一些数学知识。整数编程很难，但有免费的库。我不喜欢组合问题的遗传算法，但是如果你愿意投入足够的周期，它们可能比本地搜索更好。 – uty 2012-04-17 16:14:31

也许深度首先搜索节点。我们一次分配一个节点，并统计到目前为止的切割次数。如果这个数字超过了最佳解决方案的数量，那么我们放弃这一个并且回溯。

给予了充分的节点集合S的，让P和P”是节点的setsuts，最初是空的，和K的切割边缘的数量，初步0
令S *，K *是最知名的解决方案和它的切边数量，K *最初是无限的。
选择一个节点N开始与和其分配给S.
对于每个未指定的节点M：
1. 分配M至S”，并从M个S中添加的边缘的数目，以节点K.
2. 如果K> K *，那么没有基于此的解决方案将击败最好的，因此将M分配给S.
3. 如果| S | > X，那么这个集合变得太大了;原路返回。
4. 否则，从4
递归如果所有节点分配和K < K *，然后让S * = S和K * = K.

我一直在想象这个作为Prolog类型的算法，但在C中执行它不应该太难。回溯只意味着取消分配最后分配的节点。

来源

2012-04-17 06:08:15 Edmund

基本上，您正在查看min-cut问题的修改版本。

一种方法是修改karger's algorythm 在Karger的算法中，您沿着随机边收缩顶点，直到最终只有两个顶点，其余边表示切割。既然它是随机的，你只需要做很多次这样的操作，并且在切割中保留最少边的解决方案。

在修改后的版本中，一旦顶点折叠了x次，您可以停止折叠并计算出口边缘（这将成为您的案例中的切入点），执行适当的时间，并且您有一个解决方案。棘手的部分是计算出多少次重复计算以将置信度提高到令人满意的极限

来源

2012-04-17 06:56:57 AntonioD

最小切割问题没有固定'x' [切割边的一个顶点的数量]，并且具有特定的'source'和'sink'。如果你想减少问题，请将其添加到答案中。 – amit 2012-04-17 07:02:16

我认为对Karger's的某种修改可以解决这个问题。最小切割问题本身没有水槽和源，只是有些algorythms将问题减少到最大流量问题。我会编辑答案，如果我能想出一个很好的修改卡尔的处理固定的x案件（有一个明显的方法，但不知道它给出正确的结果） – AntonioD 2012-04-17 07:29:06

图形理论：分割图形

回答

相关问题