强连通图,单向连通图,弱连通图,强连通分图

强连通图

有向图中,若任意两个顶点 Vi 和 Vj,满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通,也就是都含有至少一条通路,则称此有向图为强连通图。如下图所示就是一个强连通图。

图片[1]-强连通图,单向连通图,弱连通图,强连通分图-开心之家
单向连通图

设G=(V,E)是有向图,对于任意u,v∈V,从u可达v或者从v可达u,则称G为单向连通图(unilateral connected digraph)。

弱连通图

将有向图的所有的有向边替换为无向边,所得到的图称为原图的基图。如果一个有向图的基图是连通图,则有向图是弱连通图。

强连通分图

1.图V1是图V的强连通分支当且仅当同时满足以下三个条件:

a.V1是V的子图;

b.V1是强连通图;

c.V中不存在包含V1的强连通子图。

2.有向图D=(V,E)的每个点位于且仅位于D的某个强(弱)连通分支中。这就是说,求强连通分支数的时候得到的强连通分支的并(总和)应该包含图中的任何一个点。

简单举个例题(就拿学习通的一道选择题为例吧)

例:下图中强连通分支的个数为(2

图片[2]-强连通图,单向连通图,弱连通图,强连通分图-开心之家

再看一道网上的题,下图中其强连通分支数有三个,包含顶点为{1,2,3,4},{5},{6}。

图片[3]-强连通图,单向连通图,弱连通图,强连通分图-开心之家


注意:强连通图的强连通分支为1!

强连通图,单向连通图,弱连通图三者间的关系(重点)

强连通图必然是单向连通的,单向连通图必然是弱连通图,反之不一定。

网上查阅资料编撰,有不正确的请指出,谢谢大家!

© 版权声明
THE END
喜欢就支持一下吧
点赞11 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容