math - 找到可以由给定节点集形成的不同未标记树的公式是什么？

Question

我只是在做一个项目的研究，遇到了一个问题。如果有人能帮助我解决这个问题，我将不胜感激。考虑下图：

两个点用一条线连成一个图，三个点用单线连成一个图，不管你怎么连点，结果都是一样的。但是当我们增加点时，会有不同的可能性，如四个点所示。

是否有计算一组节点可以形成的未标记树的数量的公式？

Answer 1

正如评论中所建议的，您的问题可以表述为确定 n 个顶点上未标记树的数量。请注意，这与计算标记树（其中有 n^{n-2}）或标记图（其中有 2^\binom{n}{2}）的问题有很大不同。

整数序列在线百科全书有很多关于这个问题的好数据（包括生成序列的代码）：https ://oeis.org/A000055 。特别是，它为这些数字提供了一个生成函数 A(x)，这是迄今为止已知的最佳解决方案（从数学家的角度来看）：

A(x) = 1 + T(x) - T^2(x)/2 + T(x^2)/2，其中 T(x) = x + x^2 + 2x^3 + ...

如果您不熟悉生成函数，请将其视为精心设计的多项式，其系数形成所需的序列。也就是说，这个多项式中 x^n 的系数将是 n 个顶点上未标记树的数量。

作为最后的插件，您可能会发现此参考很有用： http: //austinmohr.com/work/trees。它为最多十个顶点的树提供了一些计数和图像。

Answer 2

这是非同构图计数问题。

对于一般情况，顶点上有 2^( ⁿ ₂ ) 个非同构图，其中 ( ⁿ ₂ ) 是二项式系数“n 大于 2”。n

但是，这可能还会为您提供一些额外的图表，具体取决于哪些图表被认为是相同的（您也不是 100% 清楚哪些图表适用）。

见这篇论文。 还有这篇关于 MathWorld的文章。

编辑：如果你想计算标记的树只有公式是n^(n-2).

维基百科。