假如有一个无向图G=(V,E)中有8个顶点，那么当有N条边时

[单选题]

假如有一个无向图G=(V,E)中有8个顶点，那么当有N条边时，我无论怎么用这N条边来连接这8个顶点，都会使

图G是连通的，那么N最小是多少?

查看答案及解析

小野市

方法：任何情况下都是连通的，考虑极端情况，即图G的7个顶点构成完全无向图，再加上一条边链接该无向图和剩余那个顶点即构成了一个连通图。因此，最少边数 = 7 × 6 / 2 + 1 = 22。

发表于 2018-07-11 20:19:20 回复(2)

更多回答

安如水

无方向时设边的条数为e：e的条数为0~N(N-1)/2

全连通时边数为N(N-1)/2这是最大的情况，最小的全连通情况为小野式的方法，done

发表于 2019-05-20 15:17:06 回复(0)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师 2018 PHP工程师百度 Java工程师

上传者：小小

难度：

2条回答 111收藏 3220浏览

扫一扫，把题目装进口袋