algorithm - 生成强连接、均匀分布、随机的有向图

Question

所以我一直在构建一个程序，该程序使用蒙特卡罗模拟来寻找进化图论的属性。它的一个关键功能是能够生成均匀分布的随机图，这样我们就可以确定图的广义性质。对于连接无向图的情况，我已经实现了 this 中概述的解决方案回答。

然而，对于有向图，生成从 Wilson 算法获得的单向均匀生成树并不能确保该图是强连通的，而且似乎添加额外的边以使生成树成为双向的会引入对您生成的图表的偏见。

我觉得我可能遗漏了一些明显的东西/误解了一些东西，但基本上我的要求是，有人可以向我推荐一个高级方案，让我能够生成强连接、均匀分布、随机的有向图吗？

Answer 1

Can someone recommend to me a high-level scheme that allows me to generate strongly-connected, uniformly-distributed, random di-graphs?

我在为测试数据生成表达式树时遇到了类似的问题。我发现如果你知道如何计算独特的树那么问题就变得简单了。我的意思是，我发现对于具有 N 个内部节点的完整二叉树，基于 N 的唯一树的数量是 Catalan Numbers .然后对于具有 N 个总节点的一元分支的二叉树，基于 N 的唯一树的数量是 Motzkin Numbers .

然后我找到The On-Line Encyclopedia of Integer Sequences® .因此，如果您知道一个值 N，它可以唯一地标识一个图，并且您知道该 N 的唯一图的相应计数，并将这些计数放入 OEIS 搜索中，您应该会得到一个有助于您搜索的页面。例如Catalan Numbers对于完整的二叉树或 Motzkin Numbers对于常规二叉树。一路上我发现生成它们的关键之一是 recurrence relation .

或者您可以在搜索中使用关键字，但这可能无法准确匹配。我只使用数字序列而不是关键字找到 Motzkin 数字。

这是一个 OEIS 查询 strongly connected digraph

现在，如果您知道给定 N 的计数，并且您可以为给定 N 生成所有图表，或者可以在值和图表之间建立一对一的对应关系，那么您只需生成随机整数并获取/生成相应的图表.如果我正确理解你的问题，这应该可以解决它。

我对这个问题的 OEIS 序列的最佳猜测是:

具有 n 个未标记节点的非循环有向图的数量。 A003087

其中引用了 Uniform random generation of large acyclic digraphs

长话短说

有关一些相关历史，请参阅我的问题:Algorithm improvement for enumerating binary trees