离散数学623图的连通性.ppt

6.2 图的连通性图的连通性•6.2.1 通路与回路通路与回路–初级通路初级通路(回路回路)与简单通路与简单通路(回路回路)•6.2.2 无向图的连通性与连通度无向图的连通性与连通度–连通图、连通分支连通图、连通分支–短程线与距离短程线与距离–点割集、割点、边割集、割边点割集、割点、边割集、割边(桥桥)–点连通度与边连通度点连通度与边连通度16.2 图的连通性图的连通性(续续)•6.2.3 有向图的连通性及其分类有向图的连通性及其分类–可达性可达性–弱连通、单向连通、强连通弱连通、单向连通、强连通–短程线与距离短程线与距离2通路与回路通路与回路 给定图给定图G=(无向或有向的无向或有向的), G中顶点与边中顶点与边的交替序列的交替序列 =v0e1v1e2…elvl.若若 i(1 i l), ei=(vi 1,vi)(对对于于有有向向图图, ei=), 则则称称 为为v0到到vl的的通路通路, v0和和vl分别为通路的分别为通路的起点起点和和终点终点, l为为通路的通路的长度长度. 又若又若v0=vl, 则称则称 为为回路回路.若通路若通路(回路回路)中所有顶点中所有顶点(对于回路对于回路, 除除v0=vl)各异各异, 则称为则称为初级通路初级通路或或路径路径(初级回路初级回路或或圈圈). 长度为奇数的圈称作长度为奇数的圈称作奇奇圈圈,长度为偶数的圈称作长度为偶数的圈称作偶圈偶圈若通路若通路(回路回路)中所有边各异中所有边各异, 则称为则称为简单通路简单通路(简单回路简单回路), 否则称为否则称为复杂通路复杂通路(复杂回路复杂回路)3说明说明(1) 表示方法表示方法 ①① 按定义用顶点和边的交替序列按定义用顶点和边的交替序列,  =v0e1v1e2…elvl ②② 用边序列用边序列,  =e1e2…el ③③ 简单图中简单图中, 用顶点序列用顶点序列,  =v0v1…vl(2) 在无向图中在无向图中, 长度为长度为1的圈由环构成的圈由环构成.长度为长度为2的圈由两的圈由两条平行边构成条平行边构成. 在无向简单图中在无向简单图中, 所有圈的长度所有圈的长度 3. 在有向图中在有向图中, 长度为长度为1的圈由环构成的圈由环构成. 在有向简单图中在有向简单图中, 所所有圈的长度有圈的长度 2.4说明说明(续续)(3) 初级通路初级通路(回路回路)是简单通路是简单通路(回路回路), 但反之不真但反之不真初级通路初级通路非初级的简单通路非初级的简单通路初级回路初级回路非初级的非初级的简单回路简单回路5通路与回路通路与回路(续续) 在在n阶图中阶图中, 若从顶点若从顶点u到到v(u v)存在通路存在通路, 则从则从u到到v存在长度小于等于存在长度小于等于n 1的初级通路的初级通路.证证 若通路中没有相同的顶点若通路中没有相同的顶点(即初级通路即初级通路), 长度必长度必  n 1.若有相同的顶点若有相同的顶点, 删去这两个顶点之间的这一段删去这两个顶点之间的这一段, 仍是仍是u到到v的通路的通路. 重复进行重复进行, 直到没有相同的顶点为止直到没有相同的顶点为止. 在在n阶图中阶图中, 若存在若存在v到自身的简单回路到自身的简单回路, 则一定存则一定存在在v到自身长度小于等于到自身长度小于等于n的初级回路的初级回路.6无向图的连通性与连通分支无向图的连通性与连通分支设无向图设无向图G=, u,v Vu与与v连通连通: 若若u与与v之间有通路之间有通路. 规定规定u与自身总是连通的与自身总是连通的.连通图连通图: 任意两点都连通的图任意两点都连通的图. 平凡图是连通图平凡图是连通图连通关系连通关系 R={| u,v  V且且u与与v连通连通}. R是等价关系是等价关系连通分支连通分支: V关于关于R的等价类的导出子图的等价类的导出子图设设V/R={V1,V2,…,Vk}, G的连通分支为的连通分支为G[V1],G[V2],…,G[Vk]连通分支数连通分支数p(G)=kG是连通图是连通图 p(G)=17短程线与距离短程线与距离u与与v之间的短程线之间的短程线:u与与v之间长度最短的通路之间长度最短的通路(设设u与与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 ghi8点割集与边割集点割集与边割集设无向图设无向图G=, v V, e E, VV, EE. 记记G v: 从从G中删除中删除v及关联的边及关联的边G V : 从从G中删除中删除V 中所有的顶点及关联的边中所有的顶点及关联的边G e : 从从G中删除中删除eG E : 从从G中删除中删除E 中所有边中所有边 设无向图设无向图G=, VV, 若若p(G V )>p(G)且且 V  V , p(G V )=p(G), 则则称称V 为为G的的点点割割集集. 若若{v}为为点割点割集集, 则称则称v为为割点割点.设设EE, 若若p(G E )>p(G)且且 E  E , p(G E )=p(G), 则称则称E 为为G的的边割集边割集. 若若{e}为边割集为边割集, 则称则称e为为割边割边或或桥桥.9实例实例说明：说明：Kn无点割集无点割集n阶零图既无点割集，也无边割集阶零图既无点割集，也无边割集.若若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}10点连通度与边连通度点连通度与边连通度 设无向连通图设无向连通图G=,  (G)=min{|V | | V 是是G的点割集或使的点割集或使G-V 成为平凡图成为平凡图} 称为称为G的的点连通度点连通度  (G)=min{|E | | E 是是G的边割集的边割集}称为称为G的的边连通度边连通度例如例如3 (G)=3 (G)=11点连通度与边连通度点连通度与边连通度(续续)说明说明:(1) 若若G是平凡图是平凡图, 则则 (G)=0,  (G)=0.(2) 若若G是完全图是完全图Kn, 则则 (G)=n-1,  (G)= n-1(3) 若若G中存在割点中存在割点, 则则 (G)=1;若若G中存在割边中存在割边, 则则 (G)= 1(4) 规定非连通图的点连通度和边连通度均为规定非连通图的点连通度和边连通度均为0 对任何无向图对任何无向图G, 有有  (G)    (G)   (G)12有向图的连通性及其分类有向图的连通性及其分类设有向图设有向图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是单向连通的当且仅当是单向连通的当且仅当D中存在经过所有顶点的通路中存在经过所有顶点的通路13实例实例 强连通强连通单连通单连通弱连通弱连通14有向图中的短程线与距离有向图中的短程线与距离u到到v的短程线的短程线: u到到v长度最短的通路长度最短的通路 (设设u可达可达v)距离距离d: u到到v的短程线的长度的短程线的长度若若u不可达不可达v, 规定规定d=∞.性质：性质： d 0, 且且d=0  u=v d+d  d 注意注意: 没有对称性没有对称性15 图的矩阵表示图的矩阵表示•6.3.1 无向图的关联矩阵无向图的关联矩阵•6.3.2 有向无环图的关联矩阵有向无环图的关联矩阵•6.3.3 有向图的邻接矩阵有向图的邻接矩阵–有向图中的通路数与回路数有向图中的通路数与回路数•6.3.4 有向图的可达矩阵有向图的可达矩阵16无向图的关联矩阵无向图的关联矩阵设无向图设无向图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 10 0 0 0 0 00 0 1 1 0 0 17关联矩阵的性质关联矩阵的性质(6) ej是环是环  第第j列的一个元素为列的一个元素为2, 其余为其余为0(5) vi是孤立点是孤立点  第第i行全为行全为018无环有向图的关联矩阵无环有向图的关联矩阵则称则称(mij)n m为为D的关联矩阵的关联矩阵, 记为记为M(D).设无环有向图设无环有向图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和一个和一个-119实例实例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 020有向图的邻接矩阵有向图的邻接矩阵设有向图设有向图D=, V={v1, v2, …, vn}, E={e1, e2, …, em}, 令令 为顶点为顶点vi邻接到顶点邻接到顶点vj边的条数，称边的条数，称( )m n为为D的邻接矩的邻接矩阵阵, 记作记作A(D), 简记作简记作A.21实例实例A=1 1 0 00 0 1 01 0 0 01 0 2 0v1v2v3v422有向图中的通路数与回路数有向图中的通路数与回路数定理定理6.6 设设A为为n阶有向图阶有向图D的邻接矩阵的邻接矩阵, 则则Al(l 1)中元素中元素 等等于于D中中vi到到vj长长度度为为 l 的的通通路路(含含回回路路)数数, 等等于于vi到到自自身身长长度为度为l 的回路数的回路数, 等于等于D中长度为中长度为 l 的通路的通路(含回路含回路)总数总数, 等于等于D中长度为中长度为 l 的回路总数的回路总数. 23有向图中的通路数与回路数有向图中的通路数与回路数(续续)推推论论 设设Bl=A+A2+…+Al(l 1), 则则Bl中中元元素素 等等于于D中中vi到到vj长长度度小小于于等等于于 l 的的通通路路(含含回回路路)数数, 等等于于D中中vi到到vi长长度度小于等于小于等于 l 的回路数的回路数, 等于等于D中长度小于等于中长度小于等于l 的的通路通路(含回路含回路)数数, 为为D中长度小于等于中长度小于等于l 的回路数的回路数.24实例实例(续续) 说明说明: 在这里在这里, 通路和回路数是定义意义下的通路和回路数是定义意义下的A=1 1 0 00 0 1 01 0 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条条v1v2v3v425有向图的可达矩阵有向图的可达矩阵性质性质:P(D)主对角线上的元素全为主对角线上的元素全为1. D强连通当且仅当强连通当且仅当P(D)的元素全为的元素全为1.设有向图设有向图D=, V={v1, v2, …, vn}, 令令 称称(pij)n n为为D的可达矩阵的可达矩阵, 记作记作P(D), 简记为简记为P. 26实例实例例例1 (1) v1到到v4,v4到到v1长为长为3的通路各有多少条的通路各有多少条?(2) v1到自身长为到自身长为1,2,3,4的回路各有多少条的回路各有多少条?(3) 长为长为4的通路共有多少条的通路共有多少条?其中有多少条回路其中有多少条回路?(4) 长度小于等于长度小于等于4的回路共有多少条的回路共有多少条?(5) 写出写出D的可达矩阵的可达矩阵, 并问并问D是强连通的吗是强连通的吗?解解v1v2v3v4A=1 2 1 00 0 1 00 0 0 10 0 1 027实例实例(续续)v1到到v4长为长为3的通路有的通路有 条条,A2=1 2 3 10 0 0 10 0 1 00 0 0 1A3=1 2 4 30 0 1 00 0 0 10 0 1 0A4=1 2 6 40 0 0 10 0 1 00 0 0 13v4到到v1长为长为3的通路有的通路有 条条0v1到自身长为到自身长为1,2,3,4的回路各有的回路各有 条条1长为长为4的通路共有的通路共有 条条, 其中有其中有 条回路条回路163长度小于等于长度小于等于4的回路共有的回路共有 条条8可达矩阵可达矩阵非强连通非强连通,单连通单连通 P=1 1 1 10 1 1 10 0 1 10 0 1 128。