【邻接矩阵】为什么有N个顶点的连通图用邻接矩阵表示时该矩阵至少有2(n-1)个非...

发布时间：2021-03-24 14:32:33

为什么有N个顶点的连通图用邻接矩阵表示时 该矩阵至少有2(n-1)个非零元素又没有说是有向还是无向.答案说是2（n-1)但是如果是无向的话不就是n吗= =那不是更少吗 数学

网友回答

【答案】 所谓连通图一定是无向图,有向的叫做强连通图
　　连通n个顶点,至少只需要n-1条边就可以了,或者说就是生成树
　　由于无向图的每条边同时关联两个顶点,因此邻接矩阵中每条边被存储了两次（也就是说是对称矩阵）,因此至少有2(n-1)个非零元素
以上问题属网友观点，不代表本站立场，仅供参考！