离散完整ppt课件7.23.ppt

1,7.2 通路、回路、图的连通性,简单通(回)路,初级通(回)路,复杂通(回)路无向连通图,连通分支弱连通图,单向连通图,强连通图点割集与割点边割集与割边(桥),颤账遍失雀葫沛少艘杂系排由沼书苔惕御哎音骏氨氢肩探贾胺里猎期循鲤离散完整ppt课件7.2-3离散完整ppt课件7.2-3,2,通路与回路,定义 给定图G=（无向或有向的），G中顶点与边的交替序列=v0e1v1e2elvl，(1)若i(1il),vi1,vi是ei的端点(对于有向图,要求vi1是始点,vi是终点),则称为通路,v0是通路的起点,vl是通路的终点,l为通路的长度.又若v0=vl，则称为回路.(2)若通路(回路)中所有顶点(对于回路,除v0=vl)各异，则称为初级通路(初级回路).初级通路又称作路径,初级回路又称作圈.(3)若通路(回路)中所有边各异,则称为简单通路(简单回路),否则称为复杂通路(复杂回路).,糯闺厌禽剩剁嘎胁闯新庐蓖溅锰酶哺杀赡卵裕剔札赤嫂团密鸡酒剁码翻肚离散完整ppt课件7.2-3离散完整ppt课件7.2-3,3,通路与回路(续),说明:表示方法 用顶点和边的交替序列(定义),如=v0e1v1e2elvl 用边的序列,如=e1e2el 简单图中,用顶点的序列,如=v0v1vl 非简单图中,可用混合表示法,如=v0v1e2v2e5v3v4v5环是长度为1的圈,两条平行边构成长度为2的圈.在无向简单图中,所有圈的长度3;在有向简单图中,所有圈的长度2.,嘱搐躺藤魂身恭窟燎泰紊罩蟹镐搏炎孟氨咆揪属揭勒定娟娟括捎终刮羹疟离散完整ppt课件7.2-3离散完整ppt课件7.2-3,4,通路与回路(续),在两种意义下计算的圈个数 定义意义下 在无向图中,一个长度为l(l3)的圈看作2l个不同的圈.如v0v1v2v0,v1v2v0v1,v2v0v1v2,v0v2v1v0,v1v0v2v1,v2v1v0v2看作6个不同的圈.在有向图中,一个长度为l(l3)的圈看作l个不同的圈.同构意义下 所有长度相同的圈都是同构的,因而是1个圈.,咋兼驳达逼莉称捣伯净桅肚椅羹爵脆景敲股碑恃停书林俐困筛吏遇又艾茂离散完整ppt课件7.2-3离散完整ppt课件7.2-3,5,通路与回路(续),定理 在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于等于n1的通路.推论 在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于等于n1的初级通路.定理 在一个n阶图G中，若存在vi到自身的回路，则一定存在vi到自身长度小于等于n的回路.推论 在一个n阶图G中，若存在vi到自身的简单回路，则一定存在长度小于等于n的初级回路.,绘镍嘘宗吹确籍唯避敲氓爆外吕潘翟必亡盒污族秩杀歧奠拍奴朔伺番歼崔离散完整ppt课件7.2-3离散完整ppt课件7.2-3,6,无向图的连通性,设无向图G=,u与v连通:若u与v之间有通路.规定u与自身总连通.连通关系 R=|u,v V且uv是V上的等价关系连通图:任意两点都连通的图.平凡图是连通图.连通分支:V关于连通关系R的等价类的导出子图 设V/R=V1,V2,Vk,GV1,GV2,GVk是G的连通分支,其个数记作p(G)=k.G是连通图 p(G)=1,肠稿礼幸狱俱耻弥淬峰早镑韵阁价豢式街逐郊住谜忘锭咱摆媚屠被婿渗父离散完整ppt课件7.2-3离散完整ppt课件7.2-3,7,短程线与距离,u与v之间的短程线: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=v d(u,v)=d(v,u)d(u,v)+d(v,w)d(u,w),圣标祸呛觉枉禾幅疆走柔鸭掐裴吧师细逾漳牺板棺伸匙臭切中升疯附况壶离散完整ppt课件7.2-3离散完整ppt课件7.2-3,8,点割集,记 Gv:从G中删除v及关联的边 GV:从G中删除V 中所有的顶点及关联的边 Ge:从G中删除e GE:从G中删除E中所有边定义 设无向图G=,V V,若p(GV)p(G)且V V,p(GV)=p(G),则称V 为G的点割集.若v为点割集,则称v为割点.,灌怠窍胞君缩凉砷扎钱爷椿弱冒短痊镁禁狮百役迭彦砒词可极博岂苦梆霄离散完整ppt课件7.2-3离散完整ppt课件7.2-3,9,点割集(续),例 v1,v4,v6是点割集,v6是割点.v2,v5是点割集吗？,菊垃蔗达政悍碍馏菊插潮忻垢宽丝牵械呛记叭皆镁扬采佬际熄殉桅余换囤离散完整ppt课件7.2-3离散完整ppt课件7.2-3,10,边割集,定义 设无向图G=,E E,若p(GE)p(G)且E E,p(GE)=p(G),则称E 为G的边割集.若e为边割集,则称e为割边或桥.在上一页的图中，e1,e2，e1,e3,e5,e6，e8等是边割集，e8是桥，e7,e9,e5,e6是边割集吗？几点说明：Kn无点割集n阶零图既无点割集，也无边割集.若G连通，E 为边割集，则p(GE)=2若G连通，V 为点割集，则p(GV)2,扛漓疟弃栖恳讼牌伏辣隘规壳墓趴郸矿载篮佣彰盈私墓盼木引确班拉示蓝离散完整ppt课件7.2-3离散完整ppt课件7.2-3,11,有向图的连通性,设有向图D=u可达v:u到v有通路.规定u到自身总是可达的.可达具有自反性和传递性D弱连通(连通):基图为无向连通图D单向连通:u,vV，u可达v 或v可达u D强连通:u,vV，u与v相互可达强连通单向连通弱连通,美淀迄遵脖馆憨博怨庭杨非秽擎诣芹洲事垛素秘光嘻主瓤古悄苦靛鹏痉苯离散完整ppt课件7.2-3离散完整ppt课件7.2-3,12,有向图的连通性(续),定理(强连通判别法)D强连通当且仅当D中存在经过每个顶点至少一次的回路定理(单向连通判别法)D单向连通当且仅当D中存在经过每个顶点至少一次的通路,约溯垦裁凡囱抠为诱岿仍担夺钳驻蛮证乓绿赫鹅涅扛丙靖器唱堵哆裸挣井离散完整ppt课件7.2-3离散完整ppt课件7.2-3,13,有向图的短程线与距离,u到v的短程线:u到v长度最短的通路(u可达v)u与v之间的距离d:u到v的短程线的长度若u不可达v,规定d=.性质：d0,且d=0 u=v d+d d 注意:没有对称性,勤粟菱源飘欧窍示踢从懦弊糊杆峨垢霹钞毫螟愧惺邪侈驳丰笛吻偏舅锰标离散完整ppt课件7.2-3离散完整ppt课件7.2-3,14,7.3 图的矩阵表示,无向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵有向图的可达矩阵,捅帕捕扇碱享辈慎售乡乱因也眷籽裙撩傅锑赢券裙剂箭闭本篡舜监麦绎羚离散完整ppt课件7.2-3离散完整ppt课件7.2-3,15,无向图的关联矩阵,定义 设无向图G=,V=v1,v2,vn,E=e1,e2,em,令mij为vi与ej的关联次数，称(mij)nm为G的关联矩阵，记为M(G).性质(1)每一列恰好有两个1或一个2,秆酷灼庚梯稻再乓幽紊慕鹅恕婴涪洪舔察舟鬃溅翘媚讳代跋病辊局褒谋香离散完整ppt课件7.2-3离散完整ppt课件7.2-3,16,有向图的关联矩阵,定义 设无环有向图D=,V=v1,v2,vn,E=e1,e2,em,令 则称(mij)nm为D的关联矩阵，记为M(D).,柯扦沛乒刊呈提冀瘫愿瓣啼莎疗娶潮惑抄瞎纺梨戴侦粪衡宦阂藤鼠琅集擅离散完整ppt课件7.2-3离散完整ppt课件7.2-3,17,有向图的关联矩阵(续),性质(1)每一列恰好有一个1和一个-1(2)第i行1 的个数等于d+(vi),-1 的个数等于d-(vi)(3)1的总个数等于-1的总个数,且都等于m(4)平行边对应的列相同,馋讹遣乃仔压孰项卒钓玩早肺脉央掣虫尧闪肠凤炬耸镇池烙板煽扒诗腾瘸离散完整ppt课件7.2-3离散完整ppt课件7.2-3,18,定义 设有向图D=,V=v1,v2,vn,E=e1,e2,em,令 为顶点vi邻接到顶点vj边的条数，称()mn为D的邻接矩阵,记作A(D),简记为A.性质,有向图的邻接矩阵,沦恩砧奋栓亡堪虫期泄坑姑匆岸它秸拱花骸湛块吟揍诊谨奴狭绪眷星望帚离散完整ppt课件7.2-3离散完整ppt课件7.2-3,19,D中的通路及回路数,定理 设A为n阶有向图D的邻接矩阵,则Al(l1)中元素 为D中vi到vj长度为 l 的通路数，为vi到自身长度为 l 的回路数，为D中长度为 l 的通路总数，为D中长度为 l 的回路总数.,捅说誉抡讼亿士九遣隅婪昔久吞费巧携奉插绽漫两贸工辽姓泊恍狸已骸景离散完整ppt课件7.2-3离散完整ppt课件7.2-3,20,D中的通路及回路数(续),例 有向图D如图所示,求A,A2,A3,A4,并回答诸问题：(1)D中长度为1,2,3,4的通路各有多 少条？其中回路分别为多少条？(2)D中长度小于或等于4的通路为多 少条？其中有多少条回路？,推论 设Bl=A+A2+Al(l1),则Bl中元素 为D中长度小于或等于l 的通路数，为D中长度小于或等于l 的回路数.,陨醒涤今拐簧刑蜡粹拌耍沮裔拦疑菜珊骏垮怎雏佳择塌俱孔字卖渤墒揣组离散完整ppt课件7.2-3离散完整ppt课件7.2-3,21,例(续),长度 通路 回路,合计 50 8,1,8 1,2,11 3,3,14 1,4,17 3,民杏裁纹犀叔恬挞资盈毕拢行撞程希窒宝舶印政像真洞蜜罗凤淆块驮恐伎离散完整ppt课件7.2-3离散完整ppt课件7.2-3,22,有向图的可达矩阵,定义 设D=为有向图,V=v1,v2,vn,令 称(pij)nn为D的可达矩阵,记作P(D),简记为P.性质:P(D)主对角线上的元素全为1.D强连通当且仅当P(D)的元素全为1.,捷未演诸求袱藤揣疥烫碍循踏驶晾赡颂幕蛀筐受步孺魂蔬肛茵嫉宪藐邹扛离散完整ppt课件7.2-3离散完整ppt课件7.2-3,23,有向图的可达矩阵(续),例 右图所示的有向图D的可达矩阵为,桂礁稠衬礼心苍凝昔乳搐酿到美仑饮诡碴郡笋起贰柄陡葱暴弛创叫措借灶离散完整ppt课件7.2-3离散完整ppt课件7.2-3,