离散数学-62-3图的连通性课件

6.2图的连通性6.2.1通路与回路初级通路(回路)与简单通路(回路)6.2.2无向图的连通性与连通度连通图、连通分支短程线与距离点割集、割点、边割集、割边(桥)点连通度与边连通度16.2图的连通性6.2.1通路与回路16.2图的连通性(续)6.2.3有向图的连通性及其分类可达性弱连通、单向连通、强连通短程线与距离26.2图的连通性(续)6.2.3有向图的连通性及其分类2通路与回路定义6.13给定图G=<V,E>(无向或有向的),G中顶点与边的交替序列=v0e1v1e2…elvl.若i(1il),ei=(vi1,vi)(对于有向图,ei=<vi1,vi>),则称为v0到vl的通路,v0和vl分别为通路的起点和终点,l为通路的长度.又若v0=vl,则称为回路.若通路(回路)中所有顶点(对于回路,除v0=vl)各异,则称为初级通路或路径(初级回路或圈).长度为奇数的圈称作奇圈,长度为偶数的圈称作偶圈若通路(回路)中所有边各异,则称为简单通路(简单回路),否则称为复杂通路(复杂回路)3通路与回路定义6.13给定图G=<V,E>(无向或有向的)说明(1)表示方法①按定义用顶点和边的交替序列,=v0e1v1e2…elvl②用边序列,=e1e2…el③简单图中,用顶点序列,=v0v1…vl(2)在无向图中,长度为1的圈由环构成.长度为2的圈由两条平行边构成.在无向简单图中,所有圈的长度3.在有向图中,长度为1的圈由环构成.在有向简单图中,所有圈的长度2.4说明(1)表示方法4说明(续)(3)初级通路(回路)是简单通路(回路),但反之不真初级通路非初级的简单通路初级回路非初级的简单回路5说明(续)(3)初级通路(回路)是简单通路(回路),但反通路与回路(续)定理6.3在n阶图中,若从顶点u到v(uv)存在通路,则从u到v存在长度小于等于n1的初级通路.证若通路中没有相同的顶点(即初级通路),长度必n1.若有相同的顶点,删去这两个顶点之间的这一段,仍是u到v的通路.重复进行,直到没有相同的顶点为止.定理6.4

