第11章特殊图专业课堂

1、电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程离离 散散 数数 学学电子科技大学电子科技大学计算机科学与工程学院计算机科学与工程学院示示 范范 性性 软软 件件 学学 院院20212021年年1010月月2828日星期四日星期四电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-2 2第第1111章章 特殊图特殊图 偶图偶图3平面图平面图4欧拉图欧拉图1集合的表示方法集合的表示方法2哈密顿图哈密顿图2电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-3 311.0 11.0 内容提要

2、内容提要 1.1. 几个特殊图的概念：欧拉图、哈密顿图、偶图、几个特殊图的概念：欧拉图、哈密顿图、偶图、平面图；平面图；2.2. 欧拉图、哈密顿图、偶图、平面图的判定；欧拉图、哈密顿图、偶图、平面图的判定；3.3. 偶图的匹配、图的着色；偶图的匹配、图的着色；4.4. 欧拉图、哈密顿图、偶图、平面图的应用欧拉图、哈密顿图、偶图、平面图的应用电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-4 410.1 10.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1 各个特殊图各个特殊图相关基本概念相关基本概念2 2 各个特殊图各个

3、特殊图的性质的性质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

4、4b b1 1b b3 3电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-6 6定义定义11.2.111.2.1设设g g是是无孤立结点的图无孤立结点的图，若存在一条通路，若存在一条通路( (回路回路) )，经过图中每边一次且仅一次经过图中每边一次且仅一次，则称此通路，则称此通路( (回路回路) )为为该 图 的 一 条该 图 的 一 条 欧 拉 通 路欧 拉 通 路 ( ( 回 路回 路 ) ( e u l e r i a n ) ( e u l e r i a n entry/circuit)entry/circuit)。具有欧拉回路的图称为。具

5、有欧拉回路的图称为欧拉图欧拉图(eulerian graph)(eulerian graph)。 规定：规定：平凡图为欧拉图。平凡图为欧拉图。 以上定义既适合无向图，又适合有向图。以上定义既适合无向图，又适合有向图。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-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 v

7、4 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 =

8、g = 具有一条欧拉通具有一条欧拉通路，当且仅当路，当且仅当g g是连通的，且仅有零个或两个奇度是连通的，且仅有零个或两个奇度数结点。数结点。分析分析 只要找到了，就是存在的。我们具体找一条只要找到了，就是存在的。我们具体找一条欧拉通路。对于结点的度数，我们在通路中去计算。欧拉通路。对于结点的度数，我们在通路中去计算。证明证明 若若g g为平凡图，则定理显然成立。故我们下为平凡图，则定理显然成立。故我们下面讨论的均为非平凡图。面讨论的均为非平凡图。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-1010必要性：必要性：设设g g具有一条欧拉通路具有一

9、条欧拉通路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次，则

10、次，则deg( )= 2pdeg( )= 2p。 0 01 11 12 2m m- -1 1m mm mi ij ji ij ji ij ji iv v e e v v e e . . . .v ve e v vk ki iv vk ki iv vk kj je e1 1 k kj je ek ki iv vk ki iv v电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-1111若端点若端点 ，设，设 、 在通路中作为非端点在通路中作为非端点分别出现分别出现p1p1和和p2p2次，则次，则deg( )= 2p1+1deg( )= 2p1+1，deg

11、( ) = 2p2+1deg( ) = 2p2+1因而因而g g有两个度数为奇数的结点。有两个度数为奇数的结点。若端点若端点 = = ，设在通路中作为非端点出现，设在通路中作为非端点出现p3p3次，次，则则deg( )= 1+2p3+1 = 2(p3+1)deg( )= 1+2p3+1 = 2(p3+1)因而因而g g无度数为奇数的结点。无度数为奇数的结点。0 0i iv vm mi iv v0 0i iv vm mi iv v0 0i iv vm mi iv v0 0i iv vm mi iv v0 0i iv v电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程1

