离散数学-图的连通性

1、离散数学-图的连通性16.2 图的连通性图的连通性 6.2.1 通路与回路通路与回路 初级通路初级通路(回路回路)与简单通路与简单通路(回路回路) 6.2.2 无向图的连通性与连通度无向图的连通性与连通度 连通图、连通分支连通图、连通分支 短程线与距离短程线与距离 点割集、割点、边割集、割边点割集、割点、边割集、割边(桥桥) 点连通度与边连通度点连通度与边连通度离散数学-图的连通性26.2 图的连通性图的连通性(续续) 6.2.3 有向图的连通性及其分类有向图的连通性及其分类 可达性可达性 弱连通、单向连通、强连通弱连通、单向连通、强连通 短程线与距离短程线与距离离散数学-图的连通性3通路与回

2、路通路与回路定义定义6.13 给定图给定图G=(无向或有向的无向或有向的), G中顶点与边中顶点与边的交替序列的交替序列 =v0e1v1e2elvl.若若 i(1 i l), ei=(vi 1,vi)(对于有向图对于有向图, ei=), 则称则称 为为v0到到vl的的通路通路, v0和和vl分别为通路的分别为通路的起点起点和和终点终点, l为为通路的通路的长度长度. 又若又若v0=vl, 则称则称 为为回路回路.若通路若通路(回路回路)中所有顶点中所有顶点(对于回路对于回路, 除除v0=vl)各异各异, 则称为则称为初级通路初级通路或或路径路径(初级回路初级回路或或圈圈). 长度为奇数的圈称作

3、长度为奇数的圈称作奇奇圈圈,长度为偶数的圈称作长度为偶数的圈称作偶圈偶圈若通路若通路(回路回路)中所有边各异中所有边各异, 则称为则称为简单通路简单通路(简单回路简单回路), 否则称为否则称为复杂通路复杂通路(复杂回路复杂回路)离散数学-图的连通性4说明说明(1) 表示方法表示方法 按定义用顶点和边的交替序列按定义用顶点和边的交替序列, =v0e1v1e2elvl 用边序列用边序列, =e1e2el 简单图中简单图中, 用顶点序列用顶点序列, =v0v1vl(2) 在无向图中在无向图中, 长度为长度为1的圈由环构成的圈由环构成.长度为长度为2的圈由两的圈由两条平行边构成条平行边构成. 在无向简

4、单图中在无向简单图中, 所有圈的长度所有圈的长度 3. 在有向图中在有向图中, 长度为长度为1的圈由环构成的圈由环构成. 在有向简单图中在有向简单图中, 所所有圈的长度有圈的长度 2.离散数学-图的连通性5说明说明(续续)(3) 初级通路初级通路(回路回路)是简单通路是简单通路(回路回路), 但反之不真但反之不真初级通路初级通路非初级的简单通路非初级的简单通路初级回路初级回路非初级的非初级的简单回路简单回路离散数学-图的连通性6通路与回路通路与回路(续续)定理定理6.3 在在n阶图中阶图中, 若从顶点若从顶点u到到v(u v)存在通路存在通路, 则从则从u到到v存在长度小于等于存在长度小于等于

5、n 1的初级通路的初级通路.证证 若通路中没有相同的顶点若通路中没有相同的顶点(即初级通路即初级通路), 长度必长度必 n 1.若有相同的顶点若有相同的顶点, 删去这两个顶点之间的这一段删去这两个顶点之间的这一段, 仍是仍是u到到v的通路的通路. 重复进行重复进行, 直到没有相同的顶点为止直到没有相同的顶点为止.定理定理6.4 在在n阶图中阶图中, 若存在若存在v到自身的简单回路到自身的简单回路, 则一定存则一定存在在v到自身长度小于等于到自身长度小于等于n的初级回路的初级回路.离散数学-图的连通性7无向图的连通性与连通分支无向图的连通性与连通分支设无向图设无向图G=, u,v Vu与与v连通

6、连通: 若若u与与v之间有通路之间有通路. 规定规定u与自身总是连通的与自身总是连通的.连通图连通图: 任意两点都连通的图任意两点都连通的图. 平凡图是连通图平凡图是连通图连通关系连通关系 R=| u,v V且且u与与v连通连通. R是等价关系是等价关系连通分支连通分支: V关于关于R的等价类的导出子图的等价类的导出子图设设V/R=V1,V2,Vk, G的连通分支为的连通分支为GV1,GV2,GVk连通分支数连通分支数p(G)=kG是连通图是连通图 p(G)=1离散数学-图的连通性8短程线与距离短程线与距离u与与v之间的短程线之间的短程线:u与与v之间长度最短的通路之间长度最短的通路(设设u与

7、与v连通连通)u与与v之间的距离之间的距离d(u,v):u与与v之间短程线的长度之间短程线的长度若若u与与v不连通不连通, 规定规定d(u,v)=.性质：性质：(1) d(u,v) 0, 且且d(u,v)=0 u=v(2) d(u,v)=d(v,u)(3) d(u,v)+d(v,w) d(u,w) 例如例如 a与与e之间的短程线之间的短程线:ace,afe. d(a,e)=2, d(a,h)= abcde f ghi离散数学-图的连通性9点割集与边割集点割集与边割集设无向图设无向图G=, v V, e E, VV, EE. 记记G v: 从从G中删除中删除v及关联的边及关联的边G V : 从从

