首页 > 试题广场 >

要保证在任意连接方式下都能连通具有10个顶点的无向图，至少需

[单选题]

要保证在任意连接方式下都能连通具有10个顶点的无向图，至少需要（）条边。 

  • 9
  • 90
  • 37
  • 45
查看答案及解析
添加回答
sunshina黑白格头像 sunshina黑白格
如果是可以确保有，是9，保证有的是37
发表于 2017-10-29 16:25:27 回复(0)
牛客853629号头像 牛客853629号
9条边可保证10个顶点的无向图连通，如果有37条边，则可确保所有定点连通
发表于 2017-04-02 15:04:42 回复(0)
浮云安能蔽日哉_wangwentao头像 浮云安能蔽日哉_wangwentao
为什么不是9啊。
发表于 2017-01-13 10:10:41 回复(2)
倒悬的橙子头像 倒悬的橙子
发表于 2016-12-20 14:49:18 回复(4)
静水云深头像 静水云深
要保证连通具有10个顶点的无向图，重点是需要保证连通，则需要前面9个顶点两两相连，就能保证第10个顶点加入一条边就能保证连通。即：从9个节点中人任意选取两个节点连接，则需要C（9，2）条边，再加上最后一条边，则总边数为： C（9，2）+1=(9*8)/(1*2)+1=37
发表于 2017-02-22 10:37:48 回复(7)
myr头像 myr
此题意思是说要多少条边，能保证无论以怎么胡来的连法，都保证一定联通。例如九条边，确实有可以联通的连法，但是如果充满了恶意，只在前5个点连接，则后面5个点是不联通的。必须要更多的边才能保证胡乱连接也一定互联，这个边数就要取到（9个点的全通+1），这样无论怎样试图让其中一个点不连通，只在剩余九个点中连边，最后都剩余一条边，必须把最后一个点连上，于是保证联通了。
发表于 2018-08-21 10:14:44 回复(3)
mainwindow头像 mainwindow
总结起来就是：其中9个点构成完全图，另一个点随便连一条边都是通的。即：9*8/2+1=37
发表于 2017-03-18 21:25:29 回复(0)
abu-ayyub-flumer头像 abu-ayyub-flumer
给大家贴个公式



参考 殷人昆 《数据结构精讲与习题详解》（C语言版）（第二版）
P476 21题
编辑于 2018-11-21 19:39:36 回复(1)
lala17头像 lala17
总算明白了，题目说要 保证 联通，9条边可能不够。这题容易想不明白（保证-至少）这两词。
发表于 2017-08-25 11:13:11 回复(3)
菜鸟一只♞头像 菜鸟一只♞
这个题应该是说在任何情况下10个顶点都连通，也就是说9个点要保证完全连通也就是完全图，再＋1。n(n-1)/2+1=37
发表于 2019-10-28 16:34:46 回复(0)
、201908051818371头像 、201908051818371

sb题目，差点弄的我对连通的概念都误解了

发表于 2019-09-18 09:49:52 回复(1)
救赎i_头像 救赎i_
这个题目做的时候看错意思了，我以为是最少要多少条边。正确的理解和解法应该是这样：对于n个结点，如果在任意连接方式下都能连通，那也就是n-1个结点两两之间都有一条边，然后再在剩余的那一个结点加一条边，这样无论怎么相连，最后图一定都是连通的。也就是C(2,n-1) + 1 = (n-1)*(n-2)/2 + 1，在这题中n=10，所以至少需要9*8/2 + 1 = 37条边
发表于 2022-07-26 20:13:32 回复(0)
牛客824085号头像 牛客824085号
在一个无向图 G 中，若从顶点vi到顶点vj有路径相连（当然从vj到vi也一定有路径），则称vi和vj是连通的。
如果图中任意两点都是连通的，那么图被称作连通图。
发表于 2017-02-21 11:16:44 回复(1)
福娃头像 福娃
值为 =n*(n-1)/2+1；
发表于 2016-12-19 22:46:23 回复(2)
Dai_Wei头像 Dai_Wei
发表于 2024-12-15 22:26:33 回复(0)
牛客131181223号头像 牛客131181223号

这个题考complete graph的概念的,一个完全图的边数是v*(v-1)/2
所以左边9个顶点的完全子图的边数是36,再加一条边就是37了
发表于 2023-10-27 21:19:25 回复(0)
白起丶头像 白起丶
如果题目问：

设有 10 个结点的无向图，该图至少应有 (      ) 条边就可以是一个连通图。 就应该选A了。


发表于 2020-07-13 11:13:00 回复(0)
尾巴飞上天呀三千尺头像 尾巴飞上天呀三千尺
题目改一下：

要保证在任何情况下，连通具有10个顶点的无向图，至少需要（）条边。

任何情况下都是连通的，考虑极端情况，即图G的9个顶点构成完全无向图，再加上一条边链接该无向图和剩余那个顶点即构成了一个连通图。因此，最少边数 = 9 × 8 / 2 + 1 = 37
考虑：若边数n小于37的时候，可以使这n条边仅连接图G中某9个顶点，从而导致第10个顶点被孤立，不连通（不满足任何情况）

发表于 2018-07-19 16:59:12 回复(1)
牛客639527613号头像 牛客639527613号
先孤立一个点，剩余点完全联通，最后孤立点用至少一条边与完全联通图连接，即1+8+7+6+5+4+3+2+1=37
发表于 2024-01-01 23:26:36 回复(0)
牛客556088594号头像 牛客556088594号
最坏的情况下，有至少一个点始终不连通，
为了让边数达到最大，保证1个点不连通，此时最大的边数为 9个点两两之间都存在边，为36条边，
此时9个点之间没法再添加边，再添加一条边时必然连至第10个点
发表于 2022-04-19 14:58:49 回复(0)
提交观点

问题信息

图
上传者：城市里的养猫者
难度：
40条回答 14742浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号