连通度和图的矩阵表示

1、2021-11-291简单通(回)路,初级通(回)路n通路，回路n简单(simple)通路(迹) : 没有重复边的通路n简单(simple)回路(闭迹) : 没有重复边的回路n初级(element)通路(路径(path): 没有重复顶点的通路n初级(element)回路(圈(cycle): 没有重复顶点的回路2021-11-292短通路（回路）存在性n定理1: 在n阶图G中,若从不同顶点vi到vj有通路,则从vi到vj有长度小于等于n-1的（初级）通路. #n定理2: 在n阶图G中,若有从顶点vi到自身的简单回路,则有从vi到自身长度小于等于n的初级回路. #2021-11-293连通(con

2、nected)n连通(connected): 无向图G=,uv u与v之间有通路n规定: u(uu), 连通关系是等价关系,商集是 V/ = V1,V2,Vk n连通分支(component): GVi, (i=1,k)n连通分支数: p(G)=|V/|=k n连通图: p(G)=1, 非连通图p(G)12021-11-294有向图的连通分支n强连通分支(strong component): 极大强连通子图n单向连通分支: 极大单向连通子图n弱连通分支(weak component): 极大弱连通子图2021-11-295如何定义连通度n点连通度: 为了破坏连通性,至少需要删除多少个顶点?n边

3、连通度: 为了破坏连通性,至少需要删除多少条边?n说明: “破坏连通性”指 p(G-V)p(G), 或p(G-E)p(G),即“变得更加不连通”2021-11-296点割集(vertex cutset)n点割集: 无向图G=, VV, 满足 (1) p(G-V)p(G); (2) 极小性: VV, p(G-V)=p(G),则称V为点割集.n说明: “极小性”是为了保证点割集概念的非平凡性2021-11-297边割集(edge cutset)n边割集: 无向图G=, EE, 满足 (1) p(G-E)p(G); (2) 极小性: EE, p(G-E)=p(G),则称E为边割集.n说明: “极小性

4、”是为了保证边割集概念的非平凡性2021-11-298点连通度(vertex-connectivity)n点连通度: G是无向连通非完全图,(G) = min |V| | V是G的点割集 n规定: (Kn) = n-1, G非连通: (G)=0n例: (G)=1, (H)=2, (F)=3, (K5)=4 GHF2021-11-299边连通度(edge-connectivity)n边连通度: G是无向连通图,(G) = min |E| | E是G的边割集 n规定: G非连通: (G)=0n例: (G)=1, (H)=2, (F)=3, (K5)=4GHF2021-11-2910k-连通图, k

5、-边连通图nk-连通图(k-connected): (G)knk-边连通图(k-edge-connected): (G)k n例: 彼得森图 =3, =3; 它是1-连通图, 2-连通图,3-连通图, 但不是4-连通图; 它是1-边连通图, 2-边连通图,3-边连通图,但不是4-边连通图2021-11-2911Whitney定理n定理14.7: .n证明: 不妨设G是3阶以上连通简单非完全图. () 设d(v)=, 则|IG(v)|=, IG(v)中一定有边割集E, 所以|E|IG(v)|=. () 设E是边割集,|E|=,从V(E)中找出点割集V,使得|V|, 所以|V|. 2021-11-

6、2912引理1n引理1: 设E是边割集,则p(G-E)=p(G)+1.n证明: 考虑每条边e的删除，都有p(G)+1p(G-e) p(G), 把E中的边依次删除最多使连通分支数加1. #n说明: 点割集无此性质2021-11-2913引理2n引理2:设E是非完全图G的边割集, (G)=|E|,G-E的2个连通分支是G1,G2,则存在uV(G1),vV(G2),使得(u,v)E(G)n证明: (反证)否则(G)=|E| =|V(G1)|V(G2)|V(G1)|+|V(G2)|-1=n-1, 与G非完全图相矛盾! #n说明: a1b1(a-1)(b-1)=ab-a-b+10 aba+b-1.202

7、1-11-2914Whitney定理(续)n证明(续): () 设G-E的2个连通分支是G1,G2. 设uV(G1),vV(G2),使得(u,v)E(G). 如下构造V:eE, 选择e的异于u,v的一个端点放入V. |V|E|. G-VG-E=G1G2, 所以V中含有点割集V. 所以|V|V|E|=.2021-11-2915背景nHassler Whitney(19071989),美国数学家, 20世纪30年代发表了十几篇图论论文,定义了“对偶图”概念,推动了四色定理的研究.一生的最后20年致力于数学教育,提倡应当让年轻人用自己的直觉(intuition)来解决问题,而不是教一些与他们的经验无

8、关的技巧和结果.2021-11-2916=示例n=mKm,mKnn=n-12021-11-2917=示例n=1, =3abcdfeghkji2021-11-2918=示例n=2, =3n=1, =22021-11-2919示例n=1, =2, =32021-11-2920图的表示n一个图可以用数学定义来描述，也可以用图形表示；还可以用矩阵来表示图，这样便于用代数知识来研究图的性质，同时也便于用计算机处理。 2021-11-2921图的矩阵表示n1. 关联矩阵M(D), M(G) n2. 邻接矩阵A(D), 邻接矩阵A(G)n3. 用A的幂求不同长度通路(回路)总数n4. 可达矩阵P(D), 连

9、通矩阵P(G)2021-11-2922无向图关联矩阵n设G=是无向图,V=v1,v2,vn, E=e1,e2,emn关联矩阵(incidence matrix): M(G)=mijnm,(每个顶点确定一行,每条边确定一列), mij = vi与ej的关联次数 2, vi与ej关联，且ej是环 mij = 1, vi与ej关联，且ej不是环 0, vi不与ej关联100100111000010011001111)(6543214321eeeeeevvvvGM2021-11-2923无向图关联矩阵(例)1234561234111100( )110010000111001001eeeeeevM Gv

10、vvv1v2v4v3e1e2e3e4e6e52021-11-2924无向图关联矩阵(性质)n每列和为2: ni=1mij=2 ( ni=1mj=1mij=2m )n每行和为d(v): d(vi)=mj=1mij n孤立点:全0行n平行边: 相同两列n环：对应列中只有一个2其余是0100100111000010011001111)(6543214321eeeeeevvvvGM)()()()(21kGMGMGMGM2021-11-2925有向图关联矩阵n设D=是无环有向图, V=v1,v2,vn, E=e1,e2,emn关联矩阵(incidence matrix): M(D)=mijnm, ,(每个顶点确定一行,每条边确定一列)n 1, vi是ej的起点 mij = 0, vi与ej不关联 -1, vi是ej的终点110000111100001011000111)(6543214321eeeeeevvvvDM2021-11-2926有向图关联矩阵(例)110000111100001011000111)(6543214321eeeeeevvvvDMv1v2v4v3e1e2e3e5e4e62021-11-2927有向图关联矩阵(性质)n每列和为零: ni=1mij=0 n每行绝对值和为d(v): d(vi)=m