8、G中删除中删除V 中所有的顶点及关联的边中所有的顶点及关联的边G e : 从从G中删除中删除eG E : 从从G中删除中删除E 中所有边中所有边定义定义6.15 设无向图设无向图G=, VV, 若若p(G V )p(G)且且 V V , p(G V )=p(G), 则称则称V 为为G的的点割集点割集. 若若v为点割为点割集集, 则称则称v为为割点割点.设设EE, 若若p(G E )p(G)且且 E E , p(G E )=p(G), 则称则称E 为为G的的边割集边割集. 若若e为边割集为边割集, 则称则称e为为割边割边或或桥桥.离散数学-图的连通性10实例实例说明：说明：Kn无点割集无点割集n

9、阶零图既无点割集，也无边割集阶零图既无点割集，也无边割集.若若G连通，连通，E 为边割集，则为边割集，则p(G E )=2若若G连通，连通，V 为点割集，则为点割集，则p(G V ) 2abcde fge1e2e3e4e5e6e7e8e9e, f点割集点割集:e,f ,割点割点:c,d 桥桥: e8, e9边割集边割集:e8,e9, e1,e2,e1, e3, e6, e1, e3, e4, e7离散数学-图的连通性11点连通度与边连通度点连通度与边连通度定义定义6.16 设无向连通图设无向连通图G=, (G)=min|V | | V 是是G的点割集或使的点割集或使G-V 成为平凡图成为平凡图

10、 称为称为G的的点连通度点连通度 (G)=min|E | | E 是是G的边割集的边割集称为称为G的的边连通度边连通度例如例如3 (G)=3 (G)=离散数学-图的连通性12点连通度与边连通度点连通度与边连通度(续续)说明说明:(1) 若若G是平凡图是平凡图, 则则 (G)=0, (G)=0.(2) 若若G是完全图是完全图Kn, 则则 (G)=n-1, (G)= n-1(3) 若若G中存在割点中存在割点, 则则 (G)=1;若若G中存在割边中存在割边, 则则 (G)= 1(4) 规定非连通图的点连通度和边连通度均为规定非连通图的点连通度和边连通度均为0定理定理6.5 对任何无向图对任何无向图G

11、, 有有 (G) (G) (G)离散数学-图的连通性13有向图的连通性及其分类有向图的连通性及其分类设有向图设有向图D=, u,v V, u可达可达v: u到到v有通路有通路. 规定规定u到自身总是可达的到自身总是可达的.u与与v相互可达相互可达: u可达可达v且且v可达可达uD弱连通弱连通(连通连通): 略去各边的方向所得无向图为连通图略去各边的方向所得无向图为连通图D单向连通单向连通: u,v V，u可达可达v 或或v可达可达u D强连通强连通: u,v V，u与与v相互可达相互可达D是强连通的当且仅当是强连通的当且仅当D中存在经过所有顶点的回路中存在经过所有顶点的回路D是单向连通的当且仅

12、当是单向连通的当且仅当D中存在经过所有顶点的通路中存在经过所有顶点的通路离散数学-图的连通性14实例实例 强连通强连通单连通单连通弱连通弱连通离散数学-图的连通性15有向图中的短程线与距离有向图中的短程线与距离u到到v的短程线的短程线: u到到v长度最短的通路长度最短的通路 (设设u可达可达v)距离距离d: u到到v的短程线的长度的短程线的长度若若u不可达不可达v, 规定规定d=.性质：性质： d 0, 且且d=0 u=v d+d d 注意注意: 没有对称性没有对称性离散数学-图的连通性166.3 图的矩阵表示图的矩阵表示 6.3.1 无向图的关联矩阵无向图的关联矩阵 6.3.2 有向无环图的

13、关联矩阵有向无环图的关联矩阵 6.3.3 有向图的邻接矩阵有向图的邻接矩阵 有向图中的通路数与回路数有向图中的通路数与回路数 6.3.4 有向图的可达矩阵有向图的可达矩阵离散数学-图的连通性17无向图的关联矩阵无向图的关联矩阵设无向图设无向图G=, V=v1, v2, , vn, E=e1, e2, , em. 令令mij为为vi与与ej的关联次数的关联次数, 称称(mij)n m为为G的关联矩阵的关联矩阵, 记为记为M(G). mij的可能取值为的可能取值为:0,1,2例如例如e1e2e3e4e5e6v5v1v2v3v4M(G)=2 1 1 0 0 00 1 0 1 1 10 0 0 0 1

