注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

无向图生成树的个数  

2010-08-24 11:44:46|  分类: 其他 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
首先是有n个节点各无向完全图,有Cayley定理,说生成树的个数有n^(n-2)个,证明可以通过Prüfer编码来证明,参看http://www.matrix67.com/blog/archives/682 ,然后就是有个推论,如果是生成一个度数分别为d1,d2...dn的一棵生成树,则生成树的个数是(n-2)!/((d1-1)!*(d2-1)!....(dn-1)!)
如果是求一般的无向完全图的生成树的个数,需要用基尔霍夫矩阵树定理,设矩阵A=度数矩阵-邻接矩阵,比如:无向图生成树的个数 - 3214668848 - 那一日,泪水打湿雪花冰冷的心
 那么矩阵A:
 4  -2 -1 -1
-2   3 -1  0
-1  -1  2  0
-1   0  0  1
任意去掉第i行和第i列,剩余的矩阵的行列式就是生成树的个数
  评论这张
 
阅读(798)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018