若无向图 G = (V, E) 中含 7 个顶点，则保证图

[单选题]

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

```
6
```
```
15
```
```
16
```
```
21
```

查看正确选项

_no_name

首先我想很多人一开始会疑惑为什么不能是 6 个边为最少的情况。请看下图：

可以看到，同样是给出 7 点 6 边，第二种情况并不能连通，也就不符合题目中“任何情况”的要求。

由此我们可以分析到，要让 7 个点都连通，那么先让 6 个点完全连通，所谓完全就是每个点能够支出的边是满的，这样 6 个点的情况下，边和点的关系是满的。其边的数量由公式 n*(n-1)/2 得出（无向完全连通图），也就是 6*5/2=15；

那么此时，我多了一个点，7 号点，只需要在那 6 个点的图中连一根边过来，7 号点就可以访问任意 6 点图中的点了。

发表于 2019-10-21 16:36:11 回复(12)

二咩

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

发表于 2016-11-28 08:49:15 回复(2)

夏了夏天_0502

这个任何情况都能指什么情况啊

发表于 2017-02-25 09:04:13 回复(4)

Sunny_ivy

5+4+3+2+1=15,15+1=16

v0连v1、v2、v3、v4、v5，5条边

v1连v2、v3、v4、v5，4条边

……

最后再让v7连v0-v5这六个点中的任何一个就可以了

发表于 2016-12-12 10:11:48 回复(3)

gongg涛

这出题人的语文水平真差劲

发表于 2018-11-29 10:23:13 回复(1)

流逝~的~爱~

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

发表于 2017-08-05 21:44:10 回复(0)

牛客-liwei4939

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

发表于 2017-04-23 16:43:03 回复(0)

哎呦呦呦呦丁

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

发表于 2017-04-06 15:01:58 回复(0)

Ray12345

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

发表于 2017-10-14 00:07:23 回复(0)

皮卡皮卡皮卡丘201908011039538

比如只有6条边，4个顶点的无向完全图可以将这6条边消耗完，则还剩3个顶点，这三个顶点和4个顶点的无向完全图共同构成一个图，但很明显这个图没有连通（图不像树顶点与顶点之间可以没有连接）。这种情况下就可以将7个顶点都构成无向完全图，但这并不是最少边的情况，则可以考虑将6个顶点构成无向完全图，因为图不能出现重复边，则再加一条边一定是连在第7个顶点上的。

发表于 2019-08-01 10:48:16 回复(0)