在n阶图中,若存在v到自身的简单回路,则一定存在v到自身长度小于等于n的初级回路.6通路与回路(续)定理6.3在n阶图中,若从顶点u到v(无向图的连通性与连通分支设无向图G=<V,E>,u,vVu与v连通:若u与v之间有通路.规定u与自身总是连通的.连通图:任意两点都连通的图.平凡图是连通图连通关系R={<u,v>|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无向图的连通性与连通分支设无向图G=<V,E>,u,vV短程线与距离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)=abcdefghi8短程线与距离u与v之间的短程线:u与v之间长度最短的通路(设点割集与边割集设无向图G=<V,E>,vV,eE,VV,EE.记Gv:从G中删除v及关联的边GV:从G中删除V中所有的顶点及关联的边Ge:从G中删除eGE:从G中删除E中所有边定义6.15设无向图G=<V,E>,VV,若p(GV)>p(G)且VV,p(GV)=p(G),则称V为G的点割集.若{v}为点割集,则称v为割点.设EE,若p(GE)>p(G)且EE,p(GE)=p(G),则称E为G的边割集.若{e}为边割集,则称e为割边或桥.9点割集与边割集设无向图G=<V,E>,vV,eE,实例说明：Kn无点割集n阶零图既无点割集，也无边割集.若G连通，E为边割集，则p(GE)=2若G连通，V为点割集，则p(GV)2abcdefge1e2e3e4e5e6e7e8e9e,f点割集:{e},{f},割点:{c,d}

桥:e8,e9边割集:{e8},{e9},{e1,e2},{e1,e3,e6},{e1,e3,e4,e7}10实例说明：Kn无点割集abcdefge1e2e3e4e5e点连通度与边连通度定义6.16设无向连通图G=<V,E>,(G)=min{|V||V是G的点割集或使G-V成为平凡图}

称为G的点连通度

(G)=min{|E||E是G的边割集}称为G的边连通度例如3(G)=3(G)=11点连通度与边连通度定义6.16设无向连通图G=<V,E>,点连通度与边连通度(续)说明:(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,有

(G)(G)(G)12点连通度与边连通度(续)说明:12有向图的连通性及其分类设有向图D=<V,E>,u,vV,u可达v:u到v有通路.规定u到自身总是可达的.u与v相互可达:u可达v且v可达uD弱连通(连通):略去各边的方向所得无向图为连通图D单向连通:u,vV，u可达v

或v可达u

D强连通:u,vV，u与v相互可达D是强连通的当且仅当D中存在经过所有顶点的回路D是单向连通的当且仅当D中存在经过所有顶点的通路13有向图的连通性及其分类设有向图D=<V,E>,u,vV,实例

强连通单连通弱连通14实例

强连通单连通弱连通14有向图中的短程线与距离u到v的短程线:u到v长度最短的通路(设u可达v)距离d<u,v>:u到v的短程线的长度若u不可达v,规定d<u,v>=∞.性质：

d<u,v>0,且d<u,v>=0

u=vd<u,v>+d<v,w>d<u,w>

注意:没有对称性15有向图中的短程线与距离u到v的短程线:u到v长度最短的通路6.3图的矩阵表示6.3.1无向图的关联矩阵6.3.2有向无环图的关联矩阵6.3.3有向图的邻接矩阵有向图中的通路数与回路数6.3.4有向图的可达矩阵166.3图的矩阵表示6.3.1无向图的关联矩阵16无向图的关联矩阵设无向图G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}.

令mij为vi与ej的关联次数,称(mij)nm为G的关联矩阵,记为M(G).mij的可能取值为:0,1,2例如e1e2e3e4e5e6v5v1v2v3v4M(G)=21100001011100001100000000110017无向图的关联矩阵设无向图G=<V,E>,V={v1,v2关联矩阵的性质(6)ej是环第j列的一个元素为2,其余为0(5)vi是孤立点第i行全为018关联矩阵的性质(6)ej是环第j列的一个元素为2,无环有向图的关联矩阵则称(mij)nm为D的关联矩阵,记为M(D).设无环有向图D=<V,E>,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无环有向图的关联矩阵则称(mij)nm为D的关联矩阵,记实例v1v2v3v4e2e1e3e4e5e6e7M(D)=-11000–110-11000000-1-1-11-1100110020实例v1v2v3v4e2e1e3e4e5e6e7M(D)=-有向图的邻接矩阵设有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令为顶点vi邻接到顶点vj边的条数，称()mn为D的邻接矩阵,记作A(D),简记作A.21有向图的邻接矩阵设有向图D=<V,E>,V={v1,v2实例A=1100001010001020v1v2v3v422实例A=1100v1v2v3v422有向图中的通路数与回路数定理6.6设A为n阶有向图D的邻接矩阵,则Al(l1)中元素等于D中vi到vj长度为l的通路(含回路)数,等于vi到自身长度为l的回路数,等于D中长度为l的通路(含回路)总数,等于D中长度为l的回路总数.23有向图中的通路数与回路数定理6.6设A为n阶有向图D的邻接有向图中的通路数与回路数(续)推论设Bl=A+A2+…+Al(l1),则Bl中元素等于D中vi到vj长度小于等于l的通路(含回路)数,等于D中vi到vi长度小于等于l的回路数,等于D中长度小于等于l的通路(含回路)数,为D中长度小于等于l的回路数.24有向图中的通路数与回路数(续)推论设Bl=A+A2+…+实例(续)

说明:在这里,通路和回路数是定义意义下的A=1100001010001020A2=1110100011003100A3=2110110011003310A4=3210110021104310v1到v2长为3的通路有1条v1到v3长为3的通路有1条v1到自身长为3的回路有2条D中长为3的通路共有15条,其中回路3条v1v2v3v425实例(续)说明:在这里,通路和回路数是定义意义下的A有向图的可达矩阵性质:P(D)主对角线上的元素全为1.D强连通当且仅当P(D)的元素全为1.设有向图D=<V,E>,V={v1,v2,…,vn},令

称(pij)nn为D的可达矩阵,记作P(D),简记为P.26有向图的可达矩阵性质:设有向图D=<V,E>,V={v1,实例例1(1)v1到v4,v4到v1长为3的通路各有多少条?(2)v1到自身长为1,2,3,4的回路各有多少条?(3)长为4的通路共有多少条?其中有多少条回路?(4)长度小于等于4的回路共有多少条?(5)写出D的可达矩阵,并问D是强连通的吗?解v1v2v3v4A=121000100001001027实例例1(1)v1到v4,v4到v1长为3的通路各有多少实例(续)v1到v4长为3的通路有条,A2=1231000100100001A3=1243001000010010A4=12640001001000013v4到v1长为3的通路有条0v1到自身长为1,2,3,4的回路各有条1长为4的通路共有条,其中有条回路163长度小于等于4的回路共有条8可达矩阵非强连通,单连通P=111101110011001128实例(续)v1到v4长为3的通路有条,A2=16.2图的连通性6.2.1通路与回路初级通路(回路)与简单通路(回路)6.2.2无向图的连通性与连通度连通图、连通分支短程线与距离点割集、割点、边割集、割边(桥)点连通度与边连通度296.2图的连通性6.2.1通路与回路16.2图的连通性(续)6.2.3有向图的连通性及其分类可达性弱连通、单向连通、强连通短程线与距离306.2图的连通性(续)6.2.3有向图的连通性及其分类2通路与回路定义6.13给定图G=<V,E>(无向或有向的),G中顶点与边的交替序列=v0e1v1e2…elvl.若i(1il),ei=(vi1,vi)(对于有向图,ei=<vi1,vi>),则称为v0到vl的通路,v0和vl分别为通路的起点和终点,l为通路的长度.又若v0=vl,则称为回路.若通路(回路)中所有顶点(对于回路,除v0=vl)各异,则称为初级通路或路径(初级回路或圈).长度为奇数的圈称作奇圈,长度为偶数的圈称作偶圈若通路(回路)中所有边各异,则称为简单通路(简单回路),否则称为复杂通路(复杂回路)31通路与回路定义6.13给定图G=<V,E>(无向或有向的)说明(1)表示方法①按定义用顶点和边的交替序列,=v0e1v1e2…elvl②用边序列,=e1e2…el③简单图中,用顶点序列,=v0v1…vl(2)在无向图中,长度为1的圈由环构成.长度为2的圈由两条平行边构成.在无向简单图中,所有圈的长度3.在有向图中,长度为1的圈由环构成.在有向简单图中,所有圈的长度2.32说明(1)表示方法4说明(续)(3)初级通路(回路)是简单通路(回路),但反之不真初级通路非初级的简单通路初级回路非初级的简单回路33说明(续)(3)初级通路(回路)是简单通路(回路),但反通路与回路(续)定理6.3在n阶图中,若从顶点u到v(uv)存在通路,则从u到v存在长度小于等于n1的初级通路.证若通路中没有相同的顶点(即初级通路),长度必n1.若有相同的顶点,删去这两个顶点之间的这一段,仍是u到v的通路.重复进行,直到没有相同的顶点为止.定理6.4

在n阶图中,若存在v到自身的简单回路,则一定存在v到自身长度小于等于n的初级回路.34通路与回路(续)定理6.3在n阶图中,若从顶点u到v(无向图的连通性与连通分支设无向图G=<V,E>,u,vVu与v连通:若u与v之间有通路.规定u与自身总是连通的.连通图:任意两点都连通的图.平凡图是连通图连通关系R={<u,v>|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)=135无向图的连通性与连通分支设无向图G=<V,E>,u,vV短程线与距离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)=abcdefghi36短程线与距离u与v之间的短程线:u与v之间长度最短的通路(设点割集与边割集设无向图G=<V,E>,vV,eE,VV,EE.记Gv:从G中删除v及关联的边GV:从G中删除V中所有的顶点及关联的边Ge:从G中删除eGE:从G中删除E中所有边定义6.15设无向图G=<V,E>,VV,若p(GV)>p(G)且VV,p(GV)=p(G),则称V为G的点割集.若{v}为点割集,则称v为割点.设EE,若p(GE)>p(G)且EE,p(GE)=p(G),则称E为G的边割集.若{e}为边割集,则称e为割边或桥.37点割集与边割集设无向图G=<V,E>,vV,eE,实例说明：Kn无点割集n阶零图既无点割集，也无边割集.若G连通，E为边割集，则p(GE)=2若G连通，V为点割集，则p(GV)2abcdefge1e2e3e4e5e6e7e8e9e,f点割集:{e},{f},割点:{c,d}

桥:e8,e9边割集:{e8},{e9},{e1,e2},{e1,e3,e6},{e1,e3,e4,e7}38实例说明：Kn无点割集abcdefge1e2e3e4e5e点连通度与边连通度定义6.16设无向连通图G=<V,E>,(G)=min{|V||V是G的点割集或使G-V成为平凡图}

称为G的点连通度

(G)=min{|E||E是G的边割集}称为G的边连通度例如3(G)=3(G)=39点连通度与边连通度定义6.16设无向连通图G=<V,E>,点连通度与边连通度(续)说明:(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,有

(G)(G)(G)40点连通度与边连通度(续)说明:12有向图的连通性及其分类设有向图D=<V,E>,u,vV,u可达v:u到v有通路.规定u到自身总是可达的.u与v相互可达:u可达v且v可达uD弱连通(连通):略去各边的方向所得无向图为连通图D单向连通:u,vV，u可达v

或v可达u

D强连通:u,vV，u与v相互可达D是强连通的当且仅当D中存在经过所有顶点的回路D是单向连通的当且仅当D中存在经过所有顶点的通路41有向图的连通性及其分类设有向图D=<V,E>,u,vV,实例

强连通单连通弱连通42实例

强连通单连通弱连通14有向图中的短程线与距离u到v的短程线:u到v长度最短的通路(设u可达v)距离d<u,v>:u到v的短程线的长度若u不可达v,规定d<u,v>=∞.性质：

d<u,v>0,且d<u,v>=0

u=vd<u,v>+d<v,w>d<u,w>

注意:没有对称性43有向图中的短程线与距离u到v的短程线:u到v长度最短的通路6.3图的矩阵表示6.3.1无向图的关联矩阵6.3.2有向无环图的关联矩阵6.3.3有向图的邻接矩阵有向图中的通路数与回路数6.3.4有向图的可达矩阵446.3图的矩阵表示6.3.1无向图的关联矩阵16无向图的关联矩阵设无向图G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}.

令mij为vi与ej的关联次数,称(mij)nm为G的关联矩阵,记为M(G).mij的可能取值为:0,1,2例如e1e2e3e4e5e6v5v1v2v3v4M(G)=21100001011100001100000000110045无向图的关联矩阵设无向图G=<V,E>,V={v1,v2关联矩阵的性质(6)ej是环第j列的一个元素为2,其余为0(5)vi是孤立点第i行全为046关联矩阵的性质(6)ej是环第j列的一个元素为2,无环有向图的关联矩阵则称(mij)nm为D的关联矩阵,记为M(D).设无环有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}.令(3)ej与ek是平行边

第j列与第k列相同(2)第i行1的个数等于d+(v),第i行-1的个数等于d-(v)性质:(1)每列恰好有一个1和一个-147无环有向图的关联矩阵则称(mij)nm为D的关联矩阵,记实例v1v2v3v4e2e1e3e4e5e6e7M(D)=-11000–110-11000000-1-1-11-1100110048实例v1v2v3v4e2e1e3e4e5e6e7M(D)=-有向图的邻接矩阵设有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令为顶点vi邻接到顶点vj边的条数，称()mn为D的邻接矩阵,记作A(D),简记作A.49有向图的邻接矩阵设有向图D=<V,E>,V={v1,v2实例A=1100001010001020v1v2v3v450实例A=1100v1v2v3v422有向图中的通路数与回路数定理6.6设A为n阶有向图D的邻接矩阵,则Al(l1)中元素等于D中vi到vj长度为l的通路(含回路)数,等于vi到自身长度为l的回路数,等于D中长度为l的通路(含回路)总数,等于D中长度为l的回路总数.51有向图中的通路数与回路数定理6.6设A为n阶有向图D的邻接有向图中的通路数与回路数(续)推论设Bl=A+A2+…+Al(l1),则Bl中元素等于