【离散数学】单向连通和弱连通的区别

Snip20160622_1

单向连通一定是弱连通的。
but,弱连通不一定是单向连通~~

举个栗子~
Snip20160622_3

是弱连通~但不是单向连通~因为a和b结点,a不能到b,b不能到a~~

概念:
单向连通图
如果有向图中,对于任意节点v1和v2,至少存在从v1到v2和从v2到v1的路径中的一条,则原图为单向连通图。
即设G=<V,E>是有向图,如果u->v意味着图G至多包含一条从u到v的简单路径,则图G为单连通图。
强连通图、连通图、单向连通图三者之间的关系是,强连通图必然是单向连通的,单向连通图必然是弱连通图。
弱连通图
将有向图的所有的有向边替换为无向边,所得到的图称为原图的基图。如果一个有向图的基图是连通图,则有向图是弱连通图。

❤❤点击这里 -> 订阅PAT、蓝桥杯、GPLT天梯赛、LeetCode题解离线版❤❤