Question

具有六个顶点的无向图至少应有多少条边才能确保一个连通图

Answer 1

5条边。即其中5个顶点两两相连，此时，只需要再加一条边即可确保6个顶点一定连通，所以最少是5*4/2+1=11个顶点。

若G是无向图，则0≤e≤n(n-1)/2，恰有n(n-1)/2条边的无向图称无向完全图。

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

扩展资料：

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

不考虑顶点到其自身的边。即若(v1，v2)或<vl，v2>是E(G)中的一条边，则要求v1≠v2。此外，不允许一条边在图中重复出现，即只讨论简单的图。

深度优先算法是将未被访问的节点放到一个栈中(stack)，虽然在上面的代码中没有明确在代码中写stack，但是递归间接的利用递归堆实现了这一原理。和深度优先算法不同，广度优先是将所有未被访问的节点放到了队列中。

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

Answer 2

5条边。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。有向边也称为弧(Arc)，边的始点称为弧尾(Tail)，终点称为弧头(Head)。

【例】<vi，vj>表示一条有向边，vi是边的始点(起点)，vj是边的终点。因此，<vi，vj>和<vj，vi>是两条不同的有向边。

扩展资料

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

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

（2）若G是有向图，则0≤e≤n(n-1)。

恰有n(n-1)条边的有向图称为有向完全图(Directed Complete Graph)。

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

Answer 3

注意到“确保连通”，那么5条边并不能达到这种目的，需要考虑最坏情况，即其中5个顶点两两相连，此时，只需要再加一条边即可确保6个顶点一定连通，所以最少是5*4/2+1=11个顶点

Answer 4

（1）最少需要5条边；
即顶点为n，则最少需要n-1个才能连通该图，如：0-0-0-0-0-0
（2）当边的数目大于10时，该图必定连通。
即考虑最差有多少边，该图无法连通，就是n-1个顶点连成了完全图【图的每两个顶点之间有边链接，此时需要的边数为n(n-1)/2】，也就是说6个顶点中的5个连成了完全图，但是第六个顶点却没有被连接，所以大于这个数目【5(5-1)/2 + 1】= 10 一定能够使得该图连通，即>10，为11。

Answer 5

至少要11条边才能确保是连通图

最少是5条边