ImageVerifierCode 换一换
格式:PPT , 页数:29 ,大小:1.22MB ,
资源ID:5442465      下载积分:10 金币
验证码下载
登录下载
邮箱/手机:
验证码: 获取验证码
温馨提示:
支付成功后,系统会自动生成账号(用户名为邮箱或者手机号,密码是验证码),方便下次登录下载和查询订单;
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝    微信支付   
验证码:   换一换

开通VIP
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【https://www.zixin.com.cn/docdown/5442465.html】到电脑端继续下载(重复下载【60天内】不扣币)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录   QQ登录  
声明  |  会员权益     获赠5币     写作写作

1、填表:    下载求助     留言反馈    退款申请
2、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
3、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
4、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
5、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
6、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
7、本文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。

注意事项

本文(离散数学-无向树省名师优质课赛课获奖课件市赛课一等奖课件.ppt)为本站上传会员【精****】主动上传,咨信网仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知咨信网(发送邮件至1219186828@qq.com、拔打电话4008-655-100或【 微信客服】、【 QQ客服】),核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载【60天内】不扣币。 服务填表

离散数学-无向树省名师优质课赛课获奖课件市赛课一等奖课件.ppt

1、离散数学李书杰 合肥工业大学离散数学1/291&学习内容学习内容10.1 10.1 无向树无向树无向树无向树10.2 10.2 根树根树根树根树2/2923/293假如将上图看作一个图话,这个图就是一棵树,以下列图。假如将上图看作一个图话,这个图就是一棵树,以下列图。4/294定义定义10.2.1 10.2.1 无向树从无向图出发定义树无向树从无向图出发定义树n无向树无向树(树树):连通而无回路无向图,普通用连通而无回路无向图,普通用T表示表示n叶叶:树中度数为树中度数为1顶点顶点n分支点分支点/内部结点内部结点:树中度数树中度数1顶点顶点n森林森林:一一个个非非连连通通图图,假假如如其其每每

2、个个连连通通分分支支都都是是树树,则则称称为为森林森林n平凡树平凡树:平凡图,只有一个点且无边图平凡图,只有一个点且无边图n右图为一棵右图为一棵12阶树阶树.n申明申明:本章中所讨论回路均本章中所讨论回路均n 指简单回路或初级回路指简单回路或初级回路 5/295无向树性质无向树性质定定理理10.2.1 设设G=是是n阶阶m条条边边无无向向图图,则则下下面面各各命命题题是是等价:等价:(1)G是树是树(连通无回路连通无回路);(2)G中无回路且中无回路且m=n 1;(3)G是连通且是连通且m=n 1;(4)G中中没没有有回回路路,但但在在任任何何两两个个不不一一样样顶顶点点之之间间加加一一条条新

3、新边边,就会得到一条唯一基本回路就会得到一条唯一基本回路.(5)G是连通且是连通且G中任何边均为桥中任何边均为桥;(6)G中任意两个顶点之间存在惟一中任意两个顶点之间存在惟一 一条基本通路。一条基本通路。6/296(1)(2)证实假如G是无回路连通图,则G中无回路且m=n1,其中m是边数,n是结点数证实 归纳法。当n=2时,因为G连通无回路,所以只有m=1,故m=n-1成立。假设n=k-1时命题成立,当n=k时,因G是无回路且连通,则最少有一个度为1结点u,设与其关联边为(u,w),删去u,得到一个k-1个结点连通无向图G,7/297(1)(2)证实(续)由归纳假设可知,G边数m=n-1=(k

4、-1)-1=k-2。再将结点u及(u,w)放入原位,恢复到图G,那么G边数m=m+1=(k-2)+1=k-1,结点数n=n+1=k,故m=n-1成立。8/298(2)(3)证实假如G中无回路且m=n1,其中m是边数,n是结点数,则连通且m=n1;只须证实G是连通。证实 设G有k个连通分枝G1,Gk(k1),Gi有ni个结点,mi条边,因为Gi连通无回路,所以有 mi=ni-1,n=n1+n2+nk m=m1+m2+mk=(n1-1)+(n2-1)+(nk-1)=n-k因为m=n-1,所以k=1,故G是连通。9/299(3)(4)证实假如G连通且m=n1,则G中无回路,但增加一条新边,得到一个且

5、仅有一个包含新边回路。证实 归纳法。当n=2时,m=n-1=1,必无回路,假如增加一边得到且仅得到一个回路。设n=k-1时命题成立。考查n=k时情况。因为G是连通,所以每个结点u有deg(u)1,下面证实最少有一个结点u0使deg(u0)=1。若不存在,则每个结点度最少为2,所以2n2m,即n m,这与m=n-1矛盾。10/2910(3)(4)证实首先证实G中也无回路删去u0及其关联边,得到含有k-1个结点图G,G连通且m=n1。由归纳假设知G无回路。在G中加入u0及其关联边恢复到G,则G无回路。再证实在G中任意两结点之间增加一条边,得到一条且仅有一条回路。若在G中增加一条边(ui,uj),因

