2-3通路案例.ppt

* * 强连通(strongly connected) 强连通(双向连通): 有向图的任何一对顶点之间都双向可达 a b c d e j f g h i ? * * 定理14.8 定理14.8: 有向图D强连通 ? D中有回路过每个顶点至少一次. 证明: (?) 显然 (?) 设V(D)={v1,v2,…,vn}, 设?i,j是从vi到vj的有向通路, 则?1,2+?2,3+…+?n-1,n+?n,1是过每个顶点至少一次的回路. # 说明: 不一定有简单回路,反例如下: * * 定理14.9 定理14.9: 有向图D单向连通 ? D中有通路过每个顶点至少一次. 证明: (?) 显然 (?) ? 说明: 不一定有简单通路,反例如下: * * 引理 引理: 有向图D单向连通 ,则对于任意的V’?V(D), 存在v’?V’,使得任意的v?V’, v’与v之间至少有一条单向通路(v’→v). 定理14.9证明: V(D)中存在v1可达V(D)中的其余顶点; V1=V(D)-{v1}中存在v2可达V1中的其余顶点; ……,于是有v1→v2 →……→vn-1 →vn # * * 有向图的连通分支 强连通分支(strong component): 极大强连通子图 单向连通分支: 极大单向连通子图 弱连通分支(weak component): 极大弱连通子图 * * 有向图的连通分支举例1 强连通分支: G[{a}],G[{b}],G[{c,d,e,h,i}], G[{f}],G[{g}],G[{j,k,l}] 单向连通分支: G[{a,b}],G[{c,d,e,h,i,f,g}], G[{j,k,l}] (弱)连通分支: 与单向连通分支相同 a b c e d f g h i k l j * * 有向图的连通分支举例2 强连通分支: G[{a}], G[{b}], G[{c}], G[{d}], G[{e,f,g,h}] 单向连通分支: G[{a,b,c}], G[{c,d}], G[{d,e,f,g,h}] (弱)连通分支: G b c a d e f h g 划分 覆盖 * * 如何定量连通性？ 问题: 如何定量比较无向图连通性的强与弱? * * 连通度 点连通度: 为了破坏连通性,至少需要删除多少个顶点? 边连通度: 为了破坏连通性,至少需要删除多少条边? 说明: “破坏连通性”指 p(G-V’)p(G), 或p(G-E’)p(G),即“变得更加不连通” * * 删除(delete) G-e = V, E-{e} , 删除边e G-E’ = V, E-E’ , 删除边集E’ G-v = V-{v}, E-IG(v) , 删除顶点v以及v所关联的所有边 G-V’ = V-V’, E-IG(V’) ,删除顶点集V’以及V’所关联的所有边 * * 割集(cutset) 点割集(vertex cut) 边割集(edge cut) 割点(cut vertex) 割边(cut edge)(桥)(bridge) * * 点割集(vertex cutset) 点割集: 无向图G=V,E, ??V’?V, 满足 (1) p(G-V’)p(G); (2) 极小性: ? V’’?V’, p(G-V’’)=p(G), 则称V’为点割集. 说明: “极小性”是为了保证点割集概念的非平凡性 * * 点割集(举例) G1: {f},{a,e,c},{g,k,j},{b,e,f,k,h} G2: {f},{a,e,c},{g,k,j},{b,e,f,k,h} a b c d f e g h k j i a b c e f d j i g h k G1 G2 * * 割点(cut-point / cut-vertex) 割点: v是割点 ? {v}是割集 例: G1中f是割点, G2中无割点 a b c d f e g h k j i a b c e f d j i g h k G1 G2 * * 边割集(edge cutset) 边割集: 无向图G=V,E, ??E’?E, 满足 (1) p(G-E’)p(G); (2) 极小性: ?E’’?E’, p(G-E’’)=p(G), 则称E’为边割集. 说明: “极小性”是为了保证边割集概念的非平凡性 * * 边割集(举例) G1: {(a,f),(e,f),(d,f)}, {(f,g),(f,k),(f,j)} {(a,f),(e,f),(d,f),(f,g),(f,k),(f,j)}, {(c,d)} G2: {(b,a),(b,e),(b,c)} a b c d f e g h k j i a b c e f d j i g h k G1 G