Question

在一个具有n个顶点的无向图中，要连通全部顶点至少需要多少条边

在一个具有n个顶点的无向图中，要连通全部顶点至少需要多少条边

Answer 1

n个顶点的连通图至少有n-1条边，强连通图2（n-1）

连通是两个顶点之间有路径即连通，N-1条足够。

无向图中的边均是顶点的无序对，无序对通常用圆括号表示。

无向图的最多边是无向完全图：包含n(n-1)/2条边。因为一条边关联两个结点，有向完全图的才有n(n-1)条弧。而无向图变联通至少边数：n-1。有向图变连通图至少需要边数：n。

任意一条边都代表u连v以及v连u。

无向图是相对于有向图来说明的，就是说每条边都是双向边，而有向图每条边都是单向边，也就是说只能由一个点指向另一个点。因此连通无向图定义可推。同理，非连通无向图亦可推。

图的连通分量的目的，是为了确定从图中的一个顶点是否能到达图中的另一个顶点，也就是说，图中任意两个顶点之间是否有路径可达。这个问题从图上可以直观地看出答案。

Answer 2

n个顶点的连通图至少有n-1条边,强连通图2（n-1）

连通是两个顶点之间有路径即连通，N-1条足够。

无向图中的边均是顶点的无序对，无序对通常用圆括号表示。

无向图的最多边是无向完全图：包含n(n-1)/2条边。因为一条边关联两个结点，有向完全图的才有n(n-1)条弧。而无向图变联通至少边数：n-1。有向图变连通图至少需要边数：n。

扩展资料：

无向图的表示

若G是无向图，则0≤e≤n(n-1)/2

恰有n(n-1)/2条边的无向图称无向完全图(Undirected Complete Graph)

注意：完全图具有最多的边数。任意一对顶点间均有边相连。

无向图G=<V,E>,其中：

V是非空集合，称为顶点集。

E是V中元素构成的无序二元组的集合，称为边集。

参考资料来源：百度百科-无向图

Answer 3

n个顶点的连通图至少有n-1条边,强连通图2（n-1）