首页 > 试题广场 >

有n个顶点的强连通有向图G至少有()条弧。

[填空题]
有n个顶点的强连通有向图G至少有1条弧。
查看正确选项
添加回答
喵咪咪～喵咪咪～头像 喵咪咪～喵咪咪～

强连通图（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:21:55 回复(0)
提交观点

问题信息

图
上传者：呼呼L
难度：
1条回答 6285浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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