校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 数据结构 > 图的属性
题目

要保证连通具有10个顶点的无向图,至少需要()条边。

A.9

B.90

C.37

D.45

解答

正确答案是 C

要保证连通具有10个顶点的无向图,重点是需要保证连通,则需要前面9个顶点两两相连,就能保证第10个顶点加入一条边就能保证连通。即:从9个节点中人任意选取两个节点连接,则需要C(9,2)条边,再加上最后一条边,则总边数为: C(9,2)+1=(9*8)/(1*2)+1=37

C 13条回复 评论
书为

我没有实习,也没有赶上校招,毕业之后只能社招,投的简历全部石沉大海,特别受打击。开始反思,找问题。简历做的不够好,产品质量达不到。现在停下来,在开始系统的,查漏补缺的学习。

发表于 2022-03-15 22:00:00
0 0
下雨天睡觉

感觉文章思路挺清晰的~

发表于 2021-09-09 11:05:00
0 0
青辰

强~~希望更多人更加努力

发表于 2021-09-08 16:45:01
0 0
企鹅哥哥

为什么不是9啊。

发表于 2018-10-13 14:26:49
0 0
浅色回忆

如果是可以确保有,是9,保证有的是37

发表于 2018-10-13 14:26:28
0 0
粽子

最好情况是9条边,要保证连同需要考虑最坏情况,即其他9个顶点两两相连,共9*8/2=36条边,这时只需再有一条边即可保证连通。

发表于 2018-10-13 14:26:04
0 0
途安米

此题意思是说要多少条边,能保证无论以怎么胡来的连法,都保证一定联通。例如九条边,确实有可以联通的连法,但是如果充满了恶意,只在前5个点连接,则后面5个点是不联通的。必须要更多的边才能保证胡乱连接也一定互联,这个边数就要取到(9个点的全通+1),这样无论怎样试图让其中一个点不连通,只在剩余九个点中连边,最后都剩余一条边,必须把最后一个点连上,于是保证联通了。  

发表于 2018-10-13 14:25:54
0 0
落星辰

9条边可保证10个顶点的无向图连通,如果有37条边,则可确保所有定点连通

发表于 2018-10-13 14:25:42
0 0
雪糕乐

总结起来就是:其中9个点构成完全图,另一个点随便连一条边都是通的。即:9*8/2+1=37

发表于 2018-10-13 14:25:30
0 0
猪猪猪

不是说10个点连通至少需要多少个点,而是为了保证连通,不管出现什么情况都可以连通,至少需要几个点

发表于 2018-10-13 14:25:21
0 0