首页 > 试题广场 >

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

[单选题]

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

  • 9
  • 90
  • 37
  • 45
如果是可以确保有,是9,保证有的是37
发表于 2017-10-29 16:25:27 回复(0)
9条边可保证10个顶点的无向图连通,如果有37条边,则可确保所有定点连通
发表于 2017-04-02 15:04:42 回复(0)
为什么不是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)
总结起来就是:其中9个点构成完全图,另一个点随便连一条边都是通的。即:9*8/2+1=37
发表于 2017-03-18 21:25:29 回复(0)
给大家贴个公式



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

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

发表于 2019-09-18 09:49:52 回复(1)
这个题目做的时候看错意思了,我以为是最少要多少条边。正确的理解和解法应该是这样:对于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)
在一个无向图 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)
如果题目问:

设有 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)
先孤立一个点,剩余点完全联通,最后孤立点用至少一条边与完全联通图连接,即1+8+7+6+5+4+3+2+1=37
发表于 2024-01-01 23:26:36 回复(0)

这个题考complete graph的概念的,一个完全图的边数是v*(v-1)/2
所以左边9个顶点的完全子图的边数是36,再加一条边就是37了
发表于 2023-10-27 21:19:25 回复(0)
最坏的情况下,有至少一个点始终不连通,
为了让边数达到最大,保证1个点不连通,此时最大的边数为 9个点两两之间都存在边,为36条边,
此时9个点之间没法再添加边,再添加一条边时必然连至第10个点
发表于 2022-04-19 14:58:49 回复(0)
n-1 * n-2 / 2 + 1
发表于 2022-03-13 17:30:05 回复(0)