12、10-110-1212充分性：构造性证明。充分性：构造性证明。 我们从两个奇度数结点之一开始我们从两个奇度数结点之一开始( (若无奇度数若无奇度数结点，可从任一结点开始结点，可从任一结点开始) )构造一条欧拉通路，以构造一条欧拉通路，以每条边最多经过一次的方式通过图中的边。对于度每条边最多经过一次的方式通过图中的边。对于度数为偶数的结点，通过一条边进入这个结点，总可数为偶数的结点，通过一条边进入这个结点，总可以通过一条未经过的边离开这个结点，因此，这样以通过一条未经过的边离开这个结点，因此，这样的构造过程一定以到达另一个奇度数结点而告终的构造过程一定以到达另一个奇度数结点而告终( (若无奇度数

13、结点，则以回到原出发点而告终若无奇度数结点，则以回到原出发点而告终) )。如。如果图中所有的边已用这种方式经过了，显然这就是果图中所有的边已用这种方式经过了，显然这就是所求的欧拉通路。如果图中不是所有的边都经过了，所求的欧拉通路。如果图中不是所有的边都经过了，我们去掉已经过的边，得到一个由剩余的边组成的我们去掉已经过的边，得到一个由剩余的边组成的子图，这个子图的所有结点的度数均为偶数。子图，这个子图的所有结点的度数均为偶数。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-1313因为原来的图是连通的，因此，这个子图必与我们因为原来的图是连通的，因此，

14、这个子图必与我们已经过的通路在一个或多个结点相接。从这些结点已经过的通路在一个或多个结点相接。从这些结点中的一个开始，我们再通过边构造通路，因为结点中的一个开始，我们再通过边构造通路，因为结点的度数全是偶数，因此，这条通路一定最终回到起的度数全是偶数，因此，这条通路一定最终回到起点。我们将这条回路加到已构造好的通路中间组合点。我们将这条回路加到已构造好的通路中间组合成一条通路。如有必要，这一过程重复下去，直到成一条通路。如有必要，这一过程重复下去，直到我们得到一条通过图中所有边的通路，即欧拉通路。我们得到一条通过图中所有边的通路，即欧拉通路。 由定理由定理11.2.111.2.1的证明知：的证

15、明知：若连通的无向图有两若连通的无向图有两个奇度数结点，则它们是个奇度数结点，则它们是g g中每条欧拉通路的端点中每条欧拉通路的端点。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-1414结论结论推论推论11.2.111.2.1 无向图无向图g = g = 具有一条欧拉回路，具有一条欧拉回路，当且仅当当且仅当g g是连通的，并且所有结点的度数均为偶是连通的，并且所有结点的度数均为偶数。数。定理定理11.2.211.2.2 有向图有向图g g具有一条欧拉通路，当且仅当具有一条欧拉通路，当且仅当g g是连通的，且除了两个结点以外，其余结点的入是连通的，

16、且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的度等于出度，而这两个例外的结点中，一个结点的入度比出度大入度比出度大1 1，另一个结点的出度比入度大，另一个结点的出度比入度大1 1。推论推论11.2.211.2.2 有向图有向图g g具有一条欧拉回路，当且仅具有一条欧拉回路，当且仅当当g g是连通的，且所有结点的入度等于出度。是连通的，且所有结点的入度等于出度。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-1515欧拉通路与欧拉回路判别准则欧拉通路与欧拉回路判别准则 对任意给定的无向连通图，只需通过对图中各对任意给定的

17、无向连通图，只需通过对图中各结点度数的计算，就可知它是否存在欧拉通路及欧结点度数的计算，就可知它是否存在欧拉通路及欧拉回路，从而知道它是否为欧拉图；对任意给定的拉回路，从而知道它是否为欧拉图；对任意给定的有向连通图，只需通过对图中各结点出度与入度的有向连通图，只需通过对图中各结点出度与入度的计算，就可知它是否存在欧拉通路及欧拉回路，从计算，就可知它是否存在欧拉通路及欧拉回路，从而知道它是否为欧拉图。而知道它是否为欧拉图。 利用这项准则，很容易判断出哥尼斯堡七桥问利用这项准则，很容易判断出哥尼斯堡七桥问题是无解的，因为它所对应的图中所有题是无解的，因为它所对应的图中所有4 4个结点的个结点的度数