6、为G连通,则在G中存在一条从ui到uj路,那么这条路与新加入边(ui,uj)组成回路,而且这个回路是唯一。若不唯一,删掉边(ui,uj)边,G中必有回路,矛盾。11/2911(4)(5)证实假如G中无回路,但增加一条新边,得到一个且仅有一个包含新边回路,则G连通且每条边均为桥。证实 反证法。假设G不连通,则存在结点ui与uj,在ui和uj之间没有路,所以增加边(ui,uj)不会产生回路,与已知矛盾。因为G无回路,故删掉任意条边e都使G-e为非连通,所以G中每条边都是桥。12/2912(5)(6)证实假如G连通且每条边均为桥,则G中任意两个结点之间存在惟一路径。证实 由G是连通可知,任意两个结点

7、间有一条路,若存在两点它们之间有多于一条路,则G中必有回路,删去该回路上任一边,图仍是连通,与G中每条边都是桥矛盾。13/2913(6)(1)证实假如G中任意两个结点之间存在惟一路径,则G是无回路连通图。证实 因为任意两结点间有唯一条路,则图G必连通。若G有回路,则在回路上任意两结点间有两条路,与已知矛盾。14/2914定理定理10.2.210.2.2 设设T T 是是n n阶非平凡无向树,则阶非平凡无向树,则T T中最少有两片树叶中最少有两片树叶.证证 设设T T有有x x片树叶,片树叶,m m条边。由握手定理及定理条边。由握手定理及定理10.2.110.2.1可知,可知,由上式解出由上式解

8、出x x 2.2.无向树性质无向树性质(续续)15/2915例题例题例例1 已已知知无无向向树树T中中,有有1个个3度度顶顶点点,2个个2度度顶顶点点,其其余余顶顶点点全是树叶全是树叶.试求树叶数试求树叶数,并画出满足要求非同构无向树并画出满足要求非同构无向树.解解 用树性质用树性质m=n 1和握手定理和握手定理.设有设有x片树叶,于是片树叶,于是 n=1+2+x=3+x,2m=2(n 1)=2(2+x)=1 3+2 2+x解出解出x=3,故,故T有有3片树叶片树叶.T度数列为度数列为1,1,1,2,2,3 有有2棵非同构无向树棵非同构无向树,如图所表示如图所表示16/2916例题例题例例2

9、已已知知无无向向树树T有有5片片树树叶叶,2度度与与3度度顶顶点点各各1个个,其其余余顶顶点点度数均为度数均为4.求求T阶数阶数n.解解 设设T阶阶数数为为n,则则边边数数为为n 1,4度度顶顶点点个个数数为为n 7.由由握握手手定理得定理得 2m=2(n 1)=5 1+2 1+3 1+4(n 7)解出解出n=8,4度顶点为度顶点为1个个.T度数列为度数列为1,1,1,1,1,2,3,4 17/2917p生成树生成树p设设G G为为无无向向连连通通图图,若若G G生生成成子子图图(v=vv=v)是是一一棵棵树树,则则称这棵树为称这棵树为G G生成树;生成树;p设设G G一一棵棵生生成成树树为为

10、T,T,则则T T中中边边称称为为T T树树枝枝,在在G G中中而而不不在在T T中中边称为边称为T T弦弦,p全部弦集合称为全部弦集合称为生成树生成树T T补补 p注意:注意:生成树生成树T T补补不一定连通不一定连通,也不一定不含回路也不一定不含回路.p右图黑边组成生成树右图黑边组成生成树p红边组成补红边组成补定义定义10.2.2 10.2.2 18/2918生成树生成树定义定义10.2.2 若图若图G生成子图是一棵树,则该树称为生成子图是一棵树,则该树称为G生成树。生成树。生成树生成树T树枝树枝:G在在T中边中边生成树生成树T弦弦:G不在不在T中边中边生成树生成树T补补(或(或余树)余树

11、):全部弦集合导出子图全部弦集合导出子图注意:注意:不一定连通不一定连通,也不一定不含回路也不一定不含回路.19/2919举例举例例例 以下列图,以下列图,T=e1,e6,e7,e4,e3,黑线表示生成树,红线组成树补。黑线表示生成树,红线组成树补。=e2,e5,e8余树是非连通,无回路余树是非连通,无回路余树是非连通,有回路余树是非连通,有回路20/2920举例举例例例 设设T是是6阶无向简单图阶无向简单图G一棵生成树,讨论下面问题:一棵生成树,讨论下面问题:(1)当当G边数边数e=9时,时,T补是补是G生成树吗?生成树吗?(2)当当G边数边数e=12时,时,T补是补是G生成树吗?生成树吗?

