随机图分区

Question

我正在尝试测试一些图形分区模型(这些模型来自现实世界,图形缓慢地自我分区).为此,我需要能够将此图一致地随机分割为连续的组件(我们最初连接图表).如果不需要连续性标准,我相信这将是随机分组的问题,可以进行组合分析.有没有人知道将图形随机分割成子图的任何方法(即随机抽样一个分区),或者,如果不知道这样的方法,可以随机抽样一组元素？随机化分区数然后随机化成员资格的方法将不起作用,因为每个分区大小存在不同数量的可能分区.

Answer 1

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