试题-若无向图G = （V.E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（）

题目

若无向图G = （V.E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（）

A.6

B.15

C.16

D.21

上一题 下一题

解答

正确答案是 C

任何情况都连通的最少边数表示边分布最浪费的最少边情况，取点数减一的完全图6*5/2=15再加一条边得结果16

C 11条回复评论

地瓜土到掉渣

认真看完了，浅显易懂，学习到了。

发表于 2023-07-31 23:00:00

0 0

人生赢家

什么叫任何情况都连通？

发表于 2018-10-13 11:52:17

0 0

资深90后

求解答，我构成一个环不能达到全连通吗

发表于 2018-10-13 11:52:09

0 0

粽子

其实很简单。考虑极端情况，即图G的6个顶点构成完全无向图，再加上一条边链接该无向图和剩余那个顶点即构成了一个连通图。

就是c（2,6）+1=16

发表于 2018-10-13 11:52:02

0 0

小洁癖

先看六个节点。6个里面选择两个。15重组合。然后加上第七个节点

发表于 2018-10-13 11:51:51

0 0

落星辰

这题写得真模糊。

发表于 2018-10-13 11:51:41

0 0

小小小可乐

重点在于对题的理解：保证图G在任何情况下都是连通的是指－假设给定N个点给定M条边，任意连接N个点，边数不超过M，都能使该无向图连通。求最小M

发表于 2018-10-13 11:51:34

0 0

冬季恋歌

共7个顶点，依据鸽巢原理，前六个顶点需构成一个完全连通图，第七个顶点只需与其他六个中任意一个相连即可，六个顶点中每个点最多与其他五个连接，并且总共加了两次，故共有6×5╱2=15个，再加上一条边，共16条边。

发表于 2018-10-13 11:51:27

0 0

一零计划

任何情况，所以先找6个顶点的完全图需要的边即6*（6-1）/2=15条，此时再加一条边连接剩余的一个顶点就能保证图是连通的，所以共需要16条

发表于 2018-10-13 11:51:15

0 0

猪猪猪

若保证无向图在任何情况下都是连通的，即任意变动图G中的边，图G始终保持连通，首先需要G的任意6个结点构成完全联通子图G₁，需要15条边，然后在添加一条边使第7结点与G ₁连起来，共需16条边

发表于 2018-10-13 11:51:03

0 0

问题信息

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

难度:

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