为什么有N个顶点的连通图用邻接矩阵表示时 该矩阵至少有2(n-1)个非零元素
又没有说是有向还是无向.答案说是2(n-1)但是如果是无向的话不就是n吗= =那不是更少吗
人气:443 ℃ 时间: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条边的全连通图,至少去掉几条边才能构成一棵树?
- MASS ST0RAGE是什么意思?
- 1.叉开手指,大拇指尖和中指尖间的距离是?
- 把2米长的钢管平均截成5段,每段占全长的几分之几,每段长几分之几?
猜你喜欢
- 给你下列器材:一个低压电池组,一只小灯泡,一只开关,一只电铃和若干细导线,请你设计一自动放养奶牛的装置图.要求:用导线将牛群围住,合上开关后,当牛在圈内吃草时,小屋内
- 长方形花圃,画在比例尺为1:200的图纸上,纸上长方形的周长是48厘米,长与宽的比5:3,求这块花圃实际面积
- 严郑公宅同咏竹诗的前三联描写出竹子怎样的形象
- 某件工程,甲单独作需要5小时,乙需要7.5小时,甲乙合作,甲先做1小时,剩下的乙做,乙要几小时能完成这个工程
- 初中用数学知识解决生活问题的例子
- 有一个两位数,十位上的数字是个位上数字的2倍,如果把这两个数字对调,那么所得的两位数比原数小27
- When the traffic light turn red,we__cross the road.
- -mum.where is my coat