首页 > 试题广场 >

要连通具有n个顶点的无向图至少需要____条边

[单选题]
要连通具有n个顶点的无向图至少需要____条边 
  • n-1
  • n
  • n+1
  • 2n
查看答案及解析
添加回答
Realself头像 Realself

  • 选A，最少需要n-1条边

  • 连通图：在一个无向图中，从每一个顶点到每一个其它顶点都存在一条路径，则此无向图是连通的

    有n个顶点的连通图最多有n（n-1）/2 条边，最少有n-1条边

    举例说明：如图所示，设ABCD四个点构成强连通图，则：

    1. 边数最多有(4×3)/2=6条，如图所示

      图片说明

    2. 边数最少有3条，如图所示

      图片说明

  • 强连通图：满足此连通条件的有向图叫做强连通图

    有n个顶点的强连通图最多有n（n-1）条边，最少有n条边

    举例说明：如图所示，设ABCD四个点构成强连通图，则：

    1. 边数最多有4×3=12条，如图所示
      图片说明
    2. 边数最少有4条，如图所示
      图片说明

  • 完全图：每一对顶点间都存在一条边

发表于 2020-05-06 17:00:35 回复(0)
提交观点

问题信息

iOS工程师 安卓工程师 哔哩哔哩 2020
上传者：小小
难度：
1条回答 4107浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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