随机图分区

Question

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

Answer 1

您必须区分edge-cut partitioning和vertex-cut partitioning，其中沿着边或顶点划分图。这会显着影响您的问题，因为不同顶点切割的数量远大于边缘切割的数量。原因在于，您只将顶点分配给顶点切割中的分区 - 与将顶点分配给分区的边缘切割相反 - 并且边数多于顶点（例如n个顶点的O（n^2）边）。因此，组合较大的顶点切割导致需要检查连通性的更多数量的子图。一种天真的随机化方法是枚举所有分区，迭代选择一个分区，并检查选定分区中所有子图的连通性。那你就拿第一个。在这种情况下，所有的解都有相同的概率（均匀随机）。