n个结点的无根树，n-1条边，k个叶子结点，有多少种不同的树？

n个结点的无根树，n~

哥我哭了玩电脑这么多年从没听说过无根树

系统树可以是有根的，也可以是无根的。在有根树中，存在一个被称为根的特殊节点，由此导向任何别的节点都只有唯一有根系统树和无根系统树。箭头指示从根到OTUD的唯一途径。每一途径中的方向与进化时间相对应，而根则是所有正被研究的OTU的共同祖先。无根树是一种只将OUT间的关系具体化而未定义进化途径的树。对三个物种来说，存在着三种可能的有根树，但只有一个无根树。从三种OYU可能会构建出三种不同的有根树，但却只有一种无根树。对n个OTU而言，两分叉有根树的数目(NR)由NR=(2n-3)!/{[2^(2-n)](n-2)!}(n≥2)，对n≥3，两分叉无根树的数目为(NU)=(2n-5)!/{[2^(n-2)](n-2)!}。n个OTU的可能无根树数等于(n-1)个OTU的可能有根树数。OTU从2到10的可能有根树和无根树的数目如下表：随着n的增加NU和NR和都极快地增大，而到10OTU时已经有200多万两分叉无根树和将近3500万有根树了。由于这些树种只有一种能正确表示这些OTU间真是的进化关系，所有，当n较大时，推论出真实的系统树比较困难。

n{(n-1)*k}

1.深度为m的满二叉树有2^m-1个结点.
因为满二叉树的定义为:一颗深度为k且有2^k-1个结点的二叉树称为满二叉树.
2.若要树深为最小,显然要使除最后一层外的每一层都有尽可能多的结点,即要二叉树为完全二叉树.

由二叉树的一个重要性质:具有n个结点的完全二叉树的深度为[log2n]+1.(这是在根节点层次为1时,若为0,将+1去掉即可)
log2n是以2为底n的对数
[log2n]为不大于log2n的最大整数

可知,含有100个(根)结点的二叉树,(应该没"根"字吧)
可能的最小树深为[log2 100 ]+1
二叉树根结点的层次为0时,可能的最小树深为[log2 100 ]
即为6.

可以这样计算:确定最小树深当且仅当二叉树为完全二叉树时出现,设深度为k,(此时设二叉树根结点的层次为0)有:
2^0+2^1+2^2+...+2^(k-1)<100=<2^0+2^1+...+2^k
即2^k-1<100=<2^(k+1)-1
或2^k=<100<2^(k+1) (上下两式是相等的)
其中2^k为完全二叉树的第k层的最多结点个数
解得k=<log2 100<k+1
即k=[log2 100]=6

n{(n-1)*k}
不客气。。
这么简单。。
大恩不言谢！

n{(n-1)*k}

---

松溪县15966319037： 若一个具有n个顶点,k条边的无向图是一个森林,则森林中必有多少棵树 - ？
越巩洛普： 如果某棵树中有N0个结点,K0条边,则N0 = k0 + 1 设森林中有m棵树,其结点数分别为n1,n2,n3,.,nm 相应地,各棵树的边数分别为k1,k2,k3,...km 显然:n1 = k1 + 1,n2 = k2 + 1,.,nm = km + 1 (1) 按照题设: n1 + n2 + n3 +.+ nm = N (2) k1 + k2 + ...

松溪县15966319037： 设无向图G中有n个结点,n - 1条边,用归纳法于n,证明G是连通图则G中无回路. - ？
越巩洛普：[答案] 假设这个无环图是不连通的,则设图G有k个连通分支G1,G2,…,Gk(k≥2),设G1有x1个结点,G2有x2个结点,G3有x3个结点……Gk有xk个结点,则有x1+x2+x3+……+xk=n,又因为Gi有xi-1条边,所以图G有(x1-1)+(x2-1)+(x3-1)+……+(...

松溪县15966319037： 一个包含n个分支结点(非叶结点)的非空满k叉树,k>=1,它的叶结点数目为?？
越巩洛普： 它的叶结点数目是(k-1)*n+1个 你只要求出这个树有几层就可以把它的叶结点数求出来.它的分支结点有n个,设这个树有m层,所以有k^0+k^1+……+k^(m-2)=n,由此可求出层数m,再由m和k求出最后一层结点也就是叶结点的数目.

松溪县15966319037： 若一个具有N个顶点,K条边的无向图是一个森林N>K则森林有几棵树 - ？
越巩洛普： N-K 很简单,具有M个顶点的树恰有M-1条边.

松溪县15966319037： 若无向图G中有n个结点,n - 1条边,则G为树.这个命题正确吗?为什么?求证明 - ？
越巩洛普：[答案] 不正确 举个反例即可 如有4个点的图,其中3个点两两相邻,另一个点没有与之相连的边,满足条件,但显然不是树,都不连通 如果把连通作为前提条件就是对的,即 若无向连通图G中有n个结点,n-1条边,则G为树 这是树的等价定义之一

松溪县15966319037： 一棵N个节点的树有多少条边 - ？
越巩洛普： B:n-1连接两个节点的线叫边 只要知道每两个节点间有一条边就行了.

松溪县15966319037： 设无向图G中有n个结点,n - 1条边,用归纳法于n,证明G是连通图则G中无回路.？
越巩洛普： 假设这个无环图是不连通的,则设图G有k个连通分支G1,G2,…,Gk(k≥2),设G1有x1个结点,G2有x2个结点,G3有x3个结点……Gk有xk个结点,则有x1+x2+x3+……+xk=n,又因为Gi有xi-1条边,所以图G有(x1-1)+(x2-1)+(x3-1)+……+(xk-1)=n-k条边,少于已知的n-1条边,所以假设不成立,该无环图一定是联通的.

松溪县15966319037： n个结点的非空二叉树有n - 1个分支?对吗,为什么 - ？
越巩洛普：[答案] 准确地说有n-1条边(你的分支是这个含义?) 一半而言,这个树中的分支通常指的是非叶子结点(二叉树则指度为1或者2的结点),对于二叉树而言,n个结点是推导不出有n-1个分支结点的,倒是n个叶子可以推出n-1个度为2的结点

松溪县15966319037： 在一棵具有n个结点的二叉树中,所有结点的空子树一共有?棵,为什么? - ？
越巩洛普： 肯定是n+ 1棵 因为n个结点理论上有2n个分支,但是n个结点的树中有n-1条边2n-(n-1)=n+1 用数学归纳法也可以证明的

松溪县15966319037： 在具有N个结点的K叉树的K叉链表表示中,有多少个空指针? - ？
越巩洛普： n个结点的K叉树共有n*k个指针域,已使用的指针域为n-1,所以空指针的个数为:n(k-1)+1