首页 > 试题广场 > 假如有一个无向图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 回复(2)

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

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

  • 公司地址:北京市朝阳区大屯路东金泉时代3-808北京牛客科技有限公司
  • 联系方式:010-60728802(电话) admin@nowcoder.com
  • 牛客科技©2018 All rights reserved
  • 京ICP备14055008号-4
  • 京公网安备 11010502036488号