生成随机双连图

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。

因此，最后要确保你的图形真正是双连接的，你只需运行你已经知道的常规程序。

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

真正有趣的问题是“为什么我会得到一个biconnected图表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，因为所考虑的顶点不是两组中的任何一组...我只是说这些东西来说明一个人仍然需要为正式证据担心的细节......）

Answer 2

一种简单的方法是创建一个随机的最大平面（三连通）图：

• 从在一个循环中连接的3个顶点开始，形成2个三角形面（循环的内部和外部）。
• 要添加每个后续顶点，请选择一个随机面，并将其与顶点和3个边相同。

你可以在这里停下来 - 因为图表是三连接的，它也是双连接的。

但是，如果要删除边缘并确保仍然具有双连通图形，则仅删除两个入射顶点均为3度或更多度的边缘，并在移除之前使用Hopcroft & Tarjan's Depth-First Search Algorithm to find Biconnected Components测试每个边缘以检查没有该边缘的双向性。

注意 - 这将始终创建一个平面图。