18、均为奇数；也很容易得到例度数均为奇数；也很容易得到例11.2.111.2.1的结论。的结论。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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)。 显然，显然，所有的悬挂边都是桥所有的悬挂边都是桥。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-1717fleuryfleury

19、算法算法算法算法11.2.111.2.1 求欧拉图求欧拉图g = g = 的欧拉回路的的欧拉回路的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

20、 i 中的桥；中的桥；（ 3 3 ） 将 边） 将 边 e ei + 1i + 1加 入 通 路加 入 通 路 p p0 0中 ， 令中 ， 令 p p0 0 = = v v0 0e e1 1v v1 1e e2 2e ei 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算法求欧拉算法求欧拉图的一条欧拉回路。图的一条

21、欧拉回路。 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 5

22、e e5 5v v6 6e e6 6v v7 7e e7 7v v8 8时，时，g g = g-e = g-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

23、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算法求欧拉通路算法求欧拉通路( (回路回路) )时，每次走时，每次走一

24、条边，在可能的情况下，不走桥。一条边，在可能的情况下，不走桥。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-202011.2.4 11.2.4 欧拉图的应用欧拉图的应用 1 1、一笔画问题、一笔画问题 所谓所谓“一笔画问题一笔画问题”就是画一个图形，笔不离就是画一个图形，笔不离纸，每条边只画一次而不许重复，画完该图。纸，每条边只画一次而不许重复，画完该图。 “一笔画问题一笔画问题”本质上就是一个无向图是否存本质上就是一个无向图是否存在欧拉通路在欧拉通路( (回路回路) )的问题。如果该图为欧拉图，则的问题。如果该图为欧拉图，则能够一笔画完该图，并

25、且笔又回到出发点；如果该能够一笔画完该图，并且笔又回到出发点；如果该图只存在欧拉通路，则能够一笔画完该图，但笔回图只存在欧拉通路，则能够一笔画完该图，但笔回不到出发点；如果该图中不存在欧拉通路，则不能不到出发点；如果该图中不存在欧拉通路，则不能一笔画完该图。一笔画完该图。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程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

26、 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的结点，所的结点，所以不存在欧拉通路，因此不能一笔画。以不存在欧拉通路，因此不能一笔画。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程

27、国家精品课程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的欧拉通路，蚂蚁乙

28、走到的欧拉通路，蚂蚁乙走到c c只要走一条欧拉通只要走一条欧拉通路，边数为路，边数为9 9条，而蚂蚁甲要想走完所有的边到达条，而蚂蚁甲要想走完所有的边到达c c，至少要先走一条边到达至少要先走一条边到达b b，再走一条欧拉通路，因而，再走一条欧拉通路，因而它至少要走它至少要走1010条边才能到达条边才能到达c c，所以乙必胜。，所以乙必胜。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-23233 3、计算机鼓轮设计、计算机鼓轮设计 假设一个旋转鼓的表面被等假设一个旋转鼓的表面被等分为分为2424个部分，如图所示，其中个部分，如图所示，其中每一部分

29、分别由导体或绝缘体构每一部分分别由导体或绝缘体构成，图中阴影部分表示导体，空成，图中阴影部分表示导体，空白部分表示绝缘体，导体部分给白部分表示绝缘体，导体部分给出信号出信号1 1，绝缘体部分给出信号，绝缘体部分给出信号0 0。根据鼓轮转动时所处的位置，根据鼓轮转动时所处的位置，四个触头四个触头a a、b b、c c、d d将获得一定的信息。因此，鼓轮的位将获得一定的信息。因此，鼓轮的位置可用二进制信号表示。试问如何选取鼓轮置可用二进制信号表示。试问如何选取鼓轮1616个部分的材个部分的材料才能使鼓轮每转过一个部分得到一个不同的二进制信号，料才能使鼓轮每转过一个部分得到一个不同的二进制信号，即每

