首页 > 试题广场 >

N个顶点的强连通图的边数至少有多少个？

[填空题]
N个顶点的强连通图的边数至少有1个？
添加回答
推荐
单程车票头像 单程车票
至少有N条边
首先,看强连通图的定义,任意两点之间存在可达路径..
当各个顶点之间构成一个回路时,所需边数最少,即为N条边
编辑于 2015-02-04 12:06:58 回复(0)
王俊超头像 王俊超
答案：B
如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图（注意：需要双向都有路径）。
发表于 2015-08-01 09:51:46 回复(0)
梦太美偶不配头像 梦太美偶不配
n个顶点强联通图最多有n*(n-1)条边，最少有n条边。
发表于 2017-04-21 16:11:28 回复(0)
wanlanwalan头像 wanlanwalan

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

解释如下：

强连通图 （Strongly Connected Graph）是指一个有向图（Directed Graph）中任意两点v1、v2间存在v1到v2的路径（path）及v2到v1的路径的图。

最多的情况：

即n个顶点中两两相连，若不计方向，n个点两两相连有n（n-1）/2条边，而由于强连通图 是有向图，故每条边有两个方向，n（n-1）/2×2=n（n-1），故有n个顶点的强连通图最多有n（n-1）条边。

最少的情况：

即n个顶点围成一个圈，且圈上各边方向一致，即均为顺时针或者逆时针，此时有n条边。

发表于 2017-04-07 09:43:07 回复(0)
飞翔的蜗牛头像 飞翔的蜗牛
答案：N

连通图：图中任意两个顶点都是连通的。
强连通图：有向图中任意两个顶点都是连通的。

发表于 2015-09-01 22:00:49 回复(0)
喵咪咪～喵咪咪～头像 喵咪咪～喵咪咪～
强连通图 （Strongly Connected Graph）是指一个有向图（Directed Graph）中任意两点v1、v2间存在v1到v2的路径（path）及v2到v1的路径的图。最多的情况：即n个顶点中两两相连，若不计方向，n个点两两相连有n（n-1）/2条边，而由于 强连通图 是有向图，故每条边有两个方向，n（n-1）/2×2=n（n-1），故有n个顶点的强连通图最多有n（n-1）条边。最少的情况：即n个顶点围成一个圈，且圈上各边方向一致，即均为顺时针或者逆时针，此时有n条边。
发表于 2017-05-04 14:22:58 回复(0)
繁星的夜空2012头像 繁星的夜空2012
注意，强连通图的术语是应用在----有向图中的。因而若该图是抢连通图，则必须保证，图中的任意两个顶点直接都可以连通的，因而对于有向图而言，至少是N条边
发表于 2017-01-09 21:40:27 回复(0)
huixieqingchun头像 huixieqingchun
形成一个环。
发表于 2016-05-08 22:10:53 回复(0)
小河沟大河沟头像 小河沟大河沟
成环即可
发表于 2016-04-15 23:19:21 回复(0)
codersong头像 codersong
一个环就可以了
发表于 2015-10-09 10:03:28 回复(0)
haowg头像 haowg
n-1
发表于 2015-07-22 06:27:47 回复(1)
提交观点

问题信息

图
上传者：zangyoujay
难度：
11条回答 22690浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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