连通度.ppt

简单通(回)路,初级通(回)路 通路，回路 简单(simple)通路(迹) : 没有重复边的通路 简单(simple)回路(闭迹) : 没有重复边的回路 初级(element)通路(路径(path)): 没有重复顶点的通路 初级(element)回路(圈(cycle)): 没有重复顶点的回路 短通路（回路）存在性 定理1: 在n阶图G中,若从不同顶点vi到vj有通路,则从vi到vj有长度小于等于n-1的（初级）通路. # 定理2: 在n阶图G中,若有从顶点vi到自身的简单回路,则有从vi到自身长度小于等于n的初级回路. # 短程线,距离,直径 短程线: u,v之间长度最短的通路 短程线也称为测地线. 距离(distance): dG(u,v) = u,v之间短程线的长度(或?) 直径d(G)：图中两点间的最大距离 例: d(Kn)=1(n?2), d(Cn)=?n/2?, d(N1)=0, d(Nn)=? (n?2) 连通(connected) 连通(connected): 无向图G=V,E, u~v ? u与v之间有通路 规定: ?u(u~u), 连通关系~是等价关系,商集是 V/~ = { V1,V2,…,Vk } 连通分支(component): G[Vi], (i=1,…,k) 连通分支数: p(G)=|V/~|=k 连通图: p(G)=1, 非连通图p(G)1 连通分支(举例) p(G)=3 可达(reachable) 可达: 有向图D=V,E, u?v ? 从u到v有(有向)通路 规定: ?u(u?u), 可达关系是自反,传递的 双向可达: u ? v ? u?v ? v?u 双向可达关系是等价关系, 其等价类的导出子图称为强连通分支 有向图的连通分支 强连通分支(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}] (弱)连通分支: 与单向连通分支相同 有向图的连通分支举例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 如何定义连通度 问题: 如何定量比较无向图连通性的强与弱? 如何定义连通度 点连通度: 为了破坏连通性,至少需要删除多少个顶点? 边连通度: 为了破坏连通性,至少需要删除多少条边? 说明: “破坏连通性”指 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} 割点(cut-point / cut-vertex) 割点: v是割点 ? {v}是割集 例: G1中f是割点, 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)} 割边(cut-edge)(桥) 割边: (u,v)是割边 ? {(u,v)}是边割