离散数学-6.2-3图的连通性.ppt
1,6.2 图的连通性,6.2.1 通路与回路初级通路(回路)与简单通路(回路)6.2.2 无向图的连通性与连通度连通图、连通分支短程线与距离点割集、割点、边割集、割边(桥)点连通度与边连通度,2,6.2 图的连通性(续),6.2.3 有向图的连通性及其分类可达性弱连通、单向连通、强连通短程线与距离,3,通路与回路,定义6.13 给定图G=(无向或有向的),G中顶点与边的交替序列=v0e1v1e2elvl.若i(1il),ei=(vi1,vi)(对于有向图,ei=),则称为v0到vl的通路,v0和vl分别为通路的起点和终点,l为通路的长度.又若v0=vl,则称为回路.若通路(回路)中所有顶点(对于回路,除v0=vl)各异,则称为初级通路或路径(初级回路或圈).长度为奇数的圈称作奇圈,长度为偶数的圈称作偶圈若通路(回路)中所有边各异,则称为简单通路(简单回路),否则称为复杂通路(复杂回路),4,说明,(1)表示方法 按定义用顶点和边的交替序列,=v0e1v1e2elvl 用边序列,=e1e2el 简单图中,用顶点序列,=v0v1vl(2)在无向图中,长度为1的圈由环构成.长度为2的圈由两条平行边构成.在无向简单图中,所有圈的长度3.在有向图中,长度为1的圈由环构成.在有向简单图中,所有圈的长度2.,5,说明(续),(3)初级通路(回路)是简单通路(回路),但反之不真,初级通路,非初级的简单通路,初级回路,非初级的简单回路,6,通路与回路(续),定理6.3 在n阶图中,若从顶点u到v(uv)存在通路,则从u到v存在长度小于等于n1的初级通路.证 若通路中没有相同的顶点(即初级通路),长度必 n1.若有相同的顶点,删去这两个顶点之间的这一段,仍是u到v的通路.重复进行,直到没有相同的顶点为止.定理6.4 在n阶图中,若存在v到自身的简单回路,则一定存在v到自身长度小于等于n的初级回路.,7,无向图的连通性与连通分支,设无向图G=,u,vVu与v连通:若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与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)=,9,点割集与边割集,设无向图G=,vV,eE,VV,EE.记Gv:从G中删除v及关联的边GV:从G中删除V中所有的顶点及关联的边Ge:从G中删除eGE:从G中删除E中所有边定义6.15 设无向图G=,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为割边或桥.,10,实例,说明：Kn无点割集n阶零图既无点割集，也无边割集.若G连通，E为边割集，则p(GE)=2若G连通，V为点割集，则p(GV)2,e,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成为平凡图 称为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,有(G)(G)(G),13,有向图的连通性及其分类,设有向图D=,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中存在经过所有顶点的通路,14,实例,15,有向图中的短程线与距离,u到v的短程线:u到v长度最短的通路(设u可达v)距离d:u到v的短程线的长度若u不可达v,规定d=.性质：d0,且d=0 u=v d+d d 注意:没有对称性,16,6.3 图的矩阵表示,6.3.1 无向图的关联矩阵6.3.2 有向无环图的关联矩阵6.3.3 有向图的邻接矩阵有向图中的通路数与回路数6.3.4 有向图的可达矩阵,17,无向图的关联矩阵,设无向图G=,V=v1,v2,vn,E=e1,e2,em.令mij为vi与ej的关联次数,称(mij)nm为G的关联矩阵,记为M(G).mij的可能取值为:0,1,2,例如,18,关联矩阵的性质,(6)ej是环 第j列的一个元素为2,其余为0,(5)vi是孤立点 第i行全为0,19,无环有向图的关联矩阵,20,实例,21,有向图的邻接矩阵,设有向图D=,V=v1,v2,vn,E=e1,e2,em,令 为顶点vi邻接到顶点vj边的条数，称()mn为D的邻接矩阵,记作A(D),简记作A.,22,实例,23,有向图中的通路数与回路数,定理6.6 设A为n阶有向图D的邻接矩阵,则Al(l1)中元素 等于D中vi到vj长度为 l 的通路(含回路)数,等于vi到自身长度为l 的回路数,等于D中长度为 l 的通路(含回路)总数,等于D中长度为 l 的回路总数.,24,有向图中的通路数与回路数(续),推论 设Bl=A+A2+Al(l1),则Bl中元素 等于D中vi到vj长度小于等于 l 的通路(含回路)数,等于D中vi到vi长度小于等于 l 的回路数,等于D中长度小于等于l 的通路(含回路)数,为D中长度小于等于l 的回路数.,25,实例(续),说明:在这里,通路和回路数是定义意义下的,v1到v2长为3的通路有1条v1到v3长为3的通路有1条v1到自身长为3的回路有2条D中长为3的通路共有15条,其中回路3条,26,有向图的可达矩阵,性质:P(D)主对角线上的元素全为1.D强连通当且仅当P(D)的元素全为1.,设有向图D=,V=v1,v2,vn,令 称(pij)nn为D的可达矩阵,记作P(D),简记为P.,27,实例,例1(1)v1到v4,v4到v1长为3的通路各有多少条?(2)v1到自身长为1,2,3,4的回路各有多少条?(3)长为4的通路共有多少条?其中有多少条回路?(4)长度小于等于4的回路共有多少条?(5)写出D的可达矩阵,并问D是强连通的吗?解,28,实例(续),v1到v4长为3的通路有 条,3,v4到v1长为3的通路有 条,0,v1到自身长为1,2,3,4的回路各有 条,1,长为4的通路共有 条,其中有 条回路,16,3,长度小于等于4的回路共有 条,8,可达矩阵,非强连通,单连通,
