首页 > 其他 > 详细

矩阵树定理及变元矩阵树定理

时间:2019-04-26 01:04:41      阅读:471      评论:0      收藏:0      [点我收藏+]

变元矩阵树定理:
定义Kirchhoff矩阵\(K\),其中
\(K_{ii}\)为所有与\(i\)相连的边的权值和
\(K_{ij}\)为连接\(i\)\(j\)的边权值的负值
那么\(\sum\limits_{tree\in T}\prod\limits_{E\in tree}val(E)\)\(T\)为生成树集合,就是生成树的边积的和

然后矩阵树定理就是把
\(K_{ii}\)定义为\(i\)的度数
\(K_{ij}\)定义为\(i\)是否\(j\)相连(是则为\(-1\),否则为\(0\))
这样每棵生成树的贡献就是1了,也就是生成树个数

矩阵树定理及变元矩阵树定理

原文:https://www.cnblogs.com/dummyummy/p/10519370.html

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