首页 > 试题广场 >

设有 6 个结点的无向图，该图至少应有 ( ) 条

[单选题]
设有 6 个结点的无向图，该图至少应有 (      ) 条边就可以是一个连通图。 
  • 5
  • 6
  • 7
  • 8
查看正确选项
添加回答
waitme`头像 waitme`
大话数据结构中连通图的定义是：在无向图中任意两个顶点之间都是连通的，则称为连通图，6个节点连成一条线即可，所以为5
发表于 2019-03-04 18:40:30 回复(0)
字节内推dd头像 字节内推dd

这题只能因题论题选A

但是实际上是不对的。

最少：

当题目问最少几条边时，因为是无向图，直接把每个结点连成一条线就行了。

即 有n个结点，最少需要 n-1 个结点。

至少：
当题目问至少几条边时，则为了保证图一定时连通的，对无向图，可以构造一个完全连通图，在为此图加一个结点。
需知：当有n个结点的完全连通图，含有 n(n-1)/2 个结点。

因此当有n个结点，至少应有 (n-1)*(n-2)/2 + 1 条边才能保证成为一个连通图。

发表于 2022-03-02 16:52:36 回复(0)
梦境迷离头像 梦境迷离
需要确保答案应该是11  没毛病 
发表于 2018-03-03 13:31:48 回复(0)
苟.....苟富贵勿相忘啊大兄弟头像 苟.....苟富贵勿相忘啊大兄弟
“至少应有   (      )   条边才能确保是一个连通图。”和“ 至少有   (      )   条边就可以是一个连通图。 ”说法不一样，答案也不一样吧。

发表于 2017-06-29 17:28:55 回复(2)
名字是谷雨头像 名字是谷雨
5就可以了，要确保的话需要11
发表于 2019-10-23 17:21:41 回复(0)
学术废物头像 学术废物
问的是尽可能少
发表于 2022-03-11 11:01:01 回复(0)
YoJay头像 YoJay
https://www.nowcoder.com/questionTerminal/741781561c78460abeca3899c9a462f1
发表于 2018-07-28 20:54:39 回复(0)
GoAshore头像 GoAshore
“至少应有 ( )条边才能确保是一个连通图。”和“至少有 ( )条边就可以是一个连通图。”说法不一样，答案也不一样。
编辑于 2022-11-29 17:34:20 回复(0)
李秋风头像 李秋风
11
发表于 2020-10-20 07:21:14 回复(0)
翻红的番茄头像 翻红的番茄

确保连通图和是一个连通图有区别
发表于 2020-06-01 11:35:45 回复(0)
去哪儿呢111头像 去哪儿呢111
？？？？
发表于 2018-01-26 17:10:08 回复(0)
操作系统有点难头像 操作系统有点难
这个答案是不是有问题
发表于 2017-10-07 08:37:13 回复(0)
提交观点

问题信息

图
上传者：阿奻_
难度：
12条回答 8670浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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