8个顶点的树，在不同构下有多少棵？

8个顶点的树，在不同构下的棵树数目为14棵。

这个结果可以通过Cayley定理得到。Cayley定理指出，n个节点的标号不同的有根树的个数为n^(n-1)。因此，8个节点的有根树的个数为8^7=2097152。

但是，这里的问题要求的是无根树，因此需要对有根树的个数进行调整。对于一棵无根树，可以从中选择一个顶点作为根，这样就可以得到一棵有根树。因此，一棵无根树对应着n个有根树，因此8个节点的无根树的个数为2097152/8=262144。

由于对于任意一棵无根树，都可以通过重新标号的方式得到唯一的一棵树，因此需要对262144个无根树进行去重。最终得到的无根树的个数为14棵。

相关问题

具有四个顶点的不同构的无向图有多少个

具有四个顶点的无向图共有 $\binom{4}{2}=6$ 条边可以选择或不选择。对于每条边，都可以选择是否在图中存在，因此总共有 $2^6=64$ 种可能的边集合。但是，有些边集合可能对应同构的图，因此需要去除这些重复的情况。

首先考虑没有边的情况，这是一个孤立的点集，只有一种情况。

接下来考虑只有一条边的情况。共有 $6$ 条边可选，但是每个图只有一条边，因此共有 $6$ 种情况。

再接下来考虑有两条边的情况。我们可以将这两条边分别标记为 $1$ 和 $2$。共有 $\binom{6}{2}=15$ 种选择两条边的方式，但是有些选择是等价的，例如选择了边 $1$ 和边 $2$，和选择了边 $2$ 和边 $1$ 是等价的。实际上，我们只需要考虑选择编号更小的那条边作为边 $1$，另一条边作为边 $2$，因此实际上只有 $15/2=7.5$ 种不同的选择方式。对于每种选择方式，要使得图不同构，边 $1$ 和边 $2$ 必须连接不同的顶点。因此，对于每种选择方式，有 $4\times 3=12$ 种不同的边连接方式。因此，总共有 $7.5\times 12=90$ 种不同的图。

最后考虑有三条边的情况。我们可以将这三条边分别标记为 $1$，$2$ 和 $3$。共有 $\binom{6}{3}=20$ 种选择三条边的方式，但是有些选择是等价的，例如选择了边 $1$，边 $2$ 和边 $3$，和选择了边 $3$，边 $2$ 和边 $1$ 是等价的。实际上，我们只需要考虑选择编号更小的那条边作为边 $1$，另外两条边按照编号递增的顺序排列，因此实际上只有 $20/6=3.33$ 种不同的选择方式。对于每种选择方式，要使得图不同构，边 $1$ 必须连接两个不同的顶点，边 $2$ 和边 $3$ 必须连接另外两个不同的顶点。因此，对于每种选择方式，有 $4\times 3\times 2=24$ 种不同的边连接方式。因此，总共有 $3.33\times 24=80$ 种不同的图。

综上所述，具有四个顶点的不同构的无向图共有 $1+6+90+80=177$ 个。

什么是生成树？生成树有什么特点？生成树有几个顶点？几条边？

生成树是指一棵无向图的一种生成方式，它包含了该无向图的所有顶点，并且是该无向图的一个极小连通子图，即在保证连通的前提下，去掉任意一条边都会使其不连通。

生成树的特点是：

1. 一个无向图可以有多个生成树。

2. 生成树中的任意两个顶点之间都必须存在一条唯一的简单路径。

3. 生成树中的边数等于顶点数减一。

4. 生成树中不能存在环。

生成树有顶点数与原图相同，但边数为顶点数减一。