12、(3)当当G边数边数e=10时,时,T补可能有哪几个情况?补可能有哪几个情况?解解 对于树对于树T,e=v-1,而任何,而任何ev或或ev-1图都不是树图都不是树(1)T补边数为补边数为9-5=4,所以不可能是树。,所以不可能是树。(2)T补边数为补边数为12-5=7,也不可能是树。,也不可能是树。(3)有两种情况:)有两种情况:T补是生成树;补是生成树;T补不连通且含圈。补不连通且含圈。21/2921生成树存在性生成树存在性 n定理定理10.2.3 无向图无向图G含有生成树当且仅当含有生成树当且仅当G连通。连通。n证实证实 必要性必要性,显然。,显然。n充分性充分性(破圈法)。(破圈法)。n

13、 若若G中无回路,中无回路,G为自己生成树。为自己生成树。n 若若G中含回路,任取一回路,随意地删除回路上一条边,中含回路,任取一回路,随意地删除回路上一条边,n若再有回路再删除回路上一条边,直到最终无回路为止。若再有回路再删除回路上一条边,直到最终无回路为止。n易知所得图无回路、连通且为易知所得图无回路、连通且为G生成子图,生成子图,n所认为所认为G生成树。生成树。22/2922求连通图G=生成树算法n1 破圈法n2 避圈法n3 广度优先搜索算法23/2923举例(破圈法)删除边删除边1删除边删除边3删除边删除边6生成树不是唯一!24/2924最小生成树最小生成树 对无向图或有向图每一条边对

14、无向图或有向图每一条边e附加一个实数附加一个实数w(e),称作称作边边e权权.图连同附加在边上权称作图连同附加在边上权称作赋权图赋权图,记作记作G=.设设G 是是G子图子图,G 全部边权和称作全部边权和称作G 权权,记作记作W(G).最小生成树最小生成树:赋权图权最小生成树赋权图权最小生成树求最小生成树算法求最小生成树算法避圈法避圈法(克鲁斯卡尔克鲁斯卡尔/Kruskal算法算法)设设G=,将非环边按权从小到大排序:将非环边按权从小到大排序:e1,e2,em.(1)把把e1加入加入T中中(2)检检验验e2,若若e2与与e1不不组组成成回回路路,则则将将e2加加入入T中中,不不然然弃弃去去e2.

15、(3)检验检验e3,重复进行直至得到生成树为止重复进行直至得到生成树为止.25/2925实例实例例例 求图一棵最小生成树求图一棵最小生成树 W(T)=3826/29261234456778123445677827/2927普里姆普里姆(Prim)(Prim)算法算法普里姆算法基本思想:普里姆算法基本思想:普里姆算法基本思想:普里姆算法基本思想:从连通图从连通图从连通图从连通图 G G=V V,E E 中某一顶点中某一顶点中某一顶点中某一顶点 u u0 0 出出出出发,选择与它关联含有最小权值边发,选择与它关联含有最小权值边发,选择与它关联含有最小权值边发,选择与它关联含有最小权值边(u u0

16、0,v v),将其顶点加入到将其顶点加入到将其顶点加入到将其顶点加入到生成树顶点集合生成树顶点集合生成树顶点集合生成树顶点集合U U中。以后每中。以后每中。以后每中。以后每一步从一步从一步从一步从一个顶点在一个顶点在一个顶点在一个顶点在U U中中中中,而,而,而,而另一个顶点不在另一个顶点不在另一个顶点不在另一个顶点不在U U中中中中各条边中选择各条边中选择各条边中选择各条边中选择权值最小边权值最小边权值最小边权值最小边(u u,v v),把它顶点把它顶点把它顶点把它顶点加入到加入到加入到加入到集合集合集合集合U U中。如此继续下去,直到网络中中。如此继续下去,直到网络中中。如此继续下去,直到网络中中。如此继续下去,直到网络中全部顶点都加入到生成树顶点集合全部顶点都加入到生成树顶点集合全部顶点都加入到生成树顶点集合全部顶点都加入到生成树顶点集合U U中为止。中为止。中为止。中为止。28/2928用普里姆用普里姆(Prim)算法结构最小生成树过程算法结构最小生成树过程123465565173254612346551324从节点开始,选最小权值边1,节点(,)入U;从U中选最小权值边5,且对应节点不在U中,入U;从U中选最小权值边3,且对应节点不在U中,入U;从U中选最小权值边4,且对应节点不在U中,入U;从U中选最小权值边2,且对应节点不在U中,入U;29/2929

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        获赠5币

©2010-2024 宁波自信网络信息技术有限公司  版权所有

客服电话:4008-655-100  投诉/维权电话:4009-655-100

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :gzh.png    weibo.png    LOFTER.png 

客服