30、转一周，能得到即每转一周，能得到00000000到到11111111的的1616个数。个数。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-2424问题的等价描述与解决方法问题的等价描述与解决方法 问题的等价描述：问题的等价描述：把把1616个二进制数排成一个圆个二进制数排成一个圆圈，使得四个依次相连的数字所组成的圈，使得四个依次相连的数字所组成的1616个四位二个四位二进制数互不相同。进制数互不相同。 问题的解决思想：问题的解决思想：设设a ai i0,1(i= 1,2,3,0,1(i= 1,2,3, , 16)16)，鼓轮每转一个部分，信号就从，

31、鼓轮每转一个部分，信号就从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这个四这个四位二进制数，作出的所有可能的码变换的有向图。位二进制数，作出的所有可能的码变换的有向图。 电子科技大学离散数学课程组电子科技大学离散数学课程组国

32、家精品课程国家精品课程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 e15151111111100000000100110010010110

33、1111111010010011011110110e 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 0

34、e 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，把这个序列排成一个圆圈，与，把这个序列排成一个圆圈，与所求的鼓轮相对应，就得到鼓轮的设计。所求的鼓轮相对应，就得到鼓轮的设计。

35、电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-2727推广推广 存在一个存在一个2 2n n个二进制数的循环序列，其中个二进制数的循环序列，其中2 2n n个个由由n n位二进制数组成的子序列全不相同。位二进制数组成的子序列全不相同。 将上述将上述2 2n n个二进制数的循环序列称为个二进制数的循环序列称为布鲁因布鲁因(de brujin)(de brujin)序列。序列。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-282811.3 11.3 哈密顿图哈密顿图 11.2.1 11.2.1 哈密顿的引

36、入与定义哈密顿的引入与定义 1 12 23 34 45 56 67 720208 89 91010111112121313141415151616171718181919电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-2929哈密顿图哈密顿图定义定义11.3.111.3.1 经过图中经过图中每个结点一次且仅一次每个结点一次且仅一次的通的通路路( (回路回路) )称为称为哈密顿通路哈密顿通路( (回路回路)(hamiltonian )(hamiltonian entry/circuit)entry/circuit)。存在。存在哈密顿回路哈密顿回路的图称

37、为的图称为哈密顿哈密顿图图(hamiltonian graph)(hamiltonian graph)。 规定：规定：平凡图为哈密顿图平凡图为哈密顿图。 以上定义既适合无向图，又适合有向图。以上定义既适合无向图，又适合有向图。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-3030哈密顿通路和哈密顿回路的特征哈密顿通路和哈密顿回路的特征n 哈密顿通路是经过图中所有结点的通路中长度最哈密顿通路是经过图中所有结点的通路中长度最短的通路，即为通过图中所有结点的基本通路；短的通路，即为通过图中所有结点的基本通路；n 哈密顿回路是经过图中所有结点的回路中长度

38、最哈密顿回路是经过图中所有结点的回路中长度最短的回路，即为通过图中所有结点的基本回路。短的回路，即为通过图中所有结点的基本回路。n 如果我们仅用结点来描述的话如果我们仅用结点来描述的话n 哈密顿通路就是图中所有结点的一种全排列哈密顿通路就是图中所有结点的一种全排列n 哈密顿回路就是图中所有结点的一种全排列再加哈密顿回路就是图中所有结点的一种全排列再加上该排列中第一个结点的一种排列。上该排列中第一个结点的一种排列。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-3131例例11.3.111.3.1判断下面的判断下面的6 6个图中，是否是哈密顿图？是否存

39、在个图中，是否是哈密顿图？是否存在哈密顿通路？哈密顿通路？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)哈密哈密顿图顿图 不存不存在哈在哈密顿密顿通路通路 不是哈密不是哈密顿图，但顿图，但存在哈密存在哈密顿通路顿通路 哈密哈密顿图顿图 不

