邱婉玲耿素云离散数学ch省公共课一等奖全国赛课获奖课件.pptx
《邱婉玲耿素云离散数学ch省公共课一等奖全国赛课获奖课件.pptx》由会员分享,可在线阅读,更多相关《邱婉玲耿素云离散数学ch省公共课一等奖全国赛课获奖课件.pptx(51页珍藏版)》请在咨信网上搜索。
1、第五部分第五部分 图论图论本部分主要内容本部分主要内容l 图基本概念图基本概念l 欧拉图、哈密顿图欧拉图、哈密顿图l 树树l 平面图平面图l 支配集、覆盖集、独立集、匹配与着色支配集、覆盖集、独立集、匹配与着色1第1页第十四章第十四章 图基本概念图基本概念主要内容主要内容图图通路与回路通路与回路图连通性图连通性图矩阵表示图矩阵表示图运算图运算预备知识预备知识多重集合多重集合元素能够重复出现集合元素能够重复出现集合无序集无序集A B=(x,y)|x A y B2第2页14.1 图图定义定义14.1 无向图无向图G=,其中其中(1)V 为顶点集,元素称为为顶点集,元素称为顶点顶点(2)E为为V V
2、 多重集,其元素称为无向边,简称多重集,其元素称为无向边,简称边边实例实例 设设 V=v1,v2,v5,E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)则则 G=为一无向图为一无向图3第3页有向图有向图定义定义14.2 有向图有向图D=,只需注意只需注意E是是V V 多重子集多重子集图图2表示是一个有向图,试写出它表示是一个有向图,试写出它V 和和 E 注意:图数学定义与图形表示,在同构(待叙)意义下注意:图数学定义与图形表示,在同构(待叙)意义下是一一对应是一一对应4第4页相关概念相关概念1.图图 可用可用G泛指图(无向或有向
3、)泛指图(无向或有向)V(G),E(G),V(D),E(D)n阶图阶图2.有限图有限图3.n 阶零图与平凡图阶零图与平凡图4.空图空图5.用用 ek 表示无向边或有向边表示无向边或有向边6.顶点与边关联关系顶点与边关联关系 关联、关联次数关联、关联次数 环环 孤立点孤立点7.顶点之间相邻与邻接关系顶点之间相邻与邻接关系5第5页8.邻域与关联集邻域与关联集 v V(G)(G为无向图为无向图)v 关联集关联集 v V(D)(D为有向图为有向图)9.标定图与非标定图标定图与非标定图10.基图基图相关概念相关概念6第6页多重图与简单图多重图与简单图定义定义14.3 (1)无向图中平行边及重数无向图中平
4、行边及重数(2)有向图中平行边及重数(注意方向性)有向图中平行边及重数(注意方向性)(3)多重图多重图(4)简单图简单图在定义在定义14.3中定义简单图是极其主要概念中定义简单图是极其主要概念 7第7页顶点度数顶点度数定义定义14.4 (1)设设G=为无向图为无向图,v V,d(v)v度数度数,简称度简称度 (2)设设D=为有向图为有向图,v V,d+(v)v出度出度 d(v)v入度入度 d(v)v度或度数度或度数 (3)(G),(G)(4)+(D),+(D),(D),(D),(D),(D)(5)奇顶点度与偶度顶点奇顶点度与偶度顶点8第8页定理定理14.1 设设G=为任意无向图,为任意无向图,
5、V=v1,v2,vn,|E|=m,则则证证 G中每条中每条边边(包含包含环环)都有两个端点,所以在都有两个端点,所以在计计算算G中各中各顶顶点点度数之和度数之和时时,每条,每条边边均提供均提供2度,度,m 条条边边共提供共提供 2m 度度.本定理证实类似于定理本定理证实类似于定理14.1握手定理握手定理定理定理14.2 设设D=为任意有向图,为任意有向图,V=v1,v2,vn,|E|=m,则则9第9页握手定理推论握手定理推论推论推论 任何图任何图(无向或有向无向或有向)中,奇度顶点个数是偶数中,奇度顶点个数是偶数.证证 设设G=为任意图,令为任意图,令 V1=v|v V d(v)为奇数为奇数
6、V2=v|v V d(v)为偶数为偶数 则则V1 V2=V,V1 V2=,由握手定理可知,由握手定理可知因为因为2m,均为偶数,所以均为偶数,所以 为偶数,但因为为偶数,但因为V1中中顶点度数为奇数,所以顶点度数为奇数,所以|V1|必为偶数必为偶数.10第10页例例1 无向图无向图G有有16条边,条边,3个个4度顶点,度顶点,4个个3度顶点,其余度顶点,其余顶点度数均小于顶点度数均小于3,问,问G阶数阶数n为几?为几?解解 本题关键是应用握手定理本题关键是应用握手定理.设除设除3度与度与4度顶点外,还有度顶点外,还有x个顶点个顶点v1,v2,vx,则则 d(vi)2,i=1,2,x,于是得不等
7、式于是得不等式 32 24+2x得得 x 4,阶数阶数 n 4+4+3=11.握手定理应用握手定理应用11第11页图度数列图度数列1.V=v1,v2,vn为无向图为无向图G顶点集,称顶点集,称d(v1),d(v2),d(vn)为为G度数列度数列 2.V=v1,v2,vn为有向图为有向图D顶点集,顶点集,D度数列度数列:d(v1),d(v2),d(vn)D出度列出度列:d+(v1),d+(v2),d+(vn)D入度列入度列:d(v1),d(v2),d(vn)3.非负整数列非负整数列d=(d1,d2,dn)是是可图化可图化,是,是可简单图化可简单图化.易知:易知:(2,4,6,8,10),(1,3
8、,3,3,4)是可图化,后者又是可是可图化,后者又是可简单图化,而简单图化,而(2,2,3,4,5),(3,3,3,4)都不是可简单图化都不是可简单图化,尤其是后者也不是可图化,尤其是后者也不是可图化12第12页图同构图同构定义定义14.5 设设G1=,G2=为两个无向图为两个无向图(两个有两个有向向图图),若存在双射函数,若存在双射函数f:V1V2,对于对于vi,vj V1,(vi,vj)E1 当且仅当当且仅当(f(vi),f(vj)E2 (E1 当且仅当当且仅当 E2)而且而且,(vi,vj)()与)与(f(vi),f(vj)()重)重数相数相同,则称同,则称G1与与G2是是同构同构,记作
9、,记作G1 G2.图之间同构关系含有自反性、对称性和传递性图之间同构关系含有自反性、对称性和传递性.能找到多条同构必要条件,但它们全不是充分条件:能找到多条同构必要条件,但它们全不是充分条件:边数相同,顶点数相同边数相同,顶点数相同;度数列相同度数列相同;对应顶点关联集及邻域元素个数相同,等等对应顶点关联集及邻域元素个数相同,等等 若破坏必要条件,则两图不一样构若破坏必要条件,则两图不一样构判断两个图同构是个难题判断两个图同构是个难题13第13页图同构实例图同构实例图中图中(1)与与(2)度数列相同,它们同构吗?为何?度数列相同,它们同构吗?为何?(1)(2)(3)(4)图中,图中,(1)与与
10、(2)不一样构(度数列不一样),不一样构(度数列不一样),(3)与与(4)也不一样构也不一样构.(1)(2)14第14页n 阶完全图与竞赛图阶完全图与竞赛图定义定义14.6(1)n(n 1)阶无向完全图阶无向完全图每个顶点与其余顶点均相邻每个顶点与其余顶点均相邻无向简单图,记作无向简单图,记作 Kn.简单性质:边数简单性质:边数(2)n(n 1)阶阶有向完全图有向完全图每对顶点之间都有两条方向相每对顶点之间都有两条方向相反有向边有向简单图反有向边有向简单图.简单性质:简单性质:(3)n(n 1)阶阶竞赛图竞赛图基图为基图为Kn有向简单图有向简单图.简单性质:边数简单性质:边数 15第15页n
11、阶阶 k 正则图正则图(1)为为K5,(2)为为3阶有向完全图,阶有向完全图,(3)为为4阶竞赛图阶竞赛图.(1)(2)(3)定义定义14.7 n 阶阶k正则图正则图=k 无向简单图无向简单图简单性质:边数(由握手定理得)简单性质:边数(由握手定理得)Kn是是 n 1正则图,正则图,彼得松图(见书上图彼得松图(见书上图14.3(1)所表示,记住它)所表示,记住它)16第16页子图子图定义定义14.8 G=,G=(1)GG G 为为G子图子图,G为为G 母图母图(2)若若GG且且V=V,则称,则称G 为为G生成子图生成子图(3)若若VV或或EE,称,称G 为为G真子图真子图(4)V(VV且且V)
12、导出子图导出子图,记作,记作GV(5)E(EE且且E)导出子图导出子图,记作,记作GE 17第17页例例2 画出画出K4全部非同构生成子图全部非同构生成子图实例实例18第18页补图补图定义定义14.9 设设G=为为n阶无向简单图,以阶无向简单图,以V为顶点集,以为顶点集,以全部使全部使G成为完全图成为完全图Kn添加边组成集合为边集图,称为添加边组成集合为边集图,称为G补补图图,记作,记作 .若若G ,则称则称G是是自补图自补图.相对于相对于K4,求上面图中全部图补图,并指出哪些是自补图求上面图中全部图补图,并指出哪些是自补图.问:互为自补图两个图边数有何关系?问:互为自补图两个图边数有何关系?
13、19第19页14.2 通路与回路通路与回路定义定义14.11 给定图给定图G=(无向或有向),(无向或有向),G中中顶点与顶点与边交替序列边交替序列 =v0e1v1e2elvl,vi 1,vi 是是 ei 端点端点.(1)通路与回路:通路与回路:为为通路通路;若;若 v0=vl,为为回路回路,l 为为回路长回路长 度度.(2)简单通路与回路:全部边各异,简单通路与回路:全部边各异,为为简单通路简单通路,又若,又若v0=vl,为为简单回路简单回路(3)初级通路初级通路(路径路径)与初级回路与初级回路(圈圈):中全部顶点各异,中全部顶点各异,则称则称 为为初级通路初级通路(路径路径),又若除,又若
14、除v0=vl,全部顶点各不相,全部顶点各不相同且全部边各异,则称同且全部边各异,则称 为为初级回路初级回路(圈圈)(4)复杂通路与回路:有边重复出现复杂通路与回路:有边重复出现20第20页几点说明几点说明表示法表示法 定义表示法定义表示法 只用边表示法只用边表示法 只用顶点表示法(在简单图中)只用顶点表示法(在简单图中)混合表示法混合表示法环环(长为(长为1圈)长度为圈)长度为1,两条平行边组成圈长度为,两条平行边组成圈长度为 2,无向简单图中,圈长,无向简单图中,圈长 3,有向简单图中圈长度,有向简单图中圈长度 2.不一样圈(以长度不一样圈(以长度 3为例)为例)定义意义下定义意义下 无向图
15、:图中长度为无向图:图中长度为l(l 3)圈,定义意义下为)圈,定义意义下为2l个个 有向图:图中长度为有向图:图中长度为l(l 3)圈,定义意义下为)圈,定义意义下为l个个 同构意义下:长度相同圈均为同构意义下:长度相同圈均为1个个试讨论试讨论l=3和和l=4情况情况21第21页通路与回路长度通路与回路长度定理定理14.5 在在n 阶图阶图G中,若从顶点中,若从顶点vi 到到vj(vi vj)存在通路,)存在通路,则从则从vi 到到 vj 存在长度小于或等于存在长度小于或等于n 1 通路通路.推论推论 在在 n 阶图阶图G中,若从顶点中,若从顶点vi 到到 vj(vi vj)存在通路,则)存
16、在通路,则从从vi 到到vj 存在长度小于或等于存在长度小于或等于n 1初级通路(路径)初级通路(路径).定理定理14.6 在一个在一个n 阶图阶图G中,若存在中,若存在 vi 到本身回路,则一到本身回路,则一定存在定存在vi 到本身长度小于或等于到本身长度小于或等于 n 回路回路.推论推论 在一个在一个n 阶图阶图G中,若存在中,若存在 vi 到本身简单回路,则一到本身简单回路,则一定存在长度小于或等于定存在长度小于或等于n 初级回路初级回路.22第22页14.3 图连通性图连通性无向图连通性无向图连通性(1)顶点之间连通关系:顶点之间连通关系:G=为无向图为无向图 若若 vi 与与 vj
17、之间有通路,则之间有通路,则 vi vj 是是V上等价关系上等价关系 R=|u,v V且且u v(2)G连通性与连通分支连通性与连通分支 若若 u,v V,u v,则称,则称G连通连通 V/R=V1,V2,Vk,称,称GV1,GV2,GVk为为连通连通分分 支支,其个数,其个数 p(G)=k (k 1);k=1,G连通连通23第23页短程线与距离短程线与距离(3)短程线与距离短程线与距离 u与与v之间之间短程线短程线:u v,u与与v之间长度最短通路之间长度最短通路 u与与v之间之间距离距离:d(u,v)短程线长度短程线长度 d(u,v)性质:性质:d(u,v)0,u v时时d(u,v)=d(
18、u,v)=d(v,u)d(u,v)+d(v,w)d(u,w)24第24页无向图连通度无向图连通度1.删除顶点及删除边删除顶点及删除边 G v 从从G中将中将v及关联边去掉及关联边去掉 G V 从从G中删除中删除V 中全部顶点中全部顶点 G e 将将e从从G中去掉中去掉 G E 删除删除E 中全部边中全部边 2.点割集与边割集点割集与边割集 点割集与割点点割集与割点定义定义14.16 G=,VV V 为为点割集点割集p(G V)p(G)且有极小性且有极小性 v为为割点割点v为点割集为点割集定义定义14.17 G=,EE E 是是边割集边割集p(G E)p(G)且有极小性且有极小性 e是是割边割边
19、(桥)(桥)e为边割集为边割集25第25页点割集与割点点割集与割点例例3 v1,v4,v6是点是点割集,割集,v6是割点是割点.v2,v5是点割集吗?是点割集吗?e1,e2,e1,e3,e5,e6,e8等是边割集,等是边割集,e8是是桥,桥,e7,e9,e5,e6 是边是边割割集吗?集吗?几点说明:几点说明:Kn中无点割集,中无点割集,Nn中既无点割集,也无边割集,其中中既无点割集,也无边割集,其中Nn为为 n 阶零图阶零图.若若G 连通,连通,E 为边割集,则为边割集,则 p(G E)=2,V 为点割集,为点割集,则则 p(G V)2 26第26页点连通度与边连通度点连通度与边连通度定义定义
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 邱婉玲耿素云 离散数学 ch 公共课 一等奖 全国 获奖 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。