随机图分割

Question

我正在尝试测试一些图分区模型（这些模型来自现实世界，在那里图慢慢地自我分区）。为了做到这一点，我需要能够将该图均匀随机地分成连续的组件（我们已知最初该图是连接的）。如果不需要连续性标准，我认为这将是随机分割集合的问题，可以进行组合分析。是否有人知道任何一种方法可以随机地将图形分割为子图（即随机抽样一个分区），或者如果没有这种方法，则随机抽取一组元素？随机化分区数，然后随机化成员资格的方法行不通，因为每个分区大小都有不同数量的可能分区。

- jclancy

---

对于“...随机抽样一组元素？”，您可以参考此帖子：https://dev59.com/KF_Va4cB1Zd3GeqPTncZ - OmG

Answer 1

您需要区分边切割分区和点切割分区，其中您沿着边或顶点将图形分割。这对您的问题有重大影响，因为不同顶点切割的数量比较边切割要大得多。原因是在顶点切割中，您专门将边分配给分区 - 与边切割相反，在那里您将顶点分配给分区 - 并且边比顶点多得多（例如，对于n个顶点有O（n ^ 2）条边）。因此，组合更大的顶点切割会导致必须检查连通性的子图数量更多。随机化的一种朴素方法是枚举所有分区，迭代选择一个分区，并检查所选分区中所有子图的连通性。然后您只需选择第一个解决方案。在这种情况下，所有解决方案具有相等的概率（均匀随机）。

- mac7

Answer 2

我在工作中遇到了相同的问题。我有两种方法来将一个图随机分成m个连续的组件：

1. 生成树法。随机选择一个生成树（例如使用Wilson算法，在所有生成树中均匀选择）。然后随机选择m-1条边（不重复）并从生成树中删除它们。这将给出m个组件，每个组件在原始图中都是连接的。

2. 边缩法。随机选择一条边并将其缩小，将（新）顶点重新命名为两个先前顶点的联合。重复此过程，直到只剩下m个顶点。将每个顶点与被缩小成它的（原始）顶点子集进行标识。

- blucena