试题-设有6个结点的无向图，该图至少应有（）条边，才能确保是一个连通图？

题目

设有6个结点的无向图，该图至少应有（）条边，才能确保是一个连通图？

A.8

B.11

C.6

D.5

上一题 下一题

解答

正确答案是 B

这里的“确保”意思是，6个顶点不管怎么连（平行边除外），你是找不出非连通图的情况的，首先5个顶点的全连通图需要的边为n*（n-1）/2=10，再加一条边与另一个顶点相连接，总共11条边，不管你怎么连，都可以确保这个图是连通的（不存在平行边）。

C 9条回复评论

箱湘香樟树

有没有前端入门的开发软件推荐呐？

发表于 2021-09-09 12:45:00

0 0

虹猫

做错这道题的原因是：语文不好。

发表于 2018-10-13 13:47:25

0 0

雪糕乐

是在玩文字游戏吗？？？5条边应该就能保证是连通图了吧。。。

发表于 2018-10-13 13:47:00

0 0

先锋

啥叫确保啊？确保是怎么定义的呀？不懂

发表于 2018-10-13 13:46:52

0 0

几米的思维

注意扣字眼。

发表于 2018-10-13 13:46:44

0 0

老干妈拌面

最少是5条边，能形成一个连通图。

至少应有11条边，才能确保是一个连通图

发表于 2018-10-13 13:46:33

0 0

人间喜剧

应该是11条吧。

确保是连通图，假设不是连通图，则最多是5个点全部互相连接，C（5，2）=10条。

再多1条，则必须与第6个点相连，11条。

发表于 2018-10-13 13:46:25

0 0

王王王

题目的意思是，6个顶点，x条边，无论这x条边是怎么连的，你是找不出非连通图的情况的。求x的最小值。那么假设不连通的情况，最多的边数是5个顶点的完全图，其数目为10条。然后加上一条边，就可以确保连通了。

发表于 2018-10-13 13:46:13

0 0

寒山远火

请问为什么要先把五个点的全链接？

发表于 2018-10-13 13:46:02

0 0

问题信息

分类：数据结构 - 图的属性

难度:

最新校招难题刷题，快来进刷题群吧