试题-G是一个非连通无向图，共有28条边，则该图至少有 <u></u>个顶点。

题目

G是一个非连通无向图，共有28条边，则该图至少有个顶点。

A.8

B.9

C.10

D.11

解答

正确答案是 B

要使n个顶点的无向图连通，至少需要(n-1)(n-2)/2+1条边；即n=8时，至少需要23条边，无向图即可连通。
则要使图不连通，n=9
或者令(n-1)(n-2)/2+1=28,求得的n值取上整即可。也就是(n-1)(n-2)=54,n取上整可得n=9

C 5条回复评论

Yolk

大厂我来了！

发表于 2021-11-23 23:00:00

飙车去旅行

不错，值得学习参考

发表于 2021-11-01 23:00:00

望岳

我在长沙，想学ui，有没有推荐的培训机构

发表于 2021-09-09 23:10:00

窦先生

n个顶点最多拥有 n(n-1)/2条边，所以8个顶点最多有28条边，要想28条边而且保持非连通，至少要9个节点，第九个节点是孤立的，不与任何节点连通。

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

落地成盒

将28条边全部连接起来的最小顶点数为8，因为非连通，再加一个顶点得答案9

发表于 2018-10-13 10:35:01

问题信息

分类：数据结构 - 图的遍历

难度: