我要招人

去企业版

首页 > 试题广场 >

若无向图 G 中含 7 个顶点，则保证图 G 在任何情况下都

[单选题]

若无向图 G 中含 7 个顶点，则保证图 G 在任何情况下都是连通的，则需要的边数

最少是（）

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

查看正确选项

josan

有向图：强连通性

具有 7 个顶点的有向图至少应有多少条边才可能成为一个强连通图 ? 7 key: n

问题同：已知一个有向图具有 7 个顶点，且是一个强联通图，问至少多少条弧？ 7 key: n

具有 7 个顶点的有向图至少应有多少条边一定成为一个强连通图 ? 37 key:(n-1)(n-1) + 1

已知一个有向图具有 7 个顶点，且是一个强联通图，问至多多少条弧？ 42 key:(n-1)*n

无向图：连通性

具有 7 个顶点的无向图至少应有多少条边才可能成为一个连通图 ? 6 key:n-1

问题同：已知一个无向图具有 7 个顶点，且是一个连通图，问至少多少条边？ 6 key: n-1

具有7个顶点的无向图至少应有多少条边一定成为一个连通图? 16 key:(n-1)(n-2)/2 + 1

已知一个有向图具有 7 个顶点，且是一个强联通图，问至多多少条弧？ 21 key:(n-1)*n/2

发表于 2017-07-16 08:45:59 回复(0)

小小伟uestc

由于题干要求在“任何情况”下都是连通的，考虑最极端情形，即G的6个顶点构成一个完全无向图，再加上一条边后，第7个顶点必然与此完全无向图构成一个连通图，所以最少边数=6*5／2+1=16。

发表于 2017-07-10 12:36:31 回复(1)

侯卿

就是一个六芒星的完全图，外面连一个点。(5＋...+1)+1

发表于 2018-04-18 17:24:44 回复(0)

小六神通

认真阅读题目，要"保证"是连通的，也就是n-1个节点的最大边数再加上一个边，如果要求"最少的边”也是n-1条边

发表于 2017-05-31 18:44:16 回复(0)

April丶

在任何情况下，意思就是说，只要有给定的边数则必定会连通，无论你的边怎么安排，怎么放，图G都能构成连通。

因为，只需要n-1个顶点构成完全无向图，再加上1条边和剩下的顶点相连，就能让n个顶点连通。

由题，n是7，因此6个顶点需要构成完成无向图需要5+4+3+2+1=6*5/2=15，再加1是16条边。

因此，只要有16条边，图G一定会连通，不管你边怎么放。

因此选C。

至于A选项的6条边，是图 G 是连通的最少边数，不是在任何情况下的。

发表于 2017-09-25 16:19:59 回复(0)

haiki

完全无向图是指：n阶n-1度正则图。
n度正则图是指：所有节点的度均为自然数n的无向图
题目要求保证任何情况，所以假设这是一个完全无向图，当其顶点数为6，其边数为度数/2：6*5/2=15，再加一条边仍然是联通图，即为16

发表于 2017-08-26 08:48:55 回复(0)

暮秋也微凉

正确答案难道不是6吗？为什么这个的答案是16？最少边，且连通无向图的情况下，应该构成一个环啊。

发表于 2017-05-21 21:08:46 回复(1)

Vricky

任何情况？？不应该是16吗

发表于 2017-05-17 10:13:33 回复(0)

冒泡泡oοО

一模一样的题，另外一道选16条

编辑于 2017-05-16 09:03:29 回复(1)

提交观点

问题信息

图

上传者：阿奻_

难度：

9条回答 169收藏 8579浏览

若无向图 G 中含 7 个顶点，则保证图 G 在任何情况下都

问题信息

热门推荐

相关试题