必考题

考点

数据结构-图-图的遍历

面5笔5

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

麦兜兜麦

2025-03-10 23:00:00

写的不错共勉~，最近也在开始写博客。大佬们来翻牌啊！

0 0

Yolk

2021-11-23 23:00:00

大厂我来了！

0 0

飙车去旅行

2021-11-01 23:00:00

不错，值得学习参考

0 0

望岳

2021-09-09 23:10:00

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

0 0

窦先生

2018-10-13 10:35:13

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

0 0

落地成盒

2018-10-13 10:35:01

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

0 0