3.4 强连通分支.doc

有向图的连通性包含两个部分,强连通与弱连通。强连通:对有向图中一个顶点对,如果存在到和到的路,则称,是连通的。若图中任意两点都是连通的,则称图G为强连通图。弱连通图:对有向图,如果对图中任一顶点对和,有一个顶点序列,使,并且对于,或者,或者,则称图G是弱连通的。强连通分支:有向图的一个强连通分支是一个最大的强连通子图。等价关系S:对于V中的,Û从到有路,从到也有路。则由S所确定的每一个等价类以及其中点对所决定的关联边构成了图G的一个强连通分支。凝图:有向图G的强连通分支中每一个都能收缩为一点,产生一个新的没有回路的有向图。称为G的凝图,用表示。其中有个元素,在中Û从中某顶点到中某顶点的有一条边。与无向图中求图的连通分支相类似,可以借助DFS来寻找,但在有向图中情况却要复杂得多。DFS树中除树边、向后边外,可能还有向前边和交叉边。且由交叉边的性质知,交叉边是从右到左的。关系£:£Û在DFS搜索中,遇到之后才遇到,并且不是的子孙。我们把这个关系读着在的左边。,并且,则必有£或者,之中的一个顶点是另一个顶点的子孙。OLDEST(v):是树中的一个顶点,OLDEST(v)是T中从出发沿着树边、回边和交叉边能到达的最早(最接近于根部)的祖先。,和在同一强连通分支ÛOLDEST(v)=OLDEST(w)。求图中强连通分支的办法:1通过计算每一点的OLDEST()值2改进:求LOW(v)LOW(v):LOW(v)是v所在的同一个强连通分支中编号number最小的那一个顶点。:对于V中的和,和是在同一强连通分支在一个深度优先搜索树中,不同于根的一个顶点v是一个割点Ûv不是叶子结点,且v的某子树没有关联于v的一个真祖先的向后边。当LOW(v)=number(v)时移去所有的子树,则该子树就是原图的一个强连通分支。因为若有交叉边从右连结到这个连通分支C上,则交叉边上的起点不可能在这一连通分支上C。否则,就不可能是交叉边,而是树边。LOW(v)满足下列规则:1、初始值取为number(v)2、当查到有从v出发的一条向后边(v,w)时back(v)¬min{back(v),number(w)}从w返回到v时,back(v)¬min{back(v),back(w)}当从w返回到v时,测试back(w)≥number(v),如果条件满足,则v就是一个割点集颤酒码冬缆拾悉秘挟坏虱怒段后啼卫涵吻趟悦绎赃阳烧稳签极涅恋裹呕苦强赃哗幽给筋隔缓毅醇颠爱身滋跟沿炼惨做哼糯遗吾淘拯搭丢砒艰蓖雌逗崇魁需