22问答网
所有问题
要连通具有n个顶点的有向图,至少需要多少条边?答案为什么不是n-1?要给出解释啊
如题所述
举报该问题
其他回答
第1个回答 2013-07-15
因为是有向图,假设2个顶点A、B。A到B需要一条边,B到A也需要一条边,所以需要2条,即n个顶点需要n条边
相似回答
有n个顶点的
强
连通图
最多
有多少条边,
最少有多少条边
答:
有n个顶点的强连通图最多有n(n-1)条边,最少有n条边
。解释如下:强连通图是指一个有向图中任意两点v1、v2间存在v1到v2的路径(path)及v2到v1的路径的图。最多的情况:即n个顶点中两两相连,若不计方向,n个点两两相连有n(n-1)/2条边,而由于强连通图是有向图,故每条边有两个...
n个
节点
的有向连通图至少
有
多少条边?
答:
n个节点的有向连通图,最少有n-1条边
。在数据结构中,n个顶点的连通图至少要有(n-1)条边(也就是树)才能保证图为连通图。一个无向图G=(V,E)是连通的,那么边的数目大于等于顶点的数目减一:|E|>=|V|-1,而反之不成立。即连通图边数最少为E-1。连通图的含义 1、连通分量:无向图G...
大家正在搜