首页 > 试题广场 >

一个20个顶点的连通无向图，其边的个数最少，最多分别为（）

[单选题]
一个20个顶点的连通无向图，其边的个数最少，最多分别为（） 
  • 20, 115
  • 19, 190
  • 20, 380
  • 19, 400
查看正确选项
添加回答
keyven_guo头像 keyven_guo
对图中任意顶点u、v，都存在路径使u、v连通。对于最少边数，由于是无向图故为n-1；对于最多边数，先考虑有向图，全出现为n(n-1)，由于是无向图，故为n(n-1)/2.
发表于 2018-03-23 09:57:21 回复(0)
Realself头像 Realself

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

    有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 16:54:25 回复(0)
提交观点

问题信息

C++工程师 七牛云 2018 Java工程师
上传者：小小
难度：
2条回答 4608浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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