题目来源于王道论坛若无向图G=(V, E)中含有7个

[单选题]

题目来源于王道论坛

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

推荐

林呼

要保证无向图G在任何情况下都是连通的，即任意变动图G中的边，G始终保持连通，首先需要G的任意6个结点构成完全连通子图G1，需n(n-1)/2=6×(6-1)/2=15条边，然后再添一条边将第7个结点与G1连接起来，共需16条边。

发表于 2018-09-03 20:29:32 回复(1)

Heaven201903240804496

最少节点即相当于其中六个节点为完全图，再加一条边和一个顶点(6*5)/2+1=16

最多节点即七个节点构成完全图(7*6)/2=21

发表于 2019-08-14 11:30:40 回复(0)

门头沟做题家

考虑最极端的情形，即图G中的6的顶点构成一个完全无向图，再加上一条边后第7个顶点必然与此完全无向图构成一个连通图，所以边数最少为6*5/2+1=16。若边数小于或等于15时，可以使这n条边仅链接图G中的某6个顶点，导致第7个顶点与这6个顶点不连通。

发表于 2018-11-16 10:57:53 回复(0)

提交观点

问题信息

图

上传者：林呼

难度：

3条回答 71收藏 2743浏览

扫一扫，把题目装进口袋