生成一个大型的随机平面图。

Question

24

如何高效地生成一个大规模（约 300k 个顶点）的随机平面图（这里的“随机”是指均匀分布）？

- Marat Salikhov

“均匀分布”是什么意思？你是指从具有M个节点的N个平面图集合中以1/N的均匀概率选择吗？你是否了解即使对于十几个节点，N也有多么 astronomically huge 的数量级？ - Spacedman

5个回答

8

另一个可能性是随机选择坐标，然后计算Delaunay三角剖分，它是一个平面图（看起来也很好看）。请参见http://en.wikipedia.org/wiki/Delaunay_triangulation。有O(n log(n))的算法可用于计算这样的三角剖分。

- Ivo Blöchliger

但它的度数是固定的3吗？ - andrew cooke

1

它不会有固定的三度，但它将是平面的。 - Ivo Blöchliger

3

答案不正确。这种方法无法给出所需的均匀分布。 - user2316602

1

这只会生成长度为3的无弦圈（即三角形循环）的图表，这可能并不总是理想的。 - a52

3

没有其他要求的话，我建议您搜索随机迷宫生成。如果您希望图形中有循环，可以随机从简单迷宫中删除一些墙壁。迷宫中的交叉点成为您图形中的节点，而删除的墙壁则成为边缘。这意味着您可以通过选择迷宫的大小来选择节点数。

通常情况下，迷宫是在二维网格上完成的，每个点最多有4个连接，但是并没有什么阻止您在六边形瓦片或其他东西上做迷宫。

- phkahler

2

如果您所说的“均匀”是指在空间中均匀分布，那么这是我为生成用于空间生态/进化模拟器的平面图开发的一种非常快速的算法。它将生成具有您指定的期望度数的随机平面图，当然会有一些变化。如果您想要平面图中的均匀随机度数，可以扩展它以基于均匀随机数选择期望度数。

- LuisZaman

3

这个算法似乎可以生成边相交的图形？这不是一个平面图。例如，如果在给定半径的圆上有4个点，则它们将彼此连接，对角线将相交，从而使图形成为非平面图。 - Sid Datta

1

首先，可以尝试生成一个满足类似平面图的限制（例如，边数≤3*顶点数-6）的随机图，并使用Tarjan的平面性检测算法在O(n)时间内检查它是否为平面图。如果不是平面图，则再次生成。但是对于300K个顶点来说，不确定效率会有多高！而且也不确定它能否给出具有均匀概率的图形。

有一些关于生成平面图的文献，可以在这里找到一篇论文：Generating Labeled Planar Graphs，其运行时间为O(n^4)，但可能并不值得一试。也许那里的参考文献可以帮助您找到一些有用的内容。

祝您好运！

- Aryabhatta

4

几乎所有的随机图都不是可平面图吧？ - andrew cooke

1

随机图仅以指数小的概率为平面图，这意味着建议的算法具有指数时间复杂度！唉，随机图与平面图具有完全不同的结构（例如，谱特性）。 - user2316602

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Valentas · Accepted Answer

你看过Boltzmann采样吗？可以看一下Eric Fusy的论文《线性时间内平面图的均匀随机抽样》。他的主页上提供了论文和实现，据论文介绍，该实现可以在几秒钟内生成大小为100K的实例。