dl1*_*101 10 random algorithm directed-graph motzkin-numbers
所以我一直在构建一个程序,使用蒙特卡罗模拟来找到进化图论的属性.其中一个关键功能是能够生成均匀分布的随机图,以便我们可以确定图的广义属性.对于连接无向图的情况,我已经实现了本答案中概述的解决方案.
然而,对于有向图,生成从Wilson算法得到的单向均匀生成树并不能确保图形是强连通的,并且似乎添加额外的边缘以使生成树双向会引入偏差您生成的图表.
我觉得我可能会遗漏一些明显/误解的东西,但基本上我的要求是,有人可以向我推荐一个高级方案,允许我生成强连接,均匀分布的随机图吗？
\n\n\n有人可以向我推荐一个高级方案，使我能够生成强连接、均匀分布的随机有向图吗？
\n
我在为测试数据生成表达式树时遇到了类似的问题。我发现，如果你知道如何计算独特的树，那么问题就变得很容易。我的意思是，我发现对于具有 N 个内部节点的完整二叉树，基于 N 的唯一树的数量是加泰罗尼亚数字。那么，对于具有总共 N 个节点的一元分支的二叉树，基于 N 的唯一树的数量就是Motzkin Numbers。
\n\n然后我找到了The On-Line Encyclopedia of Integer Sequences\xc2\xae。因此，如果您知道一个值 N，它可以唯一地标识一个图形，并且您知道该 N 的唯一图形的相应计数，并将这些计数放入 OEIS 搜索中，您应该会得到一个可以帮助您进行搜索的页面。例如，完整二叉树的加泰罗尼亚数或规则二叉树的莫茨金数。一路上我发现生成它们的关键之一是递归关系。
\n\n或者您可以在搜索中使用关键字，但这可能不会获得准确的命中。我只使用数字序列而不是通过关键字找到 Motzkin 数字。
\n\n这是强连通有向图的 OEIS 查询
\n\n现在，如果您知道给定 N 的计数，并且可以生成给定 N 的所有图形，或者可以在值和图形之间建立一一对应关系，那么您只需生成随机整数并获取/生成相应的图形。如果我正确理解你的问题，这应该可以解决它。
\n\n我对这个问题的 OEIS 顺序的最佳猜测是：
\n\n具有 n 个未标记节点的无环有向图的数量。A003087
\n\n其中参考了大型无环有向图的均匀随机生成
\n\n有关一些相关的历史记录，请参阅我的问题：枚举二叉树的算法改进
\n