题目
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段吧..
首先给出一个非常一般的计算方法 -- 矩阵行列式法
对于任何一个顶点数为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的值和该切线方程.
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
最新试题
热门考点
- 1Mary works very hard.(hard画线)画线提问
- 2人声鼎沸中的“鼎”字是什么意思
- 3有理数:-5,7,3,-8,把这4个数通过加减算式(每个数只能用一次),请你分别写出结果是1,-1,2,-2的算式
- 4髟下面加个此字是什么字
- 5求着几句歇后语的下半句
- 6初中化学基础知识总结和常用口诀?
- 7解不等式2≤|1-2x|≤5,
- 8如图所示,有一根长60cm的铁丝,用它围成一个矩形,写出矩形面积S(cm2)与它的一边长x(cm)之间的函数关系式_.
- 9一个底面直径是20厘米的圆柱形玻璃杯中装有水,水中浸没着一个底面直径为12厘米、高10厘米的圆锥形铅锤,当铅锤取出后,杯里的水面下降多少厘米?
- 10使用某常用温度计发现:当测量冰水混合物时,温度计的读书为2℃;在1标准大气压下侧沸腾的水的温度时,读书为98℃.若用此温度计测某液体温度时读书为74摄氏度,则此液体的实际温度为多少?