离散数学省公共课一等奖全国赛课获奖课件.pptx
《离散数学省公共课一等奖全国赛课获奖课件.pptx》由会员分享,可在线阅读,更多相关《离散数学省公共课一等奖全国赛课获奖课件.pptx(110页珍藏版)》请在咨信网上搜索。
1、电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程离 散 数 学电子科技大学计算机科学与工程学院示 范 性 软 件 学 院10 十月 第1页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-2 2第第1111章章 特殊图特殊图 偶图偶图3平面图平面图4欧拉图欧拉图1集合表示方法集合表示方法2哈密顿图哈密顿图2第2页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-3 311.0 11.0 内容提要内容提要 1.1.几几个个特特殊殊图图概概念念:欧欧拉拉图图、哈哈密密顿顿图图、偶偶图图、
2、平面图;平面图;2.2.欧拉图、哈密顿图、偶图、平面图判定;欧拉图、哈密顿图、偶图、平面图判定;3.3.偶图匹配、图着色;偶图匹配、图着色;4.4.欧拉图、哈密顿图、偶图、平面图应用欧拉图、哈密顿图、偶图、平面图应用第3页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-4 410.1 10.1 本章学习要求本章学习要求重点掌握重点掌握普通掌握普通掌握了解了解11 1 各个特殊图各个特殊图相关基本概念相关基本概念2 2 各个特殊图各个特殊图性质性质3 3 各个特殊图各个特殊图判定方法判定方法 31 1 各个特殊图各个特殊图应用应用2 2 图着色图着色2
3、1 1 哈密顿图、哈密顿图、平面图判断平面图判断2 2 证实方法证实方法 第4页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-5 511.2 11.2 欧拉图欧拉图 11.2.1 11.2.1 欧拉图引入与定义欧拉图引入与定义A AB BC CD Db b5 5b b2 2b b1 1b b3 3b b4 4b b7 7b b6 6B BC CA AD Db b6 6b b2 2b b5 5b b7 7b b4 4b b1 1b b3 3第5页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-6 6定义定义
4、11.2.111.2.1设设G G是是无无孤孤立立结结点点图图,若若存存在在一一条条通通路路(回回路路),经经过过图图中中每每边边一一次次且且仅仅一一次次,则则称称此此通通路路(回回路路)为为该该图图一一条条欧欧拉拉通通路路(回回路路)(Eulerian)(Eulerian Entry/Circuit)Entry/Circuit)。含有欧拉回路图称为含有欧拉回路图称为欧拉图欧拉图(Eulerian Graph)(Eulerian Graph)。要求:要求:平凡图为欧拉图。平凡图为欧拉图。以上定义既适合无向图,又适合有向图。以上定义既适合无向图,又适合有向图。第6页电子科技大学离散数学课程组电子
5、科技大学离散数学课程组国家精品课程国家精品课程110-110-7 7欧拉通路和欧拉回路特征欧拉通路和欧拉回路特征 欧欧拉拉通通路路是是经经过过图图中中全全部部边边通通路路中中长长度度最最短短通通路路,即为,即为经过图中全部边简单通路经过图中全部边简单通路;欧欧拉拉回回路路是是经经过过图图中中全全部部边边回回路路中中长长度度最最短短回回路路,即为,即为经过图中全部边简单回路经过图中全部边简单回路。假假如如仅仅用用边边来来描描述述,欧欧拉拉通通路路和和欧欧拉拉回回路路就就是是图中全部边一个全排列图中全部边一个全排列。第7页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程
6、110-110-8 8例例11.2.111.2.1判判断断下下面面6 6个个图图中中,是是否否是是欧欧拉拉图图?是是否否存存在在欧欧拉拉通路?通路?v v3 3v v1 1v v2 2v v4 4(c)(c)v v3 3v v1 1v v2 2v v4 4(a)(a)v v3 3v v1 1v v2 2v v4 4(b)(b)v v3 3v v1 1v v2 2v v4 4(f)(f)v v3 3v v1 1v v2 2v v4 4(d)(d)v v3 3v v1 1v v2 2v v4 4(e)(e)欧拉图欧拉图 欧欧拉拉图图 不是欧拉图,但不是欧拉图,但存在欧拉通路存在欧拉通路 不存在欧不
7、存在欧拉通路拉通路 不不存存在在欧欧拉拉通通路路 不是欧拉图,但存在欧拉通路不是欧拉图,但存在欧拉通路 第8页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-9 911.2.2 11.2.2 欧拉图判定欧拉图判定 定定理理11.2.111.2.1 无无向向图图G G=V,E含含有有一一条条欧欧拉拉通通路路,当且仅当当且仅当G G是连通,且仅有零个或两个奇度数结点。是连通,且仅有零个或两个奇度数结点。分分析析 只只要要找找到到了了,就就是是存存在在。我我们们详详细细找找一一条条欧欧拉通路。对于结点度数,我们在通路中去计算。拉通路。对于结点度数,我们在通
8、路中去计算。证证实实 若若G G为为平平凡凡图图,则则定定理理显显然然成成立立。故故我我们们下下面讨论均为非平凡图。面讨论均为非平凡图。第9页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-1010必要性:必要性:设设G G含含有有一一条条欧欧拉拉通通路路L L=,则则L L经经过过G G中中每每条条边边,因因为为G G中中无无孤孤立立结结点点,因因而而L L经经过过G G全部结点,所以全部结点,所以G G是连通。是连通。对对欧欧拉拉通通路路L L任任意意非非端端点点结结点点 ,在在L L中中每每出出现现 一一次次,都都关关联联两两条条边边 和和 ,
9、而而当当 重重复复出出现现时时,它它又又关关联联另另外外两两条条边边,因因为为在在通通路路L L中中边边不不可可能能重重复复出出现现,因因而而每每出出现现一一次次都都将将使使取取得得2 2度度。若若在在L L中中重复出现重复出现p p次,则次,则deg()=2pdeg()=2p。第10页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-1111若若端端点点 ,设设 、在在通通路路中中作作为为非非端端点点分别出现分别出现p1p1和和p2p2次,则次,则deg()=2p1+1deg()=2p1+1,deg()=2p2+1deg()=2p2+1因而因而G G
10、有两个度数为奇数结点。有两个度数为奇数结点。若若端端点点 =,设设在在通通路路中中作作为为非非端端点点出出现现p3p3次次,则则deg()=1+2p3+1=2(p3+1)deg()=1+2p3+1=2(p3+1)因而因而G G无度数为奇数结点。无度数为奇数结点。第11页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-1212充分性:结构性证实。充分性:结构性证实。我我们们从从两两个个奇奇度度数数结结点点之之一一开开始始(若若无无奇奇度度数数结结点点,可可从从任任一一结结点点开开始始)结结构构一一条条欧欧拉拉通通路路,以以每每条条边边最最多多经经过过一
11、一次次方方式式经经过过图图中中边边。对对于于度度数数为为偶偶数数结结点点,经经过过一一条条边边进进入入这这个个结结点点,总总能能够够经经过过一一条条未未经经过过边边离离开开这这个个结结点点,所所以以,这这么么结结构构过过程程一一定定以以抵抵达达另另一一个个奇奇度度数数结结点点而而告告终终(若若无无奇奇度度数数结结点点,则则以以回回到到原原出出发发点点而而告告终终)。假假如如图图中中全全部部边边已已用用这这种种方方式式经经过过了了,显显然然这这就就是是所所求求欧欧拉拉通通路路。假假如如图图中中不不是是全全部部边边都都经经过过了了,我我们们去去掉掉已已经经过过边边,得得到到一一个个由由剩剩下下边边
12、组组成成子子图图,这这个个子子图图全全部部结结点点度度数均为偶数。数均为偶数。第12页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-1313因因为为原原来来图图是是连连通通,所所以以,这这个个子子图图必必与与我我们们已已经经过过通通路路在在一一个个或或多多个个结结点点相相接接。从从这这些些结结点点中中一一个个开开始始,我我们们再再经经过过边边结结构构通通路路,因因为为结结点点度度数数全全是是偶偶数数,所所以以,这这条条通通路路一一定定最最终终回回到到起起点点。我我们们将将这这条条回回路路加加到到已已结结构构好好通通路路中中间间组组合合成成一一条条通
13、通路路。如如有有必必要要,这这一一过过程程重重复复下下去去,直直到到我我们们得得到到一一条条经过图中全部边通路,即欧拉通路。经过图中全部边通路,即欧拉通路。由由定定理理11.2.111.2.1证证实实知知:若若连连通通无无向向图图有有两两个个奇奇度数结点,则它们是度数结点,则它们是G G中每条欧拉通路端点中每条欧拉通路端点。第13页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-1414结论结论推推论论11.2.111.2.1 无无向向图图G G=V,E含含有有一一条条欧欧拉拉回回路路,当且仅当当且仅当G G是连通,而且全部结点度数均为偶数。是连通,
14、而且全部结点度数均为偶数。定定理理11.2.211.2.2 有有向向图图G G含含有有一一条条欧欧拉拉通通路路,当当且且仅仅当当G G是是连连通通,且且除除了了两两个个结结点点以以外外,其其余余结结点点入入度度等等于于出出度度,而而这这两两个个例例外外结结点点中中,一一个个结结点点入入度度比比出出度大度大1 1,另一个结点出度比入度大,另一个结点出度比入度大1 1。推推论论11.2.211.2.2 有有向向图图G G含含有有一一条条欧欧拉拉回回路路,当当且且仅仅当当G G是连通,且全部结点入度等于出度。是连通,且全部结点入度等于出度。第14页电子科技大学离散数学课程组电子科技大学离散数学课程组
15、国家精品课程国家精品课程110-110-1515欧拉通路与欧拉回路判别准则欧拉通路与欧拉回路判别准则 对对任任意意给给定定无无向向连连通通图图,只只需需经经过过对对图图中中各各结结点点度度数数计计算算,就就可可知知它它是是否否存存在在欧欧拉拉通通路路及及欧欧拉拉回回路路,从从而而知知道道它它是是否否为为欧欧拉拉图图;对对任任意意给给定定有有向向连连通通图图,只只需需经经过过对对图图中中各各结结点点出出度度与与入入度度计计算算,就就可可知知它它是是否否存存在在欧欧拉拉通通路路及及欧欧拉拉回回路路,从从而而知知道道它它是否为欧拉图。是否为欧拉图。利利用用这这项项准准则则,很很轻轻易易判判断断出出哥
16、哥尼尼斯斯堡堡七七桥桥问问题题是是无无解解,因因为为它它所所对对应应图图中中全全部部4 4个个结结点点度度数数均均为奇数;也很轻易得到例为奇数;也很轻易得到例11.2.111.2.1结论。结论。第15页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-1616定义定义11.2.211.2.2设设G=G=,eEeE,假如,假如p(G-e)p(G-e)p(G)p(G)称称e e为为G G桥桥(Bridge)(Bridge)或或割边割边(Cut edge)(Cut edge)。显然,显然,全部悬挂边都是桥全部悬挂边都是桥。第16页电子科技大学离散数学课程组电
17、子科技大学离散数学课程组国家精品课程国家精品课程110-110-1717FleuryFleury算法算法算算法法11.2.111.2.1 求求欧欧拉拉图图G G=V,E欧欧拉拉回回路路FleuryFleury算算法:法:(1 1)任取)任取v v0 0VV,令,令P P0 0=v=v0 0,i=0i=0;(2 2)按下面方法从)按下面方法从E-eE-e1 1,e,e2 2,e,ei i 中选取中选取e ei+1i+1:a.ea.ei+1i+1与与v vi i相关联;相关联;b.b.除除非非无无别别边边可可选选取取,不不然然e ei+1i+1不不应应该该为为G G=G-eG-e1 1,e,e2
18、2,e,ei i 中桥;中桥;(3 3)将将 边边 e ei+1i+1加加 入入 通通 路路 P P0 0中中,令令 P P0 0 =v v0 0e e1 1v v1 1e e2 2eei iv vi ie ei+1i+1v vi+1i+1,i=i+1i=i+1;(4 4)假如)假如i=|E|i=|E|,结束,不然转,结束,不然转(2)(2)。第17页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-1818例例11.2.211.2.2用用FleuryFleury算算法法求求欧欧拉拉图一条欧拉回路。图一条欧拉回路。v v1 1v v7 7v v5 5v
19、 v3 3v v2 2v v8 8v v4 4e e1 1e e2 2e e3 3e e4 4e e5 5e e6 6e e1010e e7 7e e8 8e e9 9e e1111e e1212v v6 6分分 析析 求求 从从 v v1 1出出 发发,按按 照照FleuryFleury算算法法,每每次次走走一一条条边边,在在可可能能情情况况下下,不不走走桥桥。比比如,在得到如,在得到P P7 7=v=v1 1e e1 1v v2 2e e2 2v v3 3e e3 3v v4 4e e4 4v v5 5e e5 5v v6 6e e6 6v v7 7e e7 7v v8 8时时,G G=G
20、-eG-e1 1,e e2 2,e e7 7 中中e e8 8是是桥桥,所所以以下下一一步步选选择走择走e e9 9,而不要走,而不要走e e8 8。解解 从从v v1 1出发一条欧拉回路为:出发一条欧拉回路为:P P1212=v=v1 1e e1 1v v2 2e e2 2v v3 3e e3 3v v4 4e e4 4v v5 5e e5 5v v6 6e e6 6v v7 7e e7 7v v8 8e e9 9v v2 2e e1010v v4 4e e1111v v6 6e e1212v v8 8e e8 8v v1 1 第18页电子科技大学离散数学课程组电子科技大学离散数学课程组国家
21、精品课程国家精品课程110-110-191911.2.3 11.2.3 欧拉图难点欧拉图难点 1.1.仅有欧拉通路而无欧拉回路图不是欧拉图;仅有欧拉通路而无欧拉回路图不是欧拉图;2.2.图图中中是是否否存存在在欧欧拉拉通通路路、欧欧拉拉回回路路图图判判定定非非常常简单,只需要数一下列图中结点度数即可;简单,只需要数一下列图中结点度数即可;3.3.使使用用FleuryFleury算算法法求求欧欧拉拉通通路路(回回路路)时时,每每次次走走一条边,在可能情况下,不走桥。一条边,在可能情况下,不走桥。第19页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-2
22、02011.2.4 11.2.4 欧拉图应用欧拉图应用 1 1、一笔画问题、一笔画问题 所所谓谓“一一笔笔画画问问题题”就就是是画画一一个个图图形形,笔笔不不离离纸,每条边只画一次而不许重复,画完该图。纸,每条边只画一次而不许重复,画完该图。“一一笔笔画画问问题题”本本质质上上就就是是一一个个无无向向图图是是否否存存在在欧欧拉拉通通路路(回回路路)问问题题。假假如如该该图图为为欧欧拉拉图图,则则能能够够一一笔笔画画完完该该图图,而而且且笔笔又又回回到到出出发发点点;假假如如该该图图只只存存在在欧欧拉拉通通路路,则则能能够够一一笔笔画画完完该该图图,但但笔笔回回不不到到出出发发点点;假假如如该该
23、图图中中不不存存在在欧欧拉拉通通路路,则则不不能能一一笔画完该图。笔画完该图。第20页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-2121例例11.2.311.2.3图中三个图能否一笔画?为何?图中三个图能否一笔画?为何?v v1 1v v2 2v v3 3v v4 4v v5 5(b(b)v v1 1v v2 2v v3 3v v4 4(c(c)v v1 1v v2 2v v3 3v v4 4v v5 5(a(a)解解 因因为为图图(a)(a)和和(b)(b)中中分分别别有有0 0个个和和2 2个个奇奇度度数数结结点点,所所以以它它们们分分别别
24、是是欧欧拉拉图图和和存存在在欧欧拉拉通通路路,所所以以能能够够一一笔笔画画,而而且且在在(a)(a)中中笔笔能能回回到到出出发发点点,而而(b)(b)中中笔笔不不能能回回到到出出发发点点。图图c c中中有有4 4个个度度数数为为3 3结结点点,所所以以不存在欧拉通路,所以不能一笔画。不存在欧拉通路,所以不能一笔画。第21页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-22222 2、蚂蚁比赛问题、蚂蚁比赛问题 例例11.2.411.2.4 甲甲、乙乙两两只只蚂蚂蚁蚁分分别别位位于于图图结结点点A A、B B处处,并并设设图图中中边边长长度度相相等等
25、。甲甲、乙乙进进行行比比赛赛:从从它它们们所所在在结结点点出出发发,走走过过图图中中全全部部边边最最终终抵抵达达结结点点C C处处。假假如如它它们们速速度度相相同同,问问谁先抵达目标地?谁先抵达目标地?A(甲)B(乙)C解解 图图中中仅仅有有两两个个度度数数为为奇奇数数结结点点B B、C C,因因而而存存在在从从B B到到C C欧欧拉拉通通路路,蚂蚂蚁蚁乙乙走走到到C C只只要要走走一一条条欧欧拉拉通通路路,边边数数为为9 9条条,而而蚂蚂蚁蚁甲甲要要想想走走完完全全部部边边抵抵达达C C,最最少少要要先先走走一一条条边边抵抵达达B B,再再走走一一条条欧欧拉拉通通路路,因因而而它它最最少少要
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 公共课 一等奖 全国 获奖 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。