为什么有N个顶点的连通图用邻接矩阵表示时 该矩阵至少有2(n-1)个非零元素
又没有说是有向还是无向.答案说是2（n-1)但是如果是无向的话不就是n吗= =那不是更少吗
人气：355 ℃ 时间：2020-01-29 19:02:39
解答
所谓连通图一定是无向图,有向的叫做强连通图
连通n个顶点,至少只需要n-1条边就可以了,或者说就是生成树
由于无向图的每条边同时关联两个顶点,因此邻接矩阵中每条边被存储了两次（也就是说是对称矩阵）,因此至少有2(n-1)个非零元素
推荐
- 对于一个有n个顶点和e条边的连通图,其生成树中顶点数和边数分别为
- .n个顶点的连通图用邻接矩阵表示时,该矩阵至少有__个非零元素.
- 8 有n个顶点的无向图,采用邻接矩阵表示,图中的边数等于邻接矩阵中非零元素之和的一半.
- 证明n个顶点k条边的简单图G,若k>1/2(n-1)(n-2),则图G是连通的.
- n个顶点,m条边的全连通图,至少去掉几条边才能构成一棵树?
- 已知周长=18.84厘米,直径=?
- 你不可能犯两次同样的错误.第二次再犯,就已经不再是一个错误,而是你自己的选择.
- 请问磷酸二氢钾与国光钾是一个东西么?
猜你喜欢
- 开国大典恭敬庄严地站着是什么词语
- 第三人称形式
- 每个酚酞分子中有碳原子几个,氢原子几个,氧原子几个,共含原子几个?
- 金属块重10N,挂在弹簧测力计上,当它全部浸没在水中时,测力计的示数为8N,若金属块有一半体积浸入水中,测力计的示数为多少N；如果金属块全部浸没在酒精中,它受到的浮力为多少N（酒精的密度为0.8*10^3Kg/m^3）
- 解下列方程
- Even if you get away from what you have done, your conscience will catch up with you
- Something is wrong with my computer,I'll have it ____（repair）this afternoon.
- are there in birthdays seven October连成一句话
