graph - 随机图分区

Question

我正在尝试测试一些图形分区模型（这些模型来自现实世界，其中图形缓慢地自我分区）。为此，我需要能够将此图均匀地随机划分为连续的组件（我们得到的图最初也是连接的）。如果不需要连续性标准，我相信这将是随机划分集合的问题，可以组合分析。有谁知道将图随机划分为子图的任何方法（即随机抽样一个分区），或者，如果不知道这种方法，随机抽样一组元素？随机化分区数量然后随机化成员资格的方法将不起作用，因为每个分区大小都有不同数量的可能分区。

Answer 1

您必须区分边缘切割分区和顶点切割分区，您可以在其中沿边或顶点划分图形。这会显着影响您的问题，因为不同顶点切割的数量远大于边缘切割的数量。原因是您在顶点切割中专门将边分配给分区 - 与将顶点分配给分区的边切割相反 - 边比顶点多得多（例如，对于 n 个顶点，O(n^2) 边）。因此，组合上更大的顶点切割会导致需要检查连接性的子图数量更多。一种简单的随机化方法是枚举所有分区，迭代地选择一个分区，并检查所选分区中所有子图的连通性。然后你就拿第一个。在这种情况下，所有解决方案具有相等的概率（一致随机）。