当前位置: > N个岛建N-1座桥总建法是N的N-2次方!...
题目
N个岛建N-1座桥总建法是N的N-2次方!
哪位帮我证明一下啊

提问时间:2021-03-23

答案
对于一个无向连通图来说,它可能有很多生成树,那么如何求得它的生成树个数呢?
首先给出一个非常一般的计算方法 -- 矩阵行列式法
对于任何一个顶点数为n的无向连通图,我们列出一个矩阵.
矩阵的规则是:
1、在主对角线上的元素为此节点的度数
2、对于其他位置上的元素Matrix(i,j) { i != j },
(1) 如果节点i和节点j连通,则Matrix(i,j)的值为-k,其中k值为节点i到节点j的平行边个数.如果此图是一个简单图,即任意两点间不存在平行边,那么这个值就为-1.
(2) 但如果节点i和节点j根本不连通,则Matrix(i,j)的值为0.
接下来如何求得这个无向连通图的生成树个数呢.
直接给出定理:
撤去任意一个节点的信息,求出剩下的(n-1)*(n-1)矩阵的行列式,此值即为这个无向连通图的生成树个数.
我就先贴1段吧..
举一反三
已知函数f(x)=x,g(x)=alnx,a∈R.若曲线y=f(x)与曲线y=g(x)相交,且在交点处有相同的切线,求a的值和该切线方程.
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
版权所有 CopyRight © 2012-2019 超级试练试题库 All Rights Reserved.