提问人：BeeOnRope 提问时间：7/10/2016 最后编辑：BeeOnRope 更新时间：7/25/2016 访问量：957
生成具有 n 个顶点的所有 DAG
Generating all DAGs with n vertices
问：
我想生成所有具有 n 个顶点的 DAG，直至同构 - 即没有重复项的未标记 DAG。是的，我知道有很多这样的，但我最关心的是小数字（例如，n 小于 10），其中的东西仍然是可以处理的。
明显的方法，例如添加所有可能的边缘组合，有两个主要缺点：
- 这样产生的重复（同构）比唯一图多，尤其是在增长时。
n - 每个生成的图形都需要检查它是否包含循环。
答：
0赞
A_A
7/25/2016
#1
您可以从一个简单的完整图形 Kn 开始，其中 n 是图形的顺序，然后枚举其所有生成树。该算法是一种改进的 DFS，因为它使用回溯并避免桥接（以继续生成连接树），同时探索所有可能的不同组合。
根据 Cayley 的公式，在 Kn 上有（表示提升到幂）跨越树，因此您的最坏情况可能看起来像并包含重复项。n^(n-2)^9^7=4782969
这也让人想起基序检测中的一个“子问题”，对于某些算法（或这个算法），目标是生成所有 n 阶（基序）的简单连接图（不限于树），以便将图分解为这 n 个基序。所以，这些文学作品可能对你也有一些用处。
希望这会有所帮助。
评论
0赞
BeeOnRope
7/25/2016
主要问题是“重复”。我的问题还不够清楚（我现在已经添加了澄清），但主要的诀窍是避免大多数幼稚方法中固有的重复（即生成同构的 DAG）。此外，您的估计似乎不对 - 事实上，有（没有重复）20,286,025 个未标记的 DAG - 已经超过了您的 4,782,969 个（有重复） - 见A003087。n=9n=9
0赞
BeeOnRope
7/25/2016
事实上，生成树方法似乎行不通。例如，如何从（无向）生成树转到 DAG？那么，如何引导生成树的边缘，在你所拥有的位置生成微不足道的“菱形 DAG”？这样的 DAG 在其无向骨架中有一个循环，所以我看不出树的边缘（没有循环）的定向如何生成它。a -> {b, c}, {b, c} -> d
0赞
A_A
7/25/2016
这不是我的估计，我所做的只是使用凯利公式，它对某些树木进行了两次计数。但是，是的，我没有牢记“指导”。您可以使用指标标记重复项，并在发现期间拒绝它们，但这只是一种补救措施。有关 DAG 问题，请参阅基序。还有更多，因为每条边都有三个状态。我能问一下你正在解决什么样的问题吗？
0赞
BeeOnRope
7/25/2016
对不起，我应该说“推导”，而不是估计。我想生成所有可能的二进制函数链，似乎获得具有 2 度（和一些附加要求）的受限 DAG 类可以满足它。
下一个：查找多个平面的平均交点线
评论