首页 > 试题广场 > 假如有一个无向图G=(V,E)中有8个顶点,那么当有N条边时,我无论怎么用...
[单选题]
假如有一个无向图G=(V,E)中有8个顶点,那么当有N条边时,我无论怎么用这N条边来连接这8个顶点,都会使
图G是连通的,那么N最小是多少?
  • 7
  • 21
  • 22
  • 42

1个回答

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

发表于 2018-07-11 20:19:20 回复(1)
牛客网,程序员必备求职神器
QQ群:169195721
微 信:www_nowcoder_com 关注
微 博:牛客网 关注

扫一扫,把题目装进口袋