首页 > 试题广场 >

若无向图 G 中含 7 个顶点，则保证图 G 在任何情况下都

[单选题]

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

  • 6
  • 15
  • 16
  • 21
查看正确选项
添加回答
赌怪头像 赌怪
求最小连通，因此是6个节点达成最小边数，再加上最后一个节点构成连通，因此为n*（n-1）/2+1
发表于 2019-09-25 17:14:18 回复(0)
被升职的干饭人很会编程头像 被升职的干饭人很会编程
这种题，就是说任何情况下都要保证是构成连通的，所以如果6个结点构成无向完全图，那么6个结点用了最大边数，再加一条边就可以把第7个结点连通，所以在任何情况下7个结点就都是连通的了。如果6个结点不事先构成无向完全图，那么有可能会用掉所有的边，导致不能在任何情况下7个结点都连通
发表于 2023-05-17 15:20:13 回复(0)
提交观点

问题信息

C++工程师 2019 大数据开发工程师 蘑菇街 Java工程师
上传者：小小
难度：
2条回答 989浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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