![离散数学专题知识点讲解_第1页](http://file4.renrendoc.com/view/929db6e529e247a71afa17c8180a4856/929db6e529e247a71afa17c8180a48561.gif)
![离散数学专题知识点讲解_第2页](http://file4.renrendoc.com/view/929db6e529e247a71afa17c8180a4856/929db6e529e247a71afa17c8180a48562.gif)
![离散数学专题知识点讲解_第3页](http://file4.renrendoc.com/view/929db6e529e247a71afa17c8180a4856/929db6e529e247a71afa17c8180a48563.gif)
![离散数学专题知识点讲解_第4页](http://file4.renrendoc.com/view/929db6e529e247a71afa17c8180a4856/929db6e529e247a71afa17c8180a48564.gif)
![离散数学专题知识点讲解_第5页](http://file4.renrendoc.com/view/929db6e529e247a71afa17c8180a4856/929db6e529e247a71afa17c8180a48565.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
离散数学专题知识点讲解第一页,共二十一页,2022年,8月28日16二月2023专题一:图论基础问题知识点讲解该材料用于图论第2讲课知识点讲解环节第二页,共二十一页,2022年,8月28日在无向图G=<V,E>中,与结点v(vV)关联的边的条数(有环时计算两次),称为该结点的度数,记为deg(v);结点的度数(次数)在有向图G=<V,E>中,以结点v为始点引出的边的条数,称为该结点的出度,记为deg+(v);以结点v为终点引入的边的条数,称为该结点的入度,记为deg-(v);而结点的引出度数和引入度数之和称为该结点的度数,记为deg(v),即deg(v)=deg+(v)+deg-(v);第三页,共二十一页,2022年,8月28日对于图G=<V,E>,度数为1的结点称为悬挂结点,它所关联的边称为悬挂边。在图G=<V,E>中,称度数为奇数的结点为奇度数结点,度数为偶数的结点为偶度数结点。结点的度数(次数)v5是悬挂结点,<v1,v5>为悬挂边。第四页,共二十一页,2022年,8月28日度数序列设V={v1,v2,…,vn}为图G的结点集,称(deg(v1),deg(v2),…,deg(vn))为G的度数序列。上图的度数序列为(3,3,5,1,0)。第五页,共二十一页,2022年,8月28日(3,3,2,3),(5,2,3,1,4)能成为图的度数序列吗?为什么?已知图G中有10条边,4个度数为3的结点,其余结点的度数均小于等于2,问G中至少有多少个结点?为什么?度数序列解1)由于这两个序列中,度数为奇数的结点个数均为奇数,由握手定理的推论知,它们都不能成为图的度数序列。2)图中边数为10,由握手定理知,G中所有结点的度数之和为20,4个度数为3的结点占去12度,还剩下8度。若其余全是度数为2的结点,还需要4个结点来占用这8度,所以G至少有8个结点。第六页,共二十一页,2022年,8月28日握手定理在无向图G=<V,E>中,则所有结点的度数的总和等于边数的两倍,即:在有向图G=<V,E>中,则所有结点的引出度数之和等于所有结点的引入度数之和,所有结点的度数的总和等于边数的两倍,即:第七页,共二十一页,2022年,8月28日推论在图G=<V,E>中,其V={v1,v2,v3,…,vn},E={e1,e2,……,em},度数为奇数的结点个数为偶数。证明设V1={v|vV且deg(v)=奇数},V2={v|vV且deg(v)=偶数}。显然,V1∩V2=Φ,且V1∪V2=V,于是有:由于上式中的2m和(偶数之和为偶数)均为偶数,因而也为偶数。于是|V1|为偶数(因为V1中的结点v之deg(v)都为奇数),即奇度数的结点个数为偶数。■第八页,共二十一页,2022年,8月28日度数序列设V={v1,v2,…,vn}为图G的结点集,称(deg(v1),deg(v2),…,deg(vn))为G的度数序列。上图的度数序列为(3,3,5,1,0)。第九页,共二十一页,2022年,8月28日(3,3,2,3),(5,2,3,1,4)能成为图的度数序列吗?为什么?已知图G中有10条边,4个度数为3的结点,其余结点的度数均小于等于2,问G中至少有多少个结点?为什么?解1)由于这两个序列中,度数为奇数的结点个数均为奇数,由握手定理的推论知,它们都不能成为图的度数序列。2)图中边数为10,由握手定理知,G中所有结点的度数之和为20,4个度数为3的结点占去12度,还剩下8度。若其余全是度数为2的结点,还需要4个结点来占用这8度,所以G至少有8个结点。度数序列第十页,共二十一页,2022年,8月28日子图定义8.7
设有图G=<V,E>和图G'=<V',E'>。若V'V,E'E,则称G'是G的子图,记为G'G。若G'G,且G'≠G(即V'V或E'E),则称G'是G的真子图,记为G'G。若V'=V,E'E,则称G'是G的生成子图。设V"V且V"≠,以V"为结点集,以两个端点均在V"中的边的全体为边集的G的子图称为V"导出的G的子图,简称V"的导出子图。第十一页,共二十一页,2022年,8月28日
在如图中,给出了图G以及它的真子图G'和生成子图G"。G'是结点集{v1,v2,v3,v4,v5}的导出子图。显然,每个图都是它自身的子图。子图第十二页,共二十一页,2022年,8月28日完全图设G=<V,E>为一个具有n个结点的无向简单图,如果G中任一个结点都与其余n-1个结点相邻接,则称G为无向完全图,简称G为完全图,记为Kn。设G=<V,E>为一个具有n个结点的有向简单图,若对于任意u,vV(uv),既有有向边<u,v>,又有有向边<v,u>,则称G为有向完全图,在不发生误解的情况下,也记为Kn。第十三页,共二十一页,2022年,8月28日完全图无向的简单完全图K3,K4,K5和有向的简单完全图K3。无向完全图Kn的边数为=
n(n-1),有向完全图Kn的边数为=n(n-1)。第十四页,共二十一页,2022年,8月28日改变才能更好的生存!29--15补图设G=<V,E>为具有n个结点的简单图,从完全图Kn中删去G中的所有边而得到的图称为G相对于完全图Kn的补图,简称G的补图,记为G。这里,当G为有向图时,则Kn为有向完全图:当G为无向图时,则Kn为无向完全图显然,G与G互为补图,即G=G。第十五页,共二十一页,2022年,8月28日改变才能更好的生存!29--16补图第十六页,共二十一页,2022年,8月28日图的同构图的同构:设两个图G=<V,E>和G'=<V',E'>,如果存在双射函数g:V→V',使得对于任意的e=(vi,vj)(或者<vi,vj>)∈E当且仅当e'=(g(vi),g(vj))(或者<g(vi),g(vj)>)∈E',并且e与e'的重数相同,则称G与G'同构,记为G≌G'。第十七页,共二十一页,2022年,8月28日图的同构
容易验证:G1≌G2,结点之间的对应关系为:a→v1,b→v2,c→v3,d→v4,e→v5;G3≌G4;G5≌G6;但G7与G8不同构。图G5称为彼得森图。第十八页,共二十一页,2022年,8月28日两个图同构的必要条件结点数目相同;边数相同;度数相同的结点数相同。注意:这三个条件并不是充分条件。例如下面两个图满足这三个条件,但它们不同构。yxuvxyvu若图的结点可以任意挪动位置,而边是完全弹性的,只要在不拉断的条件下,一个图可以变形为另一个图,那么这两个图是同构的。图的同构第十九页,共二十一页,2022年,8月28日图论里的图要比欧几里得几何学里的图抽象得多。由于它描绘的是事物之间的某种“关系”,而不是事物的几何形状,因此它不在乎图形的外形与大小,更不涉及长度、面积、体积、角度等这些量,它只包含顶点和边这两种要素,用这
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 生产设备维护与升级策略
- 专业技术人员聘用协议书范本
- 社区农业的未来发展数字化农贸市场建设
- 电影产业发展报告教育领域的新机遇
- 网站设计服务协议书(2篇)
- 电能质量评估与电力工程测绘服务的结合
- 网络服务授权协议书(2篇)
- 网络安全审计协议书(2篇)
- 无产权纠纷门面房租用协议书范本
- 社区医院综合运营管理体系优化研究
- 海洋气候预测模型创新研究-深度研究
- 《客户服务基础》教案及课件项
- 2025年湖南工业职业技术学院高职单招职业技能测试近5年常考版参考题库含答案解析
- 物理(A版)-安徽省合肥一中(省十联考)2024-2025学年度高二年级上学期期末测试试题和答案
- 智能RPA财务机器人开发教程-基于来也UiBot 课件 第1章-机器人流程自动化概述
- 2024.8.1十七个岗位安全操作规程手册(值得借鉴)
- 小王子-英文原版
- T-CHTS 10021-2020 在役公路隧道长期监测技术指南
- 医院门诊医生绩效考核标准及评分细则
- 医院纳入定点后使用医疗保障基金的预测性分析报告
- 北师大版六年级下册书法练习指导教案教学设计
评论
0/150
提交评论