graph - 生成随机双连通图

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) 对顶点，这也将是该算法的预期运行时间，因为此过程生成的random graph将是双连接的with high probability。

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

对于检查返回“图形不是双连接”的(非常不可能的)场景，只需重复该过程。

真正有趣的问题是“为什么我会得到一个双连通图 w.h.p.？”。我将省略有点乏味的正式证明，并且根据您的询问方式，我假设您只想要一些有效的东西，而您不太关心它为什么有效。如果我错了并且您确实需要证据，我建议您要么在mathoverflow上询问，要么给我留言-如果我有时间，也许我会尝试使其正式化。

目前，只是为了让您直观地了解为什么这会起作用，请考虑以下证明如何进行的方法:

注意，非双连通图的数量等于至少有一个关节顶点的图的数量。

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

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