40、是哈密不是哈密顿图，但顿图，但存在哈密存在哈密顿通路顿通路 不存不存在哈在哈密顿密顿通路通路 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-323211.3.2 11.3.2 哈密顿图的判定哈密顿图的判定 定理定理11.3.111.3.1 设无向图设无向图g = g = 是哈密顿图，是哈密顿图，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

41、 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的任意非空子集。下面分的任意非空子

42、集。下面分两种情况讨论：两种情况讨论：（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 |v1|)r(2 r |v1|)个互不相邻，删个互不相邻，删除除c c上上v v1 1中各结点及关联的边后，将中各结点及关联的边后，将c c分为互不相连的分为互不相连的r r段，即段，即p(c-vp(c-v1

43、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

44、 = g = 中存在哈密顿通路，则对中存在哈密顿通路，则对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的逆否命题来判断的逆否命题来判断某些图不是哈密顿图，即：若存在某些图不是哈密顿图，即：若存

45、在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的

46、某的某个非空子集个非空子集v v1 1使得使得p(g-vp(g-v1 1) )|v|v1 1| |，则，则g g不是哈密顿不是哈密顿图。找到图。找到v v1 1 = = d, e, fd, e, f满足要求。满足要求。证明证明 在图中，删除结在图中，删除结点子集点子集d, e, fd, e, f，得，得新图，它的连通分支为新图，它的连通分支为4 4个，由定理个，由定理11.3.111.3.1知，知，该图不是哈密顿图，因该图不是哈密顿图，因而不会存在哈密顿回路。而不会存在哈密顿回路。d df fe ea ab bc cg gi ih h电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品

47、课程国家精品课程110-110-3636定理定理11.3.211.3.2设设g = g = 是具有是具有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 n

48、2 2个结点。这二个连个结点。这二个连通分支中分别有两个结点通分支中分别有两个结点v v1 1、v v2 2。显然，。显然，deg(vdeg(v1 1)n)n1 1- -1 1，deg(vdeg(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中存在哈

49、密顿通路。中存在哈密顿通路。设设p = vp = v1 1v v2 2v vk k为为g g中用中用“延长通路法延长通路法”得到的得到的“极极大基本通路大基本通路”，即，即p p的始点的始点v v1 1与终点与终点v vk k不与不与p p外的结外的结点相邻，显然点相邻，显然k nk n。（1 1）若）若k = nk = n，则，则p p为为g g中经过所有结点的通路，即中经过所有结点的通路，即为哈密顿通路。为哈密顿通路。（2 2）若）若k kn n，说明，说明g g中还有在中还有在p p外的结点，但此时外的结点，但此时可以证明存在仅经过可以证明存在仅经过p p上所有结点的基本回路，证上所有结

50、点的基本回路，证明如下：明如下：（a a）若在）若在p p上上v v1 1与与v vk k相邻，则相邻，则v v1 1v v2 2v vk 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相邻相

51、邻(j(j必定大于等于必定大于等于2 2，否则，否则deg(vdeg(v1 1)+deg(v)+deg(vk k)1+k-2)1+k-2n-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(v) + deg(vk k) j+k-2-(j-1) ) j+k-2-(j-1) = k-1= k-1n-1)n-1)。设。设v vk k与与v vi ir r-1-1

52、(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 2v vi ir r-1-1v vk kv vk-1k-1v vi 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电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程1

53、10-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-1t-1,v,vt t) )而添加边而添加边(v(vt t,v,vk+1k+1) )得到通路得到通路p p= v= vt-1

54、t-1v v1 1v vi ir rv vk kv vi ir r-1-1v vt tv vk+1k+1。显然，。显然，p p比比p p长长1 1，且，且p p上上有有k+1k+1个不同的结点。个不同的结点。对对p p重复重复(1)(1)(3)(3)，得到，得到g g中的哈密顿通路或比中的哈密顿通路或比p p更长的基本通路，由于更长的基本通路，由于g g中结点数目有限，故在有中结点数目有限，故在有限步内一定得到限步内一定得到g g中的一条哈密顿通路。中的一条哈密顿通路。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-4040推论推论推论推论11.3.

55、211.3.2 设设g = g = 是具有是具有n n个结点的简单个结点的简单无向图。如果对任意两个不相邻的结点无向图。如果对任意两个不相邻的结点u, vvu, vv，均有均有deg(u)+deg(v)ndeg(u)+deg(v)n则则g g中存在哈密顿回路。中存在哈密顿回路。推论推论11.3.311.3.3 设设g = g = 是具有是具有n n个结点的简单个结点的简单无向图，无向图，n3n3。如果对任意。如果对任意vvvv，均有，均有deg(v) deg(v) n/2n/2，则，则g g是哈密顿图。是哈密顿图。需要注意，定理需要注意，定理11.3.211.3.2给出的是哈密顿图的充分给出的

56、是哈密顿图的充分条件，而不是必要条件。在六边形中，任两个不条件，而不是必要条件。在六边形中，任两个不相邻的结点的度数之和都是相邻的结点的度数之和都是4 46 6，但六边形是哈，但六边形是哈密顿图。密顿图。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-4141例例11.3.311.3.3某地有某地有5 5个风景点，若每个风景点均有个风景点，若每个风景点均有2 2条道路与其条道路与其他点相通。问游人可否经过每个风景点恰好一次而他点相通。问游人可否经过每个风景点恰好一次而游完这游完这5 5处？处？解解 将将5 5个风景点看成是有个风景点看成是有5 5个结

57、点的无向图，两风个结点的无向图，两风景点间的道路看成是无向图的边，因为每处均有两景点间的道路看成是无向图的边，因为每处均有两条道路与其他结点相通，故每个结点的度数均为条道路与其他结点相通，故每个结点的度数均为2 2，从而任意两个不相邻的结点的度数之和等于从而任意两个不相邻的结点的度数之和等于4 4，正，正好为总结点数减好为总结点数减1 1。故此图中存在一条哈密顿通路，。故此图中存在一条哈密顿通路，因此游人可以经过每个风景点恰好一次而游完这因此游人可以经过每个风景点恰好一次而游完这5 5处。处。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-4242例

58、例11.3.411.3.4判断下图是否存在哈密顿回路。判断下图是否存在哈密顿回路。 5 5e e4 41 1a a2 2b b3 3c cd df fg gh hi ij jk km mn no op p5 54 41 12 23 3f fg gh hi ij jk km mn no op p5 5e e4 41 1a a2 2b b3 3c cd df fg gh hi ij jk km mn no op p解解 方法一方法一：在图中，删除结点子集：在图中，删除结点子集a, b, c, d, a, b, c, d, ee，得到的图有，得到的图有7 7个连通分支，由定理个连通分支，由定理11.

59、2.111.2.1知，知，该图不是哈密顿图，因而不会存在哈密顿回路。该图不是哈密顿图，因而不会存在哈密顿回路。 方法二方法二：若图中存在哈密顿回路，则该回路组成的图中任何结点：若图中存在哈密顿回路，则该回路组成的图中任何结点的度数均为的度数均为2 2。因而结点。因而结点1 1、2 2、3 3、4 4、5 5所关联的边均在回路中，所关联的边均在回路中，于是在结点于是在结点a a、b b、c c、d d、e e处均应将不与处均应将不与1 1、2 2、3 3、4 4、5 5关联的边关联的边删除，而要删除与结点删除，而要删除与结点a a、b b、c c、d d、e e关联的其它边，得到右上关联的其它边

60、，得到右上图，它不是连通图，因而图中不存在哈密顿回路。图，它不是连通图，因而图中不存在哈密顿回路。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程110-110-4343例例11.3.511.3.5证明下图没有哈密顿证明下图没有哈密顿通路。通路。 1(a)1(a)2(b)2(b)8(b)8(b)3(a)3(a)4(b)4(b)5(b)5(b)6(b)6(b)7(a)7(a)证明证明 任取一结点如任取一结点如1 1用用a a标标记，所有与它邻接的结点用记，所有与它邻接的结点用b b标记。继续不断地用标记。继续不断地用a a标记所标记所有邻接于有邻接于b b的结点，用