强连通分支的性质 Lemma 22.13 Component Graph: GSCC=(VSCC,EScC) ≥如果C和C是图G的两个不同的强连通分 where Vscc is the representation of the 支,设u,V属于C:u,V属于C,若有u到 strongly connected component, ESCc is the u的通路,则必没有v到v的通路 representation of the edges between the z证明:平凡 components Is a dag eTwo way connection 引理22.14 推论22.15 设C和C是图G的两个强连通分支,设(uV) E对于G则上述引理的不等式正好相反 是一条连接C和C的边,其中u属于C,V属 证明:平凡 于C,则当DFS完成后有:f(C)>f(C) 情况1:C中元素首先发现:白色路径定理 情况2:C中元素首先发现:C完成后才能进入 定理2216 证明(续 家上述算法可以得到一个图的强连通分支 此时,C中其它顶点必为白色,由白色路径 E证明:提示:对GT上进行DFS过程中生产 定理得知,C中的其它顶点一定是此次DFS 的每一棵树是强连通分支进行归纳法 搜索中u的后代 k=0即开始时是正确的【平凡】 另外,所有GT其它从C引出的边都在已经发 设前k棵树是强连通分支,我们来分析第k+ 现的强连通分支内,故不会有其它非C的未 棵树:设此树之根为u,而u在图的强连通分支 访问的点在完成u的搜索中被访问到。 即u为根的树是G的一个强连通分支 u=C)>1(C),其中C是任何没有被发现的连通 1010 清华大学 宋斌恒 55 强连通分支的性质 Component Graph: GSCC=(VSCC,ESCC), where VSCC is the representation of the strongly connected component, ESCC is the representation of the edges between the components. GSCC is a dag. Two way connection 清华大学 宋斌恒 56 Lemma 22.13 Lemma 22.13 如果C和C’是图G的两个不同的强连通分 支，设u， v属于C；u’, v’属于C’，若有u到 u’的通路，则必没有v’到v的通路。 证明：平凡 清华大学 宋斌恒 57 引理22.14 设C和C’是图G的两个强连通分支，设(u,v) 是一条连接C和C’的边，其中u属于C，v属 于C’，则当DFS完成后有：f(C)>f(C’). 证明： 情况1：C中元素首先发现：白色路径定理 情况2：C’中元素首先发现：C’完成后才能进入 C 清华大学 宋斌恒 58 推论22.15 对于GT则上述引理的不等式正好相反。 证明：平凡 清华大学 宋斌恒 59 定理22.16 上述算法可以得到一个图的强连通分支。 证明：提示：对GT上进行DFS过程中生产 的每一棵树是强连通分支进行归纳法。 k＝0即开始时是正确的【平凡】 设前k棵树是强连通分支，我们来分析第k＋1 棵树：设此树之根为u，而u在图的强连通分支 C内，故有 f[u]=f(C)>f(C’),其中C’是任何没有被发现的连通 分支 清华大学 宋斌恒 60 证明（续） 此时，C中其它顶点必为白色，由白色路径 定理得知，C中的其它顶点一定是此次DFS 搜索中u的后代， 另外，所有GT其它从C引出的边都在已经发 现的强连通分支内，故不会有其它非C的未 访问的点在完成u的搜索中被访问到。 即u为根的树是G的一个强连通分支