生成强连接、均匀分布、随机的有向图
Generating strongly-connected, uniformly-distributed, random di-graphs
所以我一直在构建一个程序，该程序使用 Monte Carlo 模拟来寻找进化图论的属性。它的一个关键功能是能够生成均匀分布的随机图，这样我们就可以确定图的广义性质。对于连接无向图的情况，我已经实施了 this 答案中概述的解决方案。
然而，对于有向图，生成从 Wilson 算法获得的单向均匀生成树并不能确保该图是强连通的，并且似乎添加额外的边以使生成树成为双向的会在您生成的图表中引入偏差。
我觉得我可能遗漏了一些东西 obvious/misunderstanding 一些东西，但本质上我的要求是，有人可以向我推荐一个高级方案，使我能够生成强连接的、均匀分布的、随机的二向图？
我能想到的最直接的解决方案是随机生成均匀分布的有向图并拒绝任何非强连接的有向图。这将保持均匀分布并保证您想要的 属性 。它可能不是非常有效，但如果你 运行 一些测试你就会确定。
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. Then for binary trees that have unary branches with N total nodes the number of unique trees based on N is the Motzkin Numbers。
然后我找到了The On-Line Encyclopedia of Integer Sequences®. So if you know a value, N, that can uniquely identify a graph and you know the corresponding count of unique graphs for that N and put those counts into a the OEIS search you should get back a page that will help you in your search. e.g. Catalan Numbers for full binary trees or Motzkin Numbers for regular binary tress. Along the way I found that one of the keys to generating them was a recurrence relation。
或者您可以在搜索中使用关键字，但这可能无法准确匹配。我只使用数字序列而不是关键字找到 Motzkin 号码。
的 OEIS 查询
现在，如果您知道给定 N 的计数，并且您可以为给定 N 生成所有图表，或者可以在值和图表之间建立一对一的对应关系，那么您只需生成随机整数和 get/generate 对应的图。如果我正确理解你的问题，这应该可以解决它。
我对这个问题的 OEIS 序列的最佳猜测是：
具有 n 个未标记节点的非循环有向图的数量。 A003087
其中引用了 Uniform random generation of large acyclic digraphs
TL;DR
一些相关的历史见我的问题：
所以我一直在构建一个程序，该程序使用 Monte Carlo 模拟来寻找进化图论的属性。它的一个关键功能是能够生成均匀分布的随机图，这样我们就可以确定图的广义性质。对于连接无向图的情况，我已经实施了 this 答案中概述的解决方案。
然而，对于有向图，生成从 Wilson 算法获得的单向均匀生成树并不能确保该图是强连通的，并且似乎添加额外的边以使生成树成为双向的会在您生成的图表中引入偏差。
我觉得我可能遗漏了一些东西 obvious/misunderstanding 一些东西，但本质上我的要求是，有人可以向我推荐一个高级方案，使我能够生成强连接的、均匀分布的、随机的二向图？
我能想到的最直接的解决方案是随机生成均匀分布的有向图并拒绝任何非强连接的有向图。这将保持均匀分布并保证您想要的 属性 。它可能不是非常有效，但如果你 运行 一些测试你就会确定。
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. Then for binary trees that have unary branches with N total nodes the number of unique trees based on N is the Motzkin Numbers。
然后我找到了The On-Line Encyclopedia of Integer Sequences®. So if you know a value, N, that can uniquely identify a graph and you know the corresponding count of unique graphs for that N and put those counts into a the OEIS search you should get back a page that will help you in your search. e.g. Catalan Numbers for full binary trees or Motzkin Numbers for regular binary tress. Along the way I found that one of the keys to generating them was a recurrence relation。
或者您可以在搜索中使用关键字，但这可能无法准确匹配。我只使用数字序列而不是关键字找到 Motzkin 号码。
的 OEIS 查询现在，如果您知道给定 N 的计数，并且您可以为给定 N 生成所有图表，或者可以在值和图表之间建立一对一的对应关系，那么您只需生成随机整数和 get/generate 对应的图。如果我正确理解你的问题，这应该可以解决它。
我对这个问题的 OEIS 序列的最佳猜测是：
具有 n 个未标记节点的非循环有向图的数量。 A003087
其中引用了 Uniform random generation of large acyclic digraphs
TL;DR
一些相关的历史见我的问题：