生成随机双连图

Question

是否有一种简单的算法来生成随机无向双向图(给定多个顶点作为输入)？我理解如何确定给定的图是否是双连的,但我正在努力以编程方式生成一个图.

Answer 1

您可以采用非常简单的概率方法：

1. Create an empty graph with n nodes
2. For each pair of nodes:
 -Flip a fifty-fifty-coin to decide whether to put an edge in there or not

您有 O(n^2) 对顶点（即可能的边），这也将是该算法的预期运行时间，因为该过程生成的随机图将以高概率双连接。

因此，最后为了确保您的图确实是双连接的，您只需运行您已经知道的常规程序即可。

对于检查返回“图不是双连接”的（极不可能的）情况，只需重复该过程即可。

真正有趣的问题是“为什么我会得到一个双连通图 whp？”。我将省略正式的证明，这有点乏味，并且根据您的提问方式，我假设您只是想要一些有效的东西，并且您不太关心它为什么有效。如果我错了，而你实际上需要一个证明，我建议你要么在mathoverflow上提问，要么给我发表评论——如果我有时间的话，也许我会尝试将其正式化。

目前，为了让您直观地了解为什么这会起作用，请考虑以下证明的方法：

• 请注意，非双连通图的数量等于具有至少一个铰接顶点的图的数量。

• 让我们粗略地计算单个顶点作为关节点的概率：这个想法是，如果v是一个关节点，那么它将顶点分成n 两个大小不相交的集合k，并且n-k这些集合之间没有边。现在直观上应该或多或少清楚的是，k*(n-k)抛硬币都必须导致“无边”的可能性不大（基本上(1/2)^(k*(n-k))）。我们仍然必须乘以n（因为对于每个节点），但这仍然不会产生显着差异，正如您现在可能看到的那样，具有足够大“n”的图不太可能不被双连接。

（仍然缺少的是考虑“对于每个可能的分区”，即对于 的不同选择k，然后可能会更加小心，因为它实际上是((n-1)-k)和k，而不是(n-k)和k因为所考虑的顶点不属于 2 个中的任何一个集......我只是说这些事情来说明人们仍然需要担心正式证明的细节......）