首页 > 试题广场 >

有8个节点的无向图，至少需要多少条边才能保证图是联通的（

[单选题]
有8个节点的无向图，至少需要多少条边才能保证图是联通的（        ） 
  • 5
  • 6
  • 7
  • 8
查看正确选项
添加回答
Sc0tt头像 Sc0tt
对于无向图的话，至少需要n-1条边可以使得图是联通的；如果对于有向图的话，至少需要n条边才可以使得图是联通的。
发表于 2018-05-22 10:29:48 回复(0)
霍七头像 霍七
具有【n】个节点的无向图，至少需要【n-1】条边才能保证图是联通的。此时，这个无向图是一棵树。
发表于 2017-12-21 20:05:33 回复(0)
aginn头像 aginn
22个吧？
发表于 2019-09-15 15:04:23 回复(0)
Devin———头像 Devin———
0. 默认图为简单图，不存在重边，不存在自环。
1. 如果是至少的话那么有N个顶点需要N-1条边，可以贪心的将每条边分给两个未连接的顶点，那么就得到了一颗最小生成树。
2. 如果是要保证必然连通那么至少需要.条边，代表从n-1个顶点中任意(每)选两点都连接一条边，并将最后一个没连上的点和随便一个点相连。
发表于 2021-04-08 10:11:29 回复(0)
zfun头像 zfun
sb题目没毛病吧
发表于 2018-06-14 13:10:05 回复(2)
尘埃飞舞呀头像 尘埃飞舞呀
这题是不是错了啊，至少需要多少条边才能保证图是连通的，也就是说7条边能保证图是连通的？不应该是七个顶点组成完全无向图所需边数再加1吗？？
发表于 2023-04-01 13:41:28 回复(0)
牛客626990132号头像 牛客626990132号
N-1,选C
发表于 2020-08-07 22:49:14 回复(0)
jjprincess头像 jjprincess
连通的意思不是要任意两个顶点间都存在路径吗？所以具有n个结点的无向图不应该需要n条边才能保证任意两个顶点都存在路径吗？求解答。
发表于 2018-01-07 20:53:10 回复(1)
Fengzhi志头像 Fengzhi志

无向图：连通性

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

编辑于 2017-12-21 19:58:38 回复(0)
左庶长头像 左庶长
8个点依次连接排成一条线，共7条边
发表于 2017-12-21 16:07:08 回复(0)
提交观点

问题信息

图
上传者：阿奻_
难度：
10条回答 11053浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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