有向图的强连通分支

《有向图的强连通分支》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、有向图的强连通分支有向图的连通性包含两个部分，强连通与弱连通。强连通：对有向图中一个顶点对，如果存在到和到的路，则称，是连通的。若图中任意两点都是连通的，则称图G为强连通图。弱连通图：对有向图，如果对图中任一顶点对和，有一个顶点序列，使，并且对于，或者，或者，则称图G是弱连通的。强连通分支：有向图的一个强连通分支是一个最大的强连通子图。等价关系S：对于V中的，Û从到有路，从到也有路。则由S所确定的每一个等价类以及其中点对所决定的关联边构成了图G的一个强连通分支。凝图：有向图G的强连通分支中每一个都能收缩为一点，产生一个新的没有回路的有向图。称为G的凝图，用表示。其中有个元素，在中Û从中某顶点到

2、中某顶点的有一条边。与无向图中求图的连通分支相类似，可以借助DFS来寻找，但在有向图中情况却要复杂得多。DFS树中除树边、向后边外，可能还有向前边和交叉边。且由交叉边的性质知，交叉边是从右到左的。关系£：£Û在DFS搜索中，遇到之后才遇到，并且不是的子孙。我们把这个关系读着在的左边。引理3.4如果和是在V中，并且，则必有£或者，之中的一个顶点是另一个顶点的子孙。OLDEST(v):是树中的一个顶点，OLDEST(v)是T中从出发沿着树边、回边和交叉边能到达的最早（最接近于根部）的祖先。定理3.5如果和在V中，和在同一强连通分支ÛOLDEST(v)=OLDEST(w)。求图中强连通分支的办法：1

3、通过计算每一点的OLDEST()值2改进：求LOW(v)LOW(v):LOW(v)是v所在的同一个强连通分支中编号number最小的那一个顶点。定理3.5：对于V中的和，和是在同一强连通分支在一个深度优先搜索树中，不同于根的一个顶点v是一个割点Ûv不是叶子结点，且v的某子树没有关联于v的一个真祖先的向后边。当LOW(v)=number(v)时移去所有的子树，则该子树就是原图的一个强连通分支。因为若有交叉边从右连结到这个连通分支C上，则交叉边上的起点不可能在这一连通分支上C。否则，就不可能是交叉边，而是树边。LOW(v)满足下列规则：1、初始值取为number(v)2、当查到有从v出发的一条向后

4、边(v,w)时back(v)¬min{back(v),number(w)}3、从w返回到v时，back(v)¬min{back(v),back(w)}当从w返回到v时，测试back(w)≥number(v),如果条件满足，则v就是一个割点