gpt4 book ai didi

algorithm - 找出 n 个节点的所有可能连通图和有向图的数量

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:49:41 24 4
gpt4 key购买 nike

你好 stackoverflow 社区,
我需要找出 n 个节点的所有可能连通图和有向图的数量。

例如:3 个节点图可以有 13 种可能的组合,它们是: Image

条件:如上图所示,
->3 节点连接图永远不会只有 1 条边,至少需要两条边来连接所有 3 个节点。所以所有节点都应该连接起来。
-> 3 个节点中的最大边数 = 6。 (见图中的第 13 号图,它有 6 个边)
->不能有自边。

同样4个节点会有199个相连的有向图。
总结:
2 个节点 = 3 个图
3 个节点 = 13 个图
4 个节点 = 199 个图
5 个节点 = 9364 个图
6 个节点 = 1530843 个图

我需要一个 F(n) 的公式,这样我就可以通过计算公式而不是进行穷举搜索来尝试每个可能的组合来获得 n 个节点的图形总数。
F(2) = 3
F(3) = 13
F(4) = 199
F(5) = 9364
F(6) = 1530843

什么是 F(n) 其中 n 可以是任何自然数?

很多天以来我一直在尝试解决这个难题,但一直无法弄清楚,所以我正在使用穷举法找出数字,但它们不可行。

最佳答案

整数序列在线百科全书 (OEIS) 对这类事情很有用。下面是此序列的链接,其中包含您可以用来了解更多信息的引用。

http://oeis.org/A003085

关于algorithm - 找出 n 个节点的所有可能连通图和有向图的数量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30411048/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com