第11章 特殊图.ppt

电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程离 散 数 学电子科技大学计算机科学与工程学院示 范 性 软 件 学 院02 02 三月三月 2023 2023电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-2 2第第1111章章 特殊图特殊图 偶图偶图3平面图平面图4欧拉图欧拉图1集合的表示方法集合的表示方法2哈密顿图哈密顿图2电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-3 311.0 11.0 内容提要内容提要 1.1.几几个个特特殊殊图图的的概概念念：欧欧拉拉图图、哈哈密密顿顿图图、偶偶图图、平面图；平面图；2.2.欧拉图、哈密顿图、偶图、平面图的判定；欧拉图、哈密顿图、偶图、平面图的判定；3.3.偶图的匹配、图的着色；偶图的匹配、图的着色；4.4.欧拉图、哈密顿图、偶图、平面图的应用欧拉图、哈密顿图、偶图、平面图的应用电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-4 410.1 10.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1 各个特殊图各个特殊图相关基本概念相关基本概念2 2 各个特殊图各个特殊图的性质的性质3 3 各个特殊图各个特殊图的判定方法的判定方法 31 1 各个特殊图各个特殊图的应用的应用2 2 图的着色图的着色21 1 哈密顿图、哈密顿图、平面图的判断平面图的判断2 2 证明方法证明方法 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-6 6定义定义11.2.111.2.1设设G G是是无无孤孤立立结结点点的的图图，若若存存在在一一条条通通路路(回回路路)，经经过过图图中中每每边边一一次次且且仅仅一一次次，则则称称此此通通路路(回回路路)为为该该 图图 的的 一一 条条 欧欧 拉拉 通通 路路(回回 路路)()(EulerianEulerian Entry/Circuit)Entry/Circuit)。具具有有欧欧拉拉回回路路的的图图称称为为欧欧拉拉图图(EulerianEulerian Graph)Graph)。规定：规定：平凡图为欧拉图。平凡图为欧拉图。以上定义既适合无向图，又适合有向图。以上定义既适合无向图，又适合有向图。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-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)欧拉图欧拉图 欧欧拉拉图图 不是欧拉图，但不是欧拉图，但存在欧拉通路存在欧拉通路 不存在欧不存在欧拉通路拉通路 不不存存在在欧欧拉拉通通路路 不是欧拉图，但存在欧拉通路不是欧拉图，但存在欧拉通路 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-9 911.2.2 11.2.2 欧拉图的判定欧拉图的判定 定定理理11.2.111.2.1 无无向向图图G G=V,E具具有有一一条条欧欧拉拉通通路路，当当且且仅仅当当G G是是连连通通的的，且且仅仅有有零零个个或或两两个个奇奇度度数数结结点。点。分分析析 只只要要找找到到了了，就就是是存存在在的的。我我们们具具体体找找一一条条欧拉通路。对于结点的度数，我们在通路中去计算。欧拉通路。对于结点的度数，我们在通路中去计算。证证明明 若若G G为为平平凡凡图图，则则定定理理显显然然成成立立。故故我我们们下下面讨论的均为非平凡图。面讨论的均为非平凡图。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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无度数为奇数的结点。无度数为奇数的结点。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-1212充分性：构造性证明。充分性：构造性证明。我我们们从从两两个个奇奇度度数数结结点点之之一一开开始始(若若无无奇奇度度数数结结点点，可可从从任任一一结结点点开开始始)构构造造一一条条欧欧拉拉通通路路，以以每每条条边边最最多多经经过过一一次次的的方方式式通通过过图图中中的的边边。对对于于度度数数为为偶偶数数的的结结点点，通通过过一一条条边边进进入入这这个个结结点点，总总可可以以通通过过一一条条未未经经过过的的边边离离开开这这个个结结点点，因因此此，这这样样的的构构造造过过程程一一定定以以到到达达另另一一个个奇奇度度数数结结点点而而告告终终(若若无无奇奇度度数数结结点点，则则以以回回到到原原出出发发点点而而告告终终)。如如果果图图中中所所有有的的边边已已用用这这种种方方式式经经过过了了，显显然然这这就就是是所所求求的的欧欧拉拉通通路路。如如果果图图中中不不是是所所有有的的边边都都经经过过了了，我我们们去去掉掉已已经经过过的的边边，得得到到一一个个由由剩剩余余的的边边组组成成的的子图，这个子图的所有结点的度数均为偶数。子图，这个子图的所有结点的度数均为偶数。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-1313因因为为原原来来的的图图是是连连通通的的，因因此此，这这个个子子图图必必与与我我们们已已经经过过的的通通路路在在一一个个或或多多个个结结点点相相接接。从从这这些些结结点点中中的的一一个个开开始始，我我们们再再通通过过边边构构造造通通路路，因因为为结结点点的的度度数数全全是是偶偶数数，因因此此，这这条条通通路路一一定定最最终终回回到到起起点点。我我们们将将这这条条回回路路加加到到已已构构造造好好的的通通路路中中间间组组合合成成一一条条通通路路。如如有有必必要要，这这一一过过程程重重复复下下去去，直直到到我们得到一条通过图中所有边的通路，即欧拉通路。我们得到一条通过图中所有边的通路，即欧拉通路。由由定定理理11.2.111.2.1的的证证明明知知：若若连连通通的的无无向向图图有有两两个奇度数结点，则它们是个奇度数结点，则它们是G G中每条欧拉通路的端点中每条欧拉通路的端点。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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是连通的，且所有结点的入度等于出度。是连通的，且所有结点的入度等于出度。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-1515欧拉通路与欧拉回路判别准则欧拉通路与欧拉回路判别准则 对对任任意意给给定定的的无无向向连连通通图图，只只需需通通过过对对图图中中各各结结点点度度数数的的计计算算，就就可可知知它它是是否否存存在在欧欧拉拉通通路路及及欧欧拉拉回回路路，从从而而知知道道它它是是否否为为欧欧拉拉图图；对对任任意意给给定定的的有有向向连连通通图图，只只需需通通过过对对图图中中各各结结点点出出度度与与入入度度的的计计算算，就就可可知知它它是是否否存存在在欧欧拉拉通通路路及及欧欧拉拉回回路路，从从而知道它是否为欧拉图。而知道它是否为欧拉图。利利用用这这项项准准则则，很很容容易易判判断断出出哥哥尼尼斯斯堡堡七七桥桥问问题题是是无无解解的的，因因为为它它所所对对应应的的图图中中所所有有4 4个个结结点点的的度数均为奇数；也很容易得到例度数均为奇数；也很容易得到例11.2.111.2.1的结论。的结论。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-1616定义定义11.2.211.2.2设设G=G=，eEeE，如果，如果p(G-ep(G-e)p(Gp(G)称称e e为为G G的的桥桥(Bridge)(Bridge)或或割边割边(Cut edge)(Cut edge)。显然，显然，所有的悬挂边都是桥所有的悬挂边都是桥。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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-e=G-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)。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-191911.2.3 11.2.3 欧拉图的难点欧拉图的难点 1.1.仅有欧拉通路而无欧拉回路的图不是欧拉图；仅有欧拉通路而无欧拉回路的图不是欧拉图；2.2.图图中中是是否否存存在在欧欧拉拉通通路路、欧欧拉拉回回路路图图的的判判定定非非常简单，只需要数一下图中结点的度数即可；常简单，只需要数一下图中结点的度数即可；3.3.使使用用FleuryFleury算算法法求求欧欧拉拉通通路路(回回路路)时时，每每次次走走一条边，在可能的情况下，不走桥。一条边，在可能的情况下，不走桥。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-202011.2.4 11.2.4 欧拉图的应用欧拉图的应用 1 1、一笔画问题、一笔画问题 所所谓谓“一一笔笔画画问问题题”就就是是画画一一个个图图形形，笔笔不不离离纸，每条边只画一次而不许重复，画完该图。纸，每条边只画一次而不许重复，画完该图。“一一笔笔画画问问题题”本本质质上上就就是是一一个个无无向向图图是是否否存存在在欧欧拉拉通通路路(回回路路)的的问问题题。如如果果该该图图为为欧欧拉拉图图，则则能能够够一一笔笔画画完完该该图图，并并且且笔笔又又回回到到出出发发点点；如如果果该该图图只只存存在在欧欧拉拉通通路路，则则能能够够一一笔笔画画完完该该图图，但但笔笔回回不不到到出出发发点点；如如果果该该图图中中不不存存在在欧欧拉拉通通路路，则则不不能能一笔画完该图。一笔画完该图。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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的的结结点点，所所以不存在欧拉通路，因此不能一笔画。以不存在欧拉通路，因此不能一笔画。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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，所以乙必胜。，所以乙必胜。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-23233 3、计算机鼓轮设计、计算机鼓轮设计 假假设设一一个个旋旋转转鼓鼓的的表表面面被被等等分分为为2424个个部部分分，如如图图所所示示，其其中中每每一一部部分分分分别别由由导导体体或或绝绝缘缘体体构构成成，图图中中阴阴影影部部分分表表示示导导体体，空空白白部部分分表表示示绝绝缘缘体体，导导体体部部分分给给出出信信号号1 1，绝绝缘缘体体部部分分给给出出信信号号0 0。根据鼓轮转动时所处的位置，根据鼓轮转动时所处的位置，四四个个触触头头A A、B B、C C、D D将将获获得得一一定定的的信信息息。因因此此，鼓鼓轮轮的的位位置置可可用用二二进进制制信信号号表表示示。试试问问如如何何选选取取鼓鼓轮轮1616个个部部分分的的材材料料才才能能使使鼓鼓轮轮每每转转过过一一个个部部分分得得到到一一个个不不同同的的二二进进制制信信号号，即每转一周，能得到即每转一周，能得到00000000到到11111111的的1616个数。个数。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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这这个个四四位二进制数，作出的所有可能的码变换的有向图。位二进制数，作出的所有可能的码变换的有向图。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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，把把这这个个序序列列排排成成一一个个圆圆圈圈，与与所求的鼓轮相对应，就得到鼓轮的设计。所求的鼓轮相对应，就得到鼓轮的设计。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-2727推广推广 存存在在一一个个2 2n n个个二二进进制制数数的的循循环环序序列列，其其中中2 2n n个个由由n n位二进制数组成的子序列全不相同。位二进制数组成的子序列全不相同。将将上上述述2 2n n个个二二进进制制数数的的循循环环序序列列称称为为布布鲁鲁因因(De(De BrujinBrujin)序列。序列。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-282811.3 11.3 哈密顿图哈密顿图 11.2.1 11.2.1 哈密顿的引入与定义哈密顿的引入与定义 1 12 23 34 45 56 67 720208 89 91010111112121313141415151616171718181919电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-2929哈密顿图哈密顿图定定义义11.3.111.3.1 经经过过图图中中每每个个结结点点一一次次且且仅仅一一次次的的通通路路(回回路路)称称为为哈哈密密顿顿通通路路(回回路路)(Hamiltonian)(Hamiltonian Entry/circuit)Entry/circuit)。存存在在哈哈密密顿顿回回路路的的图图称称为为哈哈密密顿顿图图(Hamiltonian Graph)(Hamiltonian Graph)。规定：规定：平凡图为哈密顿图平凡图为哈密顿图。以上定义既适合无向图，又适合有向图。以上定义既适合无向图，又适合有向图。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-3030哈密顿通路和哈密顿回路的特征哈密顿通路和哈密顿回路的特征n哈哈密密顿顿通通路路是是经经过过图图中中所所有有结结点点的的通通路路中中长长度度最最短的通路，即为通过图中所有结点的基本通路；短的通路，即为通过图中所有结点的基本通路；n哈哈密密顿顿回回路路是是经经过过图图中中所所有有结结点点的的回回路路中中长长度度最最短的回路，即为通过图中所有结点的基本回路。短的回路，即为通过图中所有结点的基本回路。n如果我们仅用结点来描述的话如果我们仅用结点来描述的话n哈密顿通路就是图中所有结点的一种全排列哈密顿通路就是图中所有结点的一种全排列n哈哈密密顿顿回回路路就就是是图图中中所所有有结结点点的的一一种种全全排排列列再再加加上该排列中第一个结点的一种排列。上该排列中第一个结点的一种排列。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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)哈密哈密顿图顿图 不存不存在哈在哈密顿密顿通路通路 不是哈密不是哈密顿图，但顿图，但存在哈密存在哈密顿通路顿通路 哈密哈密顿图顿图 不是哈密不是哈密顿图，但顿图，但存在哈密存在哈密顿通路顿通路 不存不存在哈在哈密顿密顿通路通路 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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-V p(C-V1 1)，故只需要证明，故只需要证明p(C-Vp(C-V1 1)|V)|V1 1|即可。即可。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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 1|V|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|电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-3636定理定理11.3.211.3.2设设G G=V,E是是具具有有n n个个结结点点的的简简单单无无向向图图。如如果果对对任任意两个不相邻的结点意两个不相邻的结点u,u,vVvV，均有，均有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是连通的。是连通的。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-3737定理定理11.3.2 11.3.2 证明证明(续续)其次，证明其次，证明G G中存在哈密顿通路。中存在哈密顿通路。设设P P=v v1 1v v2 2v vk 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上所有结点的基本回路。上所有结点的基本回路。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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中删除边