首页 > 其他 > 详细

学习总结--数学.cayley定理

时间:2014-06-25 19:33:33      阅读:423      评论:0      收藏:0      [点我收藏+]

定义:

有n个标志节点的树的数目等于nn?2(仅是cayley在组合数学中的应用)


简单证明:

1.首先我们假设n为4,即有3个节点
2.这样的话我们就有k个子树,此时k=3

bubuko.com,布布扣(图1)
3.选中其中一个节点C(1n),然后x 再选中不含该节点的一个子树C(1k?1),让这颗子树的根连接到该节点上,这样的话子树就减少了一棵
bubuko.com,布布扣(图2)
bubuko.com,布布扣(图3)
等。。。

4.重复操作直到k=1,k从n变成1总共执行了n-1次,所以根据乘法原理,构造出的有确定根节点的树有ans=nn?1?(n?1)!
5.但是对于一棵树来说,它又n-1条边,每条边被选中先后的顺序有(n?1)!种,但是对于树来说,边的先后关系是无关紧要的,所以ans=ans(n?1)!=nn?1

bubuko.com,布布扣(图4)
bubuko.com,布布扣(图5)
6.对于每个树来说,构造树时有确定根节点,每一个树可以将该树中的n个节点均做为根节点,于是乎ans=ansn=nn?2
bubuko.com,布布扣(图6)
bubuko.com,布布扣(图7)
bubuko.com,布布扣(图8)

学习总结--数学.cayley定理,布布扣,bubuko.com

学习总结--数学.cayley定理

原文:http://blog.csdn.net/keshuai19940722/article/details/33417525

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!