离散数学省公共课一等奖全国赛课获奖课件.pptx

电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程离 散 数 学电子科技大学计算机科学与工程学院示 范 性 软 件 学 院10 十月 第1页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-2 2第第1111章章 特殊图特殊图 偶图偶图3平面图平面图4欧拉图欧拉图1集合表示方法集合表示方法2哈密顿图哈密顿图2第2页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-3 311.0 11.0 内容提要内容提要 1.1.几几个个特特殊殊图图概概念念：欧欧拉拉图图、哈哈密密顿顿图图、偶偶图图、平面图；平面图；2.2.欧拉图、哈密顿图、偶图、平面图判定；欧拉图、哈密顿图、偶图、平面图判定；3.3.偶图匹配、图着色；偶图匹配、图着色；4.4.欧拉图、哈密顿图、偶图、平面图应用欧拉图、哈密顿图、偶图、平面图应用第3页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-4 410.1 10.1 本章学习要求本章学习要求重点掌握重点掌握普通掌握普通掌握了解了解11 1 各个特殊图各个特殊图相关基本概念相关基本概念2 2 各个特殊图各个特殊图性质性质3 3 各个特殊图各个特殊图判定方法判定方法 31 1 各个特殊图各个特殊图应用应用2 2 图着色图着色21 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定义定义11.2.111.2.1设设G G是是无无孤孤立立结结点点图图，若若存存在在一一条条通通路路(回回路路)，经经过过图图中中每每边边一一次次且且仅仅一一次次，则则称称此此通通路路(回回路路)为为该该图图一一条条欧欧拉拉通通路路(回回路路)(Eulerian)(Eulerian Entry/Circuit)Entry/Circuit)。含有欧拉回路图称为含有欧拉回路图称为欧拉图欧拉图(Eulerian Graph)(Eulerian Graph)。要求：要求：平凡图为欧拉图。平凡图为欧拉图。以上定义既适合无向图，又适合有向图。以上定义既适合无向图，又适合有向图。第6页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-7 7欧拉通路和欧拉回路特征欧拉通路和欧拉回路特征 欧欧拉拉通通路路是是经经过过图图中中全全部部边边通通路路中中长长度度最最短短通通路路，即为，即为经过图中全部边简单通路经过图中全部边简单通路；欧欧拉拉回回路路是是经经过过图图中中全全部部边边回回路路中中长长度度最最短短回回路路，即为，即为经过图中全部边简单回路经过图中全部边简单回路。假假如如仅仅用用边边来来描描述述，欧欧拉拉通通路路和和欧欧拉拉回回路路就就是是图中全部边一个全排列图中全部边一个全排列。第7页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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)欧拉图欧拉图 欧欧拉拉图图 不是欧拉图，但不是欧拉图，但存在欧拉通路存在欧拉通路 不存在欧不存在欧拉通路拉通路 不不存存在在欧欧拉拉通通路路 不是欧拉图，但存在欧拉通路不是欧拉图，但存在欧拉通路 第8页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-9 911.2.2 11.2.2 欧拉图判定欧拉图判定 定定理理11.2.111.2.1 无无向向图图G G=V,E含含有有一一条条欧欧拉拉通通路路，当且仅当当且仅当G G是连通，且仅有零个或两个奇度数结点。是连通，且仅有零个或两个奇度数结点。分分析析 只只要要找找到到了了，就就是是存存在在。我我们们详详细细找找一一条条欧欧拉通路。对于结点度数，我们在通路中去计算。拉通路。对于结点度数，我们在通路中去计算。证证实实 若若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中中每每出出现现 一一次次，都都关关联联两两条条边边 和和 ，而而当当 重重复复出出现现时时，它它又又关关联联另另外外两两条条边边，因因为为在在通通路路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有两个度数为奇数结点。有两个度数为奇数结点。若若端端点点 =，设设在在通通路路中中作作为为非非端端点点出出现现p3p3次次，则则deg()=1+2p3+1=2(p3+1)deg()=1+2p3+1=2(p3+1)因而因而G G无度数为奇数结点。无度数为奇数结点。第11页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-1212充分性：结构性证实。充分性：结构性证实。我我们们从从两两个个奇奇度度数数结结点点之之一一开开始始(若若无无奇奇度度数数结结点点，可可从从任任一一结结点点开开始始)结结构构一一条条欧欧拉拉通通路路，以以每每条条边边最最多多经经过过一一次次方方式式经经过过图图中中边边。对对于于度度数数为为偶偶数数结结点点，经经过过一一条条边边进进入入这这个个结结点点，总总能能够够经经过过一一条条未未经经过过边边离离开开这这个个结结点点，所所以以，这这么么结结构构过过程程一一定定以以抵抵达达另另一一个个奇奇度度数数结结点点而而告告终终(若若无无奇奇度度数数结结点点，则则以以回回到到原原出出发发点点而而告告终终)。假假如如图图中中全全部部边边已已用用这这种种方方式式经经过过了了，显显然然这这就就是是所所求求欧欧拉拉通通路路。假假如如图图中中不不是是全全部部边边都都经经过过了了，我我们们去去掉掉已已经经过过边边，得得到到一一个个由由剩剩下下边边组组成成子子图图，这这个个子子图图全全部部结结点点度度数均为偶数。数均为偶数。第12页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-1313因因为为原原来来图图是是连连通通，所所以以，这这个个子子图图必必与与我我们们已已经经过过通通路路在在一一个个或或多多个个结结点点相相接接。从从这这些些结结点点中中一一个个开开始始，我我们们再再经经过过边边结结构构通通路路，因因为为结结点点度度数数全全是是偶偶数数，所所以以，这这条条通通路路一一定定最最终终回回到到起起点点。我我们们将将这这条条回回路路加加到到已已结结构构好好通通路路中中间间组组合合成成一一条条通通路路。如如有有必必要要，这这一一过过程程重重复复下下去去，直直到到我我们们得得到到一一条条经过图中全部边通路，即欧拉通路。经过图中全部边通路，即欧拉通路。由由定定理理11.2.111.2.1证证实实知知：若若连连通通无无向向图图有有两两个个奇奇度数结点，则它们是度数结点，则它们是G G中每条欧拉通路端点中每条欧拉通路端点。第13页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-1414结论结论推推论论11.2.111.2.1 无无向向图图G G=V,E含含有有一一条条欧欧拉拉回回路路，当且仅当当且仅当G G是连通，而且全部结点度数均为偶数。是连通，而且全部结点度数均为偶数。定定理理11.2.211.2.2 有有向向图图G G含含有有一一条条欧欧拉拉通通路路，当当且且仅仅当当G G是是连连通通，且且除除了了两两个个结结点点以以外外，其其余余结结点点入入度度等等于于出出度度，而而这这两两个个例例外外结结点点中中，一一个个结结点点入入度度比比出出度大度大1 1，另一个结点出度比入度大，另一个结点出度比入度大1 1。推推论论11.2.211.2.2 有有向向图图G G含含有有一一条条欧欧拉拉回回路路，当当且且仅仅当当G G是连通，且全部结点入度等于出度。是连通，且全部结点入度等于出度。第14页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-1515欧拉通路与欧拉回路判别准则欧拉通路与欧拉回路判别准则 对对任任意意给给定定无无向向连连通通图图，只只需需经经过过对对图图中中各各结结点点度度数数计计算算，就就可可知知它它是是否否存存在在欧欧拉拉通通路路及及欧欧拉拉回回路路，从从而而知知道道它它是是否否为为欧欧拉拉图图；对对任任意意给给定定有有向向连连通通图图，只只需需经经过过对对图图中中各各结结点点出出度度与与入入度度计计算算，就就可可知知它它是是否否存存在在欧欧拉拉通通路路及及欧欧拉拉回回路路，从从而而知知道道它它是否为欧拉图。是否为欧拉图。利利用用这这项项准准则则，很很轻轻易易判判断断出出哥哥尼尼斯斯堡堡七七桥桥问问题题是是无无解解，因因为为它它所所对对应应图图中中全全部部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页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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 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 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-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页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-191911.2.3 11.2.3 欧拉图难点欧拉图难点 1.1.仅有欧拉通路而无欧拉回路图不是欧拉图；仅有欧拉通路而无欧拉回路图不是欧拉图；2.2.图图中中是是否否存存在在欧欧拉拉通通路路、欧欧拉拉回回路路图图判判定定非非常常简单，只需要数一下列图中结点度数即可；简单，只需要数一下列图中结点度数即可；3.3.使使用用FleuryFleury算算法法求求欧欧拉拉通通路路(回回路路)时时，每每次次走走一条边，在可能情况下，不走桥。一条边，在可能情况下，不走桥。第19页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-202011.2.4 11.2.4 欧拉图应用欧拉图应用 1 1、一笔画问题、一笔画问题 所所谓谓“一一笔笔画画问问题题”就就是是画画一一个个图图形形，笔笔不不离离纸，每条边只画一次而不许重复，画完该图。纸，每条边只画一次而不许重复，画完该图。“一一笔笔画画问问题题”本本质质上上就就是是一一个个无无向向图图是是否否存存在在欧欧拉拉通通路路(回回路路)问问题题。假假如如该该图图为为欧欧拉拉图图，则则能能够够一一笔笔画画完完该该图图，而而且且笔笔又又回回到到出出发发点点；假假如如该该图图只只存存在在欧欧拉拉通通路路，则则能能够够一一笔笔画画完完该该图图，但但笔笔回回不不到到出出发发点点；假假如如该该图图中中不不存存在在欧欧拉拉通通路路，则则不不能能一一笔画完该图。笔画完该图。第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个个奇奇度度数数结结点点，所所以以它它们们分分别别是是欧欧拉拉图图和和存存在在欧欧拉拉通通路路，所所以以能能够够一一笔笔画画，而而且且在在(a)(a)中中笔笔能能回回到到出出发发点点，而而(b)(b)中中笔笔不不能能回回到到出出发发点点。图图c c中中有有4 4个个度度数数为为3 3结结点点，所所以以不存在欧拉通路，所以不能一笔画。不存在欧拉通路，所以不能一笔画。第21页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-22222 2、蚂蚁比赛问题、蚂蚁比赛问题 例例11.2.411.2.4 甲甲、乙乙两两只只蚂蚂蚁蚁分分别别位位于于图图结结点点A A、B B处处，并并设设图图中中边边长长度度相相等等。甲甲、乙乙进进行行比比赛赛：从从它它们们所所在在结结点点出出发发，走走过过图图中中全全部部边边最最终终抵抵达达结结点点C C处处。假假如如它它们们速速度度相相同同，问问谁先抵达目标地？谁先抵达目标地？A(甲)B(乙)C解解 图图中中仅仅有有两两个个度度数数为为奇奇数数结结点点B B、C C，因因而而存存在在从从B B到到C C欧欧拉拉通通路路，蚂蚂蚁蚁乙乙走走到到C C只只要要走走一一条条欧欧拉拉通通路路，边边数数为为9 9条条，而而蚂蚂蚁蚁甲甲要要想想走走完完全全部部边边抵抵达达C C，最最少少要要先先走走一一条条边边抵抵达达B B，再再走走一一条条欧欧拉拉通通路路，因因而而它它最最少少要要走走1010条边才能抵达条边才能抵达C C，所以乙必胜。，所以乙必胜。第22页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-23233 3、计算机鼓轮设计、计算机鼓轮设计 假假设设一一个个旋旋转转鼓鼓表表面面被被等等分分为为2424个个部部分分，如如图图所所表表示示，其其中中每每一一部部分分分分别别由由导导体体或或绝绝缘缘体体组组成成，图图中中阴阴影影部部分分表表示示导导体体，空空白白部部分分表表示示绝绝缘缘体体，导导体体部部分分给给出出信信号号1 1，绝绝缘缘体体部部分分给给出出信信号号0 0。依据鼓轮转动时所处位置，依据鼓轮转动时所处位置，四四个个触触头头A A、B B、C C、D D将将取取得得一一定定信信息息。所所以以，鼓鼓轮轮位位置置可可用用二二进进制制信信号号表表示示。试试问问怎怎样样选选取取鼓鼓轮轮1616个个部部分分材材料料才才能能使使鼓鼓轮轮每每转转过过一一个个部部分分得得到到一一个个不不一一样样二二进进制制信信号号，即即每每转一周，能得到转一周，能得到00000000到到111111111616个数。个数。第23页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-2424问题等价描述与处理方法问题等价描述与处理方法 问问题题等等价价描描述述：把把1616个个二二进进制制数数排排成成一一个个圆圆圈圈，使使得得四四个个依依次次相相连连数数字字所所组组成成1616个个四四位位二二进进制制数数互互不相同。不相同。问问题题处处理理思思想想：设设a ai i0,1(i=0,1(i=1,2,3,1,2,3,16)16)，鼓鼓轮轮每每转转一一个个部部分分，信信号号就就从从a a1 1a a2 2a a3 3a a4 4变变为为a a2 2a a3 3a a4 4a a5 5，前者右三位决定了后者左三位。，前者右三位决定了后者左三位。我我们们可可把把全全部部三三位位二二进进制制数数作作为为结结点点，从从每每个个结结点点a a1 1a a2 2a a3 3到到a a2 2a a3 3a a4 4连连一一条条有有向向边边表表示示a a1 1a a2 2a a3 3a a4 4这这个个四四位二进制数，作出全部可能码变换有向图。位二进制数，作出全部可能码变换有向图。第24页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-2525全部可能码变换有向图全部可能码变换有向图e e0 000000000e e8 810001000e e1 100010001e e9 910011001e e2 200100010e e101010101010e e3 300110011e e111110111011e e4 401000100e e121211001100e e5 501010101e e131311011101e e6 601100110e e141411101110e e7 701110111e e151511111111000000001001100100101101111111010010011011110110e e0 0e e1 1e e2 2e e3 3e e7 7e e1414e e1212e e8 8e e9 9e e4 4e e5 5e e1010e e1111e e1313e e6 6e e1515第25页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-2626问题求解问题求解 问题转化为在这个有向图中找一条欧拉回路。问题转化为在这个有向图中找一条欧拉回路。这这个个有有向向图图中中8 8个个结结点点出出度度和和入入度度都都是是2 2，所所以以存在欧拉回路。存在欧拉回路。比比 如如 e e0 0e e1 1e e2 2e e4 4e e9 9e e3 3e e6 6e e1313e e1010e e5 5e e1111e e7 7e e1515e e1414e e1212e e8 8就就 是是一一条条欧欧拉拉回回路路。依依据据邻邻接接边边标标号号记记法法，这这1616个个二二进进制制数数可可写写成成对对应应二二进进制制序序列列00001001101011110000100110101111，把把这这个个序序列列排排成成一一个个圆圆圈圈，与与所所求求鼓鼓轮轮相相对对应应，就就得得到鼓轮设计。到鼓轮设计。第26页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-2727推广推广 存存在在一一个个2 2n n个个二二进进制制数数循循环环序序列列，其其中中2 2n n个个由由n n位二进制数组成子序列全不相同。位二进制数组成子序列全不相同。将将上上述述2 2n n个个二二进进制制数数循循环环序序列列称称为为布布鲁鲁因因(De(De Brujin)Brujin)序列。序列。第27页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-282811.3 11.3 哈密顿图哈密顿图 11.2.1 11.2.1 哈密顿引入与定义哈密顿引入与定义 1 12 23 34 45 56 67 720208 89 91010111112121313141415151616171718181919第28页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-2929哈密顿图哈密顿图定定义义11.3.111.3.1 经经过过图图中中每每个个结结点点一一次次且且仅仅一一次次通通路路(回回 路路)称称 为为 哈哈 密密 顿顿 通通 路路(回回 路路)(Hamiltonian)(Hamiltonian Entry/circuit)Entry/circuit)。存存在在哈哈密密顿顿回回路路图图称称为为哈哈密密顿顿图图(Hamiltonian Graph)(Hamiltonian Graph)。要求：要求：平凡图为哈密顿图平凡图为哈密顿图。以上定义既适合无向图，又适合有向图。以上定义既适合无向图，又适合有向图。第29页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-3030哈密顿通路和哈密顿回路特征哈密顿通路和哈密顿回路特征哈哈密密顿顿通通路路是是经经过过图图中中全全部部结结点点通通路路中中长长度度最最短短通路，即为经过图中全部结点基本通路；通路，即为经过图中全部结点基本通路；哈哈密密顿顿回回路路是是经经过过图图中中全全部部结结点点回回路路中中长长度度最最短短回路，即为经过图中全部结点基本回路。回路，即为经过图中全部结点基本回路。假如我们仅用结点来描述话假如我们仅用结点来描述话哈密顿通路就是图中全部结点一个全排列哈密顿通路就是图中全部结点一个全排列哈哈密密顿顿回回路路就就是是图图中中全全部部结结点点一一个个全全排排列列再再加加上上该排列中第一个结点一个排列。该排列中第一个结点一个排列。第30页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-3131例例11.3.111.3.1判判断断下下面面6 6个个图图中中，是是否否是是哈哈密密顿顿图图？是是否否存存在在哈哈密顿通路？密顿通路？v v3 3v v1 1v v2 2v v4 4(a(a)v v3 3v v1 1v v2 2v v4 4(d(d)v v3 3v v1 1v v2 2v v4 4(b(b)v v5 5v v6 6v v7 7v v2 2v v4 4v v1 1v v5 5(c(c)v v3 3v v3 3v v1 1v v2 2v v4 4(e(e)v v3 3v v1 1v v2 2v v4 4(f(f)哈密哈密顿图顿图 不存不存在哈在哈密顿密顿通路通路 不是哈密不是哈密顿图，但顿图，但存在哈密存在哈密顿通路顿通路 哈密哈密顿图顿图 不是哈密不是哈密顿图，但顿图，但存在哈密存在哈密顿通路顿通路 不存不存在哈在哈密顿密顿通路通路 第31页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-323211.3.2 11.3.2 哈密顿图判定哈密顿图判定 定定理理11.3.111.3.1 设设无无向向图图G G=V,E是是哈哈密密顿顿图图，V V1 1是是V V任意非空子集，则任意非空子集，则p(G-Vp(G-V1 1)|V)|V1 1|其中其中p(G-Vp(G-V1 1)是从是从G G中删除中删除V V1 1后所得到图连通分支数。后所得到图连通分支数。分分析析 考考查查G G一一条条哈哈密密顿顿回回路路C C，显显然然C C是是G G生生成成子子图图，从从而而C-VC-V1 1也也是是G-VG-V1 1生生成成子子图图，且且有有p(G-Vp(G-V1 1)p(C-p(C-V V1 1)，故只需要证实，故只需要证实p(C-Vp(C-V1 1)|V)|V1 1|即可。即可。第32页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-3333定理定理11.3.1 11.3.1 证实证实设设C C是是G G中中一一条条哈哈密密顿顿回回路路，V V1 1是是V V任任意意非非空空子子集集。下下面面分分两两种种情况讨论：情况讨论：（1 1）V V1 1中中结结点点在在C C中中均均相相邻邻，删删除除C C上上V V1 1中中各各结结点点及及关关联联边边后后，C-VC-V1 1仍是连通，但已非回路，所以仍是连通，但已非回路，所以p(C-Vp(C-V1 1)=1|V)=1|V1 1|。（2 2）V V1 1中中结结点点在在C C上上存存在在r(2 r(2 r r|V1|)|V1|)个个互互不不相相邻邻，删删除除C C上上V V1 1中各结点及关联边后，将中各结点及关联边后，将C C分为互不相连分为互不相连r r段，即段，即p(C-Vp(C-V1 1)=r|V)=r|V1 1|。普普通通情情况况下下，V1V1中中结结点点在在C C中中即即有有相相邻邻，又又有有不不相相邻邻，所所以以总总有有p(C-Vp(C-V1 1)|V)|V1 1|。又因又因C C是是G G生成子图，从而生成子图，从而C-V1C-V1也是也是G-V1G-V1生成子图，故有生成子图，故有p(G-Vp(G-V1 1)p(C-V)p(C-V1 1)|V)|V1 1|第33页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-3434推论推论11.3.111.3.1设设无无向向图图G G=V,E中中存存在在哈哈密密顿顿通通路路，则则对对V V任任意非空子集意非空子集V V1 1，都有，都有p(G-Vp(G-V1 1)|V)|V1 1|+1|+1 注意：注意：定理定理11.3.111.3.1给出是哈密给出是哈密顿图必要条件，而不是顿图必要条件，而不是充分条件。充分条件。定定理理11.3.111.3.1在在应应用用中中它它本本身身用用处处不不大大，但但它它逆逆否否命命题题却却非非常常有有用用。我我们们经经常常利利用用定定理理11.3.111.3.1逆逆否否命命题题来来判判断断一一些些图图不不是是哈哈密密顿顿图图，即即：若若存存在在V V某某个个非非空空子子集集V V1 1使使得得p(G-Vp(G-V1 1)|V|V1 1|，则则G G不不是是哈哈密密顿图。顿图。v v3 3v v1 1v v2 2v v4 4v v5 5v v6 6v v7 7v v2 2v v4 4v v1 1v v5 5v v3 3第34页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-3535例例11.3.211.3.2证实图中不存在哈密顿回路。证实图中不存在哈密顿回路。a ab bc cg gi ih h分分析析 利利用用定定理理11.3.111.3.1逆逆否否命命题题，寻寻找找V V某某个个非非空空子子集集V V1 1使使得得p(G-Vp(G-V1 1)|V|V1 1|，则则G G不不是是哈哈密密顿顿图图。找找到到V V1 1 =d,d,e,e,f f满满足足要求。要求。证证实实 在在图图中中，删删除除结结点点子子集集d,d,e,e,f f，得得新新图图，它它连连通通分分支支为为4 4个个，由由定定理理11.3.111.3.1知知，该该图图不不是是哈哈密密顿顿图图，因因而而不不会会存存在哈密顿回路。在哈密顿回路。d df fe ea ab bc cg gi ih h第35页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-3636定理定理11.3.211.3.2设设G G=V,E是是含含有有n n个个结结点点简简单单无无向向图图。假假如如对对任任意意两个不相邻结点两个不相邻结点u,vVu,vV，都有，都有deg(u)+deg(v)n-1deg(u)+deg(v)n-1则则G G中存在哈密顿通路。中存在哈密顿通路。证证实实 首首先先证证实实满满足足上上述述条条件件G G是是连连通通图图。用用反反证证法法：假假设设G G有有两两个个或或更更多多连连通通分分支支。设设一一个个连连通通分分支支有有n n1 1个个结结点点，另另一一个个连连通通分分支支有有n n2 2个个结结点点。这这二二个个连连通通分分支支中中分分别别有有两两个个结结点点v v1 1、v v2 2。显显然然，deg(vdeg(v1 1)n)n1 1-1-1，degdeg(v(v2 2)n)n2 2-1-1。从从而而deg(vdeg(v1 1)+deg(v)+deg(v2 2)n)n1 1+n+n2 2-2-2 n-2n-2与与已知矛盾，故已知矛盾，故G G是连通。是连通。第36页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-3737定理定理11.3.2 11.3.2 证实证实(续续)其次，证实其次，证实G G中存在哈密顿通路。中存在哈密顿通路。设设P P=v v1 1v v2 2vvk k为为G G中中用用“延延长长通通路路法法”得得到到“极极大大基基本本通通路路”，即即P P始始点点v v1 1与与终终点点v vk k不不与与P P外外结结点点相相邻邻，显然显然k nk n。（1 1）若若k k=n n，则则P P为为G G中中经经过过全全部部结结点点通通路路，即即为为哈密顿通路。哈密顿通路。（2 2）若若k kn n，说说明明G G中中还还有有在在P P外外结结点点，但但此此时时能能够够证证实实存存在在仅仅经经过过P P上上全全部部结结点点基基本本回回路路，证证实实以以下：下：（a a）若若在在P P上上v v1 1与与v vk k相相邻邻，则则v v1 1v v2 2vvk kv v1 1为为仅仅经经过过P P上全部结点基本回路。上全部结点基本回路。第37页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-3838定理定理11.3.2 11.3.2 证实证实(续续)（b b）若若在在P P上上v v1 1与与v vk k不不相相邻邻，假假设设v v1 1在在P P上上与与v vi i1 1=v v2 2,v,vi i2 2,v,vi i3 3,v,vi ij j相相邻邻(j(j必必定定大大于于等等于于2 2，不不然然degdeg(v(v1 1)+deg(v)+deg(vk k)1+k-2)1+k-2 n-1)n-1)，此此 时时 v vk k必必 与与v vi i2 2,v,vi i3 3,v,vi ij j相相邻邻结结点点v vi i2 2-1-1,v,vi i3 3-1-1,v,vi ij j-1-1最最少少之之一一相相邻邻(不不然然deg(vdeg(v1 1)+deg(vdeg(vk k)j+k-2-(j-1)j+k-2-(j-1)=k-1k-1n-1)n-1)。设设v vk k与与v vi ir r-1-1(2rj)(2rj)相相邻邻，如如图图所所表表示示。在在P P中中添添加加边边(v(v1 1,v,vi ir r)、(v(vk k,v,vi ir r-1-1)，删删除除边边(v(vi ir r-1 1,v,vi ir r)得基本回路得基本回路C=vC=v1 1v v2 2vvi ir r-1-1v vk kv vk-1k-1vvi ir rv v1 1。v v1 1v vi ir r-1-1v vi ir rv vk k(a)(a)v v1 1v vk k(b)(b)v vk+1k+1v vt t第38页电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-3939定理定理11.3.2 11.3.2 证实证实(续续)（3 3）证实存在比）证实存在比P P更长通路。更长通路。因为因为k kn n，所以，所以V V中还有一些结点不在中还有一些结点不在C C中，由中，由G G连连通性知，存在通性知，存在C C外结点与外结点与C C上结点相邻，不妨设上结点相邻，不妨设v vk+1k+1V-V(C)V-V(C)且与且与C C上结点上结点v vt t相邻，在相邻，在C C中删除边中删除边(v(vt-t-1 1,v,vt t)而添加边而添加边(v(vt t,v,vk+1k+1)得到通路得到通路P=vP=vt-1t-1vv1 1v vi ir rvvk kv vi ir r-1-1vvt tv vk+1k+1。显然，。显然，PP比比P P长长1 1，且，且PP上有上有k+1k+1个不一样结点。个不一样结点。对对PP重重复复(1)(1)(3)(3)，得得到到G G中中哈哈密密顿顿通通路路或或比比PP更更长长基基本本通通路路，因因为为G G中中结结点点数数目目有有限限，故故在在有有限限步内一定得到步内一定得到G