校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
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条回复 评论
虹猫

我认为题意曲解了连通的概念

发表于 2018-10-13 14:25:05
0 0
雨声敲敲

为什么9个顶点非得是完全联通呢?定义不是说只要任意两个顶点之间存在路径就算连通吗?不理解~

发表于 2018-10-13 14:24:48
0 0