14、 10 0 0 0 0 00 0 1 1 0 0 离散数学-图的连通性18关联矩阵的性质关联矩阵的性质列相同列相同列与第列与第第第是平行边是平行边与与kjeemmnivdmmjmkjjiijimjijniij)4(2)3(,.,2 , 1),()2(,.,2 , 1, 2)1(,11(6) ej是环是环 第第j列的一个元素为列的一个元素为2, 其余为其余为0(5) vi是孤立点是孤立点 第第i行全为行全为0离散数学-图的连通性19无环有向图的关联矩阵无环有向图的关联矩阵则称则称(mij)n m为为D的关联矩阵的关联矩阵, 记为记为M(D).的终点的终点为为，不关联不关联与与，的始点的始点为为j

15、ijijiijevevevm10,1设无环有向图设无环有向图D=, V=v1, v2, , vn, E=e1, e2, , em. 令令(3) ej与与ek是平行边是平行边 第第j列与第列与第k列相同列相同(2) 第第i行行1的个数等于的个数等于d+(v), 第第i行行-1的个数等于的个数等于d-(v)性质性质: (1) 每列恰好有一个每列恰好有一个1和一个和一个-1离散数学-图的连通性20实例实例v1v2v3v4e2e1e3e4e5e6e7M(D)=-1 1 0 0 0 1 1 0 -1 1 0 0 0 0 0 0 -1 -1 -1 1 -1 1 0 0 1 1 0 0离散数学-图的连通性2

16、1有向图的邻接矩阵有向图的邻接矩阵环的个数环的个数中中等于等于性质性质Damanjvdanivdaniiijiijjniijinjij1)1(,)1(1)1(1)1()4()3(,.,2 , 1),()2(,.,2 , 1),()1(:设有向图设有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令令 为顶点为顶点vi邻接到顶点邻接到顶点vj边的条数，称边的条数，称( )m n为为D的邻接矩阵的邻接矩阵, 记作记作A(D), 简记作简记作A.)1(ija)1(ija离散数学-图的连通性22实例实例A=1 1 0 00 0 1 01 0 0 01 0 2 0v1v2v3

17、v4离散数学-图的连通性23有向图中的通路数与回路数有向图中的通路数与回路数定理定理6.6 设设A为为n阶有向图阶有向图D的邻接矩阵的邻接矩阵, 则则Al(l 1)中元素中元素 等于等于D中中vi到到vj长度为长度为 l 的通路的通路(含回路含回路)数数, 等于等于vi到自身长到自身长度为度为l 的回路数的回路数, 等于等于D中长度为中长度为 l 的通路的通路(含回路含回路)总数总数, 等于等于D中长度为中长度为 l 的回路总数的回路总数. )(liia)(lija ninjlija11)( niliia1)(离散数学-图的连通性24有向图中的通路数与回路数有向图中的通路数与回路数(续续)推论

18、推论 设设Bl=A+A2+Al(l 1), 则则Bl中元素中元素 等于等于D中中vi到到vj长度小于等于长度小于等于 l 的通路的通路(含回路含回路)数数, 等于等于D中中vi到到vi长度长度小于等于小于等于 l 的回路数的回路数, 等于等于D中长度小于等于中长度小于等于l 的的通路通路(含回路含回路)数数, 为为D中长度小于等于中长度小于等于l 的回路数的回路数. ninjlijb11)( niliib1)()(lijb)(liib离散数学-图的连通性25实例实例(续续) 说明说明: 在这里在这里, 通路和回路数是定义意义下的通路和回路数是定义意义下的A=1 1 0 00 0 1 01 0

19、0 01 0 2 0A2=1 1 1 01 0 0 01 1 0 03 1 0 0A3=2 1 1 01 1 0 01 1 0 03 3 1 0A4=3 2 1 01 1 0 02 1 1 04 3 1 0v1到到v2长为长为3的通路有的通路有1条条v1到到v3长为长为3的通路有的通路有1条条v1到自身长为到自身长为3的回路有的回路有2条条D中长为中长为3的通路共有的通路共有15条条,其中回路其中回路3条条v1v2v3v4离散数学-图的连通性26有向图的可达矩阵有向图的可达矩阵性质性质:P(D)主对角线上的元素全为主对角线上的元素全为1. D强连通当且仅当强连通当且仅当P(D)的元素全为的元素全为1.设有向图设有向图D=, V=v1, v2, , v