9.3 带权图与带权图中的最短通路 (一) 带权图 (二) 最短通路问题 (三) 狄克斯瑞(Dijkstra)算法.

Presentation on theme: "9.3 带权图与带权图中的最短通路 (一) 带权图 (二) 最短通路问题 (三) 狄克斯瑞(Dijkstra)算法."— Presentation transcript:

1 9.3 带权图与带权图中的最短通路 (一) 带权图 (二) 最短通路问题 (三) 狄克斯瑞(Dijkstra)算法

2 例 假设有分布在不同建筑物中的5台计算机C1, C2, C3, C4, C5。计算机连接的可能方案以及每种连接方式的成本（单位：元）如右图所示。 C C2 900 C3 C4 C5 120 400 200 450 370 C C2 C3 C4 C5 120 370 200 成本最低的安装方案

3 带权图 一个带权图规定为 ◆ 一个有序三元组(V，E，f )，或 ◆ 一个有序三元组(V，E，g)，或
◆ 一个有序四元组(V，E，f，g)， 其中，V是顶点集，E是边集， f是定义在V上的函数，g是定义在E上的函数， f和g我们可以称为权函数。 对于每一个顶点或边x，f(x)和g(x)可以是一个数字、符号或是某种量。

4 带权图中的最短通路 设G=(V,E,W)是一个带权图， 其W是边集E 到R+={x∊R│x>0} 的一个函数。
通常称 W(e)为边e的长度， 图G中一个通路的长度定义为通路中所经过的边的长度之和。 设 v0,z∊V， 要求从 v0到z的最短通路的长。 狄杰斯特拉算法

5 Dijkstra算法的基本思想 先把V分成两个子集， 一个设为T, T={v∊V│v0到v的最短通路的长已经求出}， 另一个是P=V－T。
显然T≠Ø，因为至少v0∊T。 要不断地扩大T，直到z∊T。 T P＝V－T 狄杰斯特拉算法 z v0

6 定理 对于任意的x∊P，设LT(x)表示从v0仅经过T中的顶点到x的最短通路的长。若不存在这样的通路，置LT(x)=∞。
称LT(x)为 x关于T的指标。令 LT(t1)=min{LT(x) │x∊P} 则 LT(t1)是从v0到t1的最短通路的长。 T P＝V－T 理解:全局最优=局部最优中的最优 x 注：LT(x)即为教材上的l(t) v0 t1

7 定理的证明 若存在从v0到t1的通路其长小于LT(t1)，这条路一定包含了P中的顶点（否则， 与LT(t1)最小性矛盾）。
设t2∊P，且t2是从v0到t1的其长度小于LT(t1)的通路中遇到的第一个P中的点。 于是有一条从v0到t2仅经过T中的点的通路， 其长度小于LT(t1)， 而由LT(t2)的定义知， LT(t2)<LT(t1), 这与假设 LT(t1)=min{LT(x)│x∊P}矛盾。 T P＝V－T t2 v0 t1

8 命题 设T和P已知，已找出t1, 使 LT(t1)=min{ LT(x) │x∊P}。 令 T’=T∪ {t1} P’=P－ {t1}，
并设 LT’(x)表示仅经过T’中的点从v0到x的最短通路的长。则有 LT’(x)=min{LT(x), LT(t1)+W({t1,x})} 这里，若图中{t1,x} ∉E, 取W({t1,x})=∞。

9 v0 t1 x v0 t1 x v0 t1 x t’

10 命题的证明 从v0到x且不含P’中顶点的任何一条最短通路，只有两种可能的情况： 一条既不包含P’中的顶点也不包含t1的通路.
此时，最短通路长仍然为 LT(x) v0 t1 x 也许有人说还有一种，就是一条从 v0到t1，再回到 T中某一顶点t’，由t’到t中间不经P中其余点。实际上，从v0到t1再到 t’的这条通路一定不短于从v0到t’的最短通路，而由作法可知从v0 到t’的最短路经过的点全在T中，所以即使有可能产生一条最短路，我们也可以用一条从 v0到t’的仅经过T中点的最短通路取代，也就是说这种情况可以归化为第一种情况考虑。

11 命题的证明 (2) 一条由v0到t1不包含P中的其它顶点，然后由t1经过{t1,x}到x的通路。 此时，最短通路长为
LT(t1) +W({t1,x}) . v0 t1 x 也许有人说还有一种，就是一条从 v0到t1，再回到 T中某一顶点t’，由t’到t中间不经P中其余点。实际上，从v0到t1再到 t’的这条通路一定不短于从v0到t’的最短通路，而由作法可知从v0 到t’的最短路经过的点全在T中，所以即使有可能产生一条最短路，我们也可以用一条从 v0到t’的仅经过T中点的最短通路取代，也就是说这种情况可以归化为第一种情况考虑。

12 命题证明的说明：还有一种？ 从 v0到t1，再到 T’中某一顶点t’，由t’到x中间不经P’中点。
实际上，从v0到t1再到 t’的这条通路一定不短于从v0到t’的最短通路，而由作法可知从v0 到t’的最短路经过的点全在T中，所以即使有可能产生一条最短路，我们也可以用一条从 v0到t’的仅经过T中点的最短通路取代，也就是说这种情况可以归化为第一种情况考虑。 v0 t1 x t’

13 Dijkstra算法 设起点是v0，终点是z。具体程序如下：
开始，设 T={v0}，P=V－T，对P中的每一个顶点x,令 LT(x)=W({v0,x})。 设t1是P中关于T有最小指标的顶点, 即 LT(t1)=min{LT(x) │x∊P}。 若t1=z，则终止。 否则，设 T’=T∪ {t1}，P’=P－ {t1}。 对于P’中的每一个顶点 ，计算它关于T’的指标： LT’(x)=min{LT(x), LT(t1)+W({t1,x})}。 把T’代为T,把P’代为P,把LT’(x)代为LT(x)， 重复步骤(2)。

14 例 求图9.9中从a到z的最短通路的长 最短通路的长度为9，最短通路的路径为(a,b,c,e,d,z)。 a c e b d z 1 4 7
2 3 6 5 a b c d e z T={a} ∞ ∞ ∞ LT(x) T={a,b} ∞ a c e b d z 1 4 2 3 T={a,b,c} ∞ T={a,b,c,e} T={a,b,c,e,d} 最短通路的长度为9，最短通路的路径为(a,b,c,e,d,z)。

15 例(在各顶点上标记了最短通路及长度) a c e b d z 1 4 7 2 3 6 5 4(a) ∞ 1(a) 1 4 7 2 3 6 5
3(a,b) 6(a,b) 1(a) 8(a,b) ∞ 1 4 7 2 3 6 5 3(a,b) 4(a,b,c) 1(a) 8(a,b) ∞ 1 4 7 2 3 6 5 3(a,b) 4(a,b,c) 1(a) 7(a,b,c,e) 10 1 4 7 2 3 6 5 3(a,b) 4(a,b,c) 1(a) 7(a,b,c,e) 9(a,b,c,e,d) 1 4 7 2 3 6 5

16 例 求顶点a至顶点f最短通路的长 L a b c d e f g 13 8  30  32 f b g e d c a 8 5 6 2
  32 f b g e d c a 8 5 6 2 30 13 7 17 32 9 L a b c d e f g  32 L a b c d e f g L a b c d e f g L a b c d e f g L a b c d e f g

17 狄克斯瑞 （Edsger Wybe Dijkstra， 1930-2002.08.02）
计算机编程艺术与科学创建人之一. 1930年出生在荷兰鹿特丹市，于2002年8月6日在荷兰家中与世长辞。他在欧洲和美国曾从事首次航空和结构计算机模拟的工作。曾是开发Algol的委员会成员。他编写了第一个Algol 60编译器。 1972年，荣获美国计算机协会的图灵奖。 1962年，他担任Eindhoven Polytechnic大学数学教授。他不赞成将教授职位称作计算科学教授，因为计算专业的科学性还不够。他用了十年时间使编程被承认为一门真正的学科。他对Basic编程语言所鼓励的许多“罪恶”尤其不能容忍，他说Basic不可挽回地伤害了年轻的程序员，并写下了一篇著名的论文：《Go To语句是有害的》。

18 9.4 欧拉图 (一) 欧拉通路欧拉回路 (二) 欧拉图 (三) 欧拉定理(1836年) (四) 欧拉图的示例

19 例(蚂蚁比赛问题) 甲、乙两只蚂蚁分别位于如下图中的结点A，B处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点C处。如果它们的速度相同，问谁先到达目的地？ A (甲) B(乙) C

20 哥德尼斯堡七桥问题 十八世纪初，在当时德国哥德尼斯堡（现加里林格勒）城的普雷格尔河上有7座桥。当地人经常在桥上散步，有人提出，从岛和河岸的某一处出发是否能找到一条通过每一座桥一次且仅一次的通路。 (b) (a) 1736年，欧拉解决了这个问题。从此，欧拉成为图论之父。

21 欧拉(Leonhard Euler，1707－1783) 瑞士数学家及自然科学家。在1707年4月15日出生於瑞士的巴塞尔，1783年9月18日於俄国的彼得堡去逝。 欧拉出生於牧师家庭，13岁时入读巴塞尔大学，15岁大学毕业，16岁获得硕士学位。 1733年，年仅26岁的欧拉担任了彼得堡科学院数学教授．据统计他那不倦的一生，共写下了886本书籍和论文。彼得堡科学院为了整理他的著作，足足忙碌了四十七年。 一位父亲临死时叫他的几个孩子按照下列方式瓜分他的财产：第一个儿子分得一百克朗与下剩财产的十分之一；第二个儿子分到二百克朗与下剩财产的十分之一；第三个儿子分到三百克朗与下剩财产的十分之一；第四个儿子分到四百克朗与下剩财产的十分之一……依此类推。问这位父亲共有多少财产？他一共有几个孩子？每个孩子分到多少？ 骡子与驴子身上各背着几百斤的重物，它们互相埋怨着。驴子对骡子说：“只要把你身上所背的重量给我一百斤，我所背的就是你的两倍。”骡子回答道：“不错！可是如果你把你背的一百斤给了我的话，我所背的就是你的三倍”。问它们各背了多少斤的重物？ 三个人在一起做某种游戏。第一局结束时，甲输给了其他两个人的东西分别等于他们手中所有的东西。第二局收场了，乙输给甲、西两人的东西也正好等于他们那时手中所有的东西；第三场结束时，这回却轮到丙是输家，他输给了甲、乙两人的东西也恰恰是他们两人那时手中所有的东西。他们结束了这种游戏，最后竟然发现三人各自手头有的东西正好一样，都是24个。问比赛前这三个人手中各有多少个东西? 欧拉还创设了许多数学符号，例如π（1736年），i（1777年），e（1748年），sin和cos（1748年），tg（1753年），△x（1755年），Σ（1755年），f(x)（1734年）等.

22 欧拉通路、欧拉回路、欧拉图 定义 G=（V，E）是一个图， ◆ G中一条通路称为欧拉通路，若此条通路经过了图中每条边一次且仅一次。
◆ 若一条欧拉通路是一个回路，则称此回路为欧拉回路。 ◆ 一个图若有欧拉回路，则称这个图为欧拉图。

23 定理1（欧拉，1736年） 一个没有孤立点的无向图具有欧拉通路，当且仅当它是连通的，并且或者没有奇数度的顶点或者有且仅有2个奇数度的顶点。
证明：“” 设这个图有欧拉通路，由于没有孤立点，显然是连通的，我们沿着欧拉通路走，除出发点外，每经过一个顶点，要走过关联这个顶点的两条边，且由于欧拉通路每条边仅能走过一次，除了出发点和终点外，每一个顶点被欧拉通路经过的次数乘以2，即该顶点的度数。因此，除两个端点外其余顶点为偶数度。出发点出发时，走过关联它的一条边，若途中再走过，同样，每经过一次走过，关联它的二条边。若出发点不是终点，则出发点是奇数度顶点，同样终点也是奇数度定顶点。若出发点和终点一致，最后回到出发点，又仅走过关联它的一条边，故所有顶点均为偶数度。 证明：“” （1）假设图中仅有两个奇数度顶点。从其中一个奇数度顶点出发，随意地经过图中的顶点，有一个要求，走过的边不能再走。我们说如果到了一个顶点，与这个顶点关联的边全部被走过，此时，就不能再走了。到不能走时，一定是到了另一个奇数度顶点，因为途中的点，都是偶数度，有进入这个顶点的边，就会有走出这个顶点的边。若所有的边均走完了，则这条路一定是欧拉通路。否则，擦去所有走过的边，剩下的图每一个顶点全是偶数度。我们在剩下的中任取一个不是0度但已被第一次经过的顶点，从它出发，仍随意地走，要求同上。此时若不能走了，一定回到了出发点，原因也是途中每个顶点是偶数度，只有出发点，原来虽也是偶数，但出发时，走过一条边后，剩下的是奇数条边了。此时，我们重新把这两条通路变为一条通路，从奇数度顶点出发，沿第一次的路径前进，当走过第二次路径的出发点时，停止走第一次路径的路，而先沿着第二次路径前进，把第二次路径走完，回到了第一次路径中，在沿第一次路径走到其终点。这样的一条通路仍保证了每条边仅走过一次，但确实增加了长度。若走完了所有的边，则此通路即欧拉通路。若还有边没有走完，重复第二条路径的走法，由于原图的连通性，所以若有没有走完的边，一定存在已经被走过的顶点，有没有走完的边，一直进行下去，由于图中边是有限的，若干步之后，一定可以走完所有的边，产生一条欧拉通路。 （2）若原图均为偶数度顶点，我们可以任选一个顶点出发，显然，有上面证明可知，走到不能走为止时，一定回到出发点。其余同上面证明。

24 例 找欧拉通路 A G F B C D E 从奇数度顶点走到奇数度顶点。 在顶点C可以将通路延伸如下： ABCDGC

25 例 找欧拉通路 A G F B C D E 在绿顶点处，走完所有黑边，再走完剩余的红边。有三种通路。

26 定理1的推论 一个无向图有欧拉回路当且仅当所有顶点均为偶数度。

27 一笔画问题 一个无向图是否有欧拉通路的问题与此图能否一笔画是同一个问题。 一个图能够一笔画即此图要么没有奇数度顶点，要么仅有两个奇数度顶点。

28 例 判断下面两图能否一笔画出

29 哥德尼斯堡七桥问题（续） 原问题无解。 能否通过拆掉一座桥来找到一条欧拉通路？ 能否通过建一座新桥来找到一条欧拉通路？

30 例 如果可能，请画一个顶点是偶数，边是奇数的欧拉图。否则说明理由。

31 例证明一个欧拉图不存在割边，即不存在一条边，拿去此边后，原图变成不连通的两部分。
证明: 下面证明从欧拉图中拿去任意一条边后,图还是连通的. 事实上, 假设G=(V,E)是一个欧拉图, |V|=n. 不妨假设图中欧拉回路是 v1, v2, v3, , vi, vi+1, , vn, v1=vn+1 显然,E={ {vi, vi+1}|1≤i≤n } 拿去任意一边{vi,vi+1}后, 所有顶点依然连通,而且组成一个欧拉通路: vi+1, ,vn, v1, ,vi

32 定理2 （1）一个有向图有欧拉回路，当且仅当它是连通的，并且每一个顶点的入度与出度相等。
（2）一个有向图有欧拉通路，当且仅当它是连通的，并且或者每一顶点的出度等于入度；或者除二个顶点外，其余各顶点出度等于入度，这二个顶点一个入度比出度多1，一个入度比出度少1。

33 例 判断以下有向图是否有欧拉回路、欧拉通路。
解：(1)无欧拉通路， (2)有欧拉通路，无欧拉回路， (3)有欧拉回路。

34 例 2元2级布鲁英（De Bruijn)序列 在分四个扇区的转盘上分别刻上0、0、1、1，顺时针转动转盘，观察所看到的两位的二进制数。 1
1 10 00 11 01 1 1 1 1 1 1 1 1

35 例 2元3级布鲁英（De Bruijn)序列 在无线电通信中，有一个有趣的有向欧拉回路的应用。假设有一个有8个不同扇区的旋转磁鼓，每个扇区要么包含一个0，要么包含1。共放置3个探测器使得它们能读出3个相邻扇区的内容，如下图所示。 下面的任务是：对每个扇区赋予1和0，使得探测器的读数能够描述旋转磁鼓的确切位置。 补充例题 1 假设如右图所示地赋值。可以看到：读数与位置不是一一对应 （8个位置，只有2个读数）。

36 例 2元3级布鲁英（De Bruijn)序列 希望把8个1或0安排成一个圆环，使得每3个连续扇区的读数都是不同的。
◆ 构造以00、01、11和10作为顶点的有向图 000 00 11 10 01 001 ◆ 从顶点ab， 到顶点b0构造一条有向边，并给这条边标记为ab0。 到顶点b1构造一条有向边，并给这条边标记为ab1。 (以00为例，结果见右图）

37 例 2元3级布鲁英（De Bruijn)序列 (1) 构造有向图 00 11 10 01 000 001 100 010 101 110
011 111

38 例 2元3级布鲁英（De Bruijn)序列 (2) 找欧拉圈(注意约束：各边的后两位=续边的前两位) (3) 挑出各边的第一位 00 11
10 01 000 001 111 110 101 100 010 011 1 1 1 1

39 例 2元4级布鲁英（De Bruijn)序列 在模数转换问题中，一个转鼓的表面分为16个扇形段，如图9.11（a）所示，鼓的位置信息使用二进制信号表示。如图9.11（b）中的d、c、b、a。转鼓的扇形段使用导体材料（阴影区）和非导体材料（空白区）组成，终端a、c和d接地，而终端b不接地。为了把鼓的16个不同位置，在终端用二进制信号表示出来，这些扇形段必须按照这样一种方式构成，即应使任何四个相连扇形段中，每两个的导电和不导电的形式都不相同。问题是确定导电和不导电扇形段的这种排列是否存在，若存在的话，求出这样一个排列。设二进制数字0表示一个导电扇形段，二进制数字1表示一个不导电扇形段。这个问题可以重述如下：把16个二进制数字排成一个环形，使得四个一次相连的数字所组成的16个序列均不同。 图9.11 模数转换图

40 例 2元4级布鲁英（De Bruijn)序列 ０ １ １ ０ １ ０ ０ １ ０ １ １ ０ １ １ ０ ０

41 例 2元n级布鲁英（De Bruijn)序列 能把 2n个二进制数字排列成一个环形阵列，使得这个排列里，任何n个依次相连的数字构成的序列，共有 2n个均不同的序列。 为了证明这一个点，我们构思一个具有2n-1个顶点的有向图，这些顶点标以 2n-1个n-1位的二进制数，并且从标有 a1a2…an-1的顶点到标有a2a3…an-10的顶点和标有 a2a3…an-11的顶点各有一条边，这两条边分别标上a1a2…an-10和 a1a2…an-11。显然这样一个图存在欧拉圈，而这个圈就对应于 2n个二进制数字所组成的一个环形排列。 一条闭串项链由35颗珠子组成，珠子的颜色共分7种。从7种颜色中选3种共有35种不同组合。 请找出一种珠子安排，令这35种不同颜色组合在项链的每3颗相连珠子中恰好出现1次。

42 中国邮递员问题 最后介绍一下“中国邮递员问题”（The Chinese Postman Problem）。
我国数学家管梅谷于1962年首先提出这个问题，并得到一些结果，得到世界同行们的承认。该问题是说：邮递员从邮局出发在他的管辖区域内投递邮件，然后回到邮局。自然，他必须走过他所辖区域内的每一条街道至少一次。在此前提下，希望找到一条尽可能短的路线。

43 中国邮递员问题 若G是欧拉图，则G中的任何一条欧拉回路均是最佳周游，而寻找欧拉回路的Fleury算法为解决这一问题提供了切实可行的方法。
设G=〈V,E,w〉是一带权图，L是G的一条回路，称 ∑w(ei) 为L的权。中国邮递员问题就是在带非负权的连通图中找到一条权最小的走遍所有边的回路，称此回路为最佳周游。 若G是欧拉图，则G中的任何一条欧拉回路均是最佳周游，而寻找欧拉回路的Fleury算法为解决这一问题提供了切实可行的方法。 对于非欧拉图，也有相应的算法 (1973年，Edmonds和Johnson给出了解法) 。 求Euler回路的弗罗莱 (Fleury)算法(1921年) (1) ∀v0∊V, 令W0=v0。 (2) 假设迹 Wi=v0e1v1⋯eivi已经选定，那么按下述方法从E-{e1, ⋯ei} 中选取边ei+1： （ i ） ei+1 和 vi 相关联； （ ii ）除非没有别的边可选择，否则 ei+1 不是Gi=G-{e1, ⋯,ei} 的割边(cut edge)。(所谓割边是一条删除后使连通图不再连通的边)。 (3) 当第(2)步不能再执行时，算法停止。

44 9.5 哈密尔顿图 (一)哈密尔顿通路哈密尔顿回路 (二)哈密尔顿图 (三)哈密尔顿图的必要条件 (四)哈密尔顿图的充分条件
9.5 哈密尔顿图 (一)哈密尔顿通路哈密尔顿回路 (二)哈密尔顿图 (三)哈密尔顿图的必要条件 (四)哈密尔顿图的充分条件 (五)旅行货郎问题(最短哈密尔顿回路问题)

45 哈密頓周遊世界問題 十九世纪中期威廉·哈密尔顿爵士描述了一个数学游戏：從正十二面體的一個頂點出發，沿著正十二面體的棱前進，要把二十個頂點無一遺漏地全部通過，而且每個頂點恰好只通過一次，最後回到出發點。 關於周遊世界問題是有一段頗為有趣的故事的。話說當年哈密頓設計了這個問題，並且以二十五英鎊賣給了玩具商。玩具商就為此而設計了一個玩具。 玩具商起初以為這是一道難題，可以吸引消費者購買。誰知當這玩具推出巿面後，這個問題就立刻被人解決了！令到玩具商虧蝕了一大筆金錢。

46 威廉·哈密尔顿爵士 Sin William Rowan Hamilton (1805 – 1865)
英国数学家、物理学家。 1863年，美国科学院选定在都柏林出生的爱尔兰人William Rowan Hamilton为它的第一个外籍院士，它们认为Hamilton是当时最伟大的科学家。 爱尔兰政府决定：2005年是Hamilton Year-哈密顿年。 Hamilton诞生在1805年8月3-4日的正夜，他是一个天才神童。在都柏林大学圣三一学院（该大学的数学学院已定名为哈密顿学院）的每一次文学和科学测试中他都从没有被任何人超过，他大学时居住在Dunsink天文台并在没有毕业时已是爱尔兰皇家天文学家一员，他对数学和物理理论做出重要的贡献。

47 哈密頓周遊世界問題 把正十二面体的一面正五邊形ABCDE沿着棱剪开，并将该五邊形「張開」，並將它「壓平」在一個平面上（如右下圖）。 A B

48 哈密頓周遊世界問題 可以畫出一個符合要求的路徑（如左下圖中的藍線）。將這個路投影於原正十二面體之上（如右下圖），那麼就解決了這個問題。 A
B C D E 周遊世界問題可以算是歐拉七橋問題的延續。解此題時，亦應用了圖論的特性，就是圖中點與線之間的關係是最重要的，點的位置和線的長度並不重要，因此我們可以將原圖變形，並壓平至一個平面之上來考慮，從而得到它的解。

49 哈密尔顿通路、哈密尔顿圈 定义： G=(V,E)是一个图 若G中一条通路通过每一个顶点一次且一次，称这条通路为哈密尔顿通路。
若一个图存在哈密尔顿圈，就称为哈密尔顿图。 到目前为止判定一个图是否是哈密尔顿图的充要条件尚不知道，而且这个问题是图论中主要的未解决问题之一。

50 例 画一个图， （1）使它是一个哈密尔顿图和一个欧拉图； （2）使既不是一个哈密尔顿图和又不是一个欧拉图； （3）使它是一个哈密尔顿图但不是一个欧拉图； （4）使它不是一个哈密尔顿图但是一个欧拉图.
解: (1) （2） (3) （4）

51 例 (1) 画一个欧拉图，但不是哈密尔顿图。 (2) 画一个哈密尔顿图，但不是欧拉图。 (3) 画一个有哈密尔顿路的非哈密尔顿图 (4) 画一个有哈密尔顿通路但无哈密尔顿圈的欧拉图。
解： 下面两个例子都适合（1）（3）（4）的要求 右边的例子适合（2）的要求

52 定理1 (必要条件 ) 若G=(V,E) 是一个哈密尔顿图，则对于V的每一个非空子集S，均有 W(G－S) ≤|S|
其中W(G－S)表示图G擦去属于S中的顶点后，剩下子图的连通分枝的个数。

53 定理1的证明 设C是图G中的哈密尔顿圈，对于V的任意的一个非空子集S。显然有： W(C－S) ≤|S|
其中C－S表示图G仅由哈密尔顿圈C中的边组成的子图擦去S中的顶点后所得子图, W(C－S)表示这样的子图的连通分枝的个数。 显然 W(G－S) ≤W(C－S), 定理得证。

54 例 不满足必要条件，不是哈密尔顿图。 不满足必要条件，不是哈密尔顿图。

55 例 图9.14(a) 不满足必要条件，不是哈密尔顿图。因为删去黑点所示的三个顶点，剩下四个连通分枝（见右下图）。

56 例 皮德森（Petersen）图 皮德森图（见图9.14（b））满足必要条件，但也不是哈密尔顿图（尽管有哈密尔顿通路）。
在该图G中，对任意的顶 点集合S，都满足 W(G-S) ≡１|S|．

57 定理２ (充分条件) 设G=(V,E)是一个无向简单图， |V|=n. n≥3. 若对于任意的两个不相邻顶点u，v∊V，
d(u)+d(v) ≥n， 那么, G是哈密尔顿图 我们称一个没有多重边，没有自环，也没有孤立点的图为简单图，若不声明是简单图，就泛指图或多重图。 在耿素云《离散数学》上，充分性条件仅要求对于不相邻的顶点成立即可。

58 定理２的证明: 先证G是连通图。 用反证法，若G不连通，则 至少分成两个不连通的部分， 其中一部分的顶点集为Ｖ1，另一部分为V2，
令|V1|=n1，|V2|=n2，则n1+n2=n。 在V1中取一个顶点 v1，d(v1)≤n1-1， 在V2中取一个顶点 v2，d(v2)≤n2-1， 所以 d(v1)+d(v2) ≤n1+n <n-1， 与已知矛盾，所以G是连通图。

59 定理２的证明思路 找起点与终点仅与通路中的顶点相邻的初等通路v1, v2, …, vp. 将初等通路变成圈. 若v1与vp相邻接， 圈为
A B C D E

60 定理２的证明思路 若v1与vp不邻接，必然存在vi-1, vi，使得 vi-1与vp相邻接, vi与v1相邻接，
于是圈为 v1, v2, …, vi-1,vp, …, vi, v1 A B C D E A B C D E 60

61 定理２的证明思路 如果圈没有包含所有顶点，则任取与圈连通的一个顶点Vx，加上一条边，并去掉圈中的一条边，则得到长度为p+1的初等通路，并可以将之扩展为具有性质①的初等通路。 A B C D E A B C D E A B C D E

62 定理２的证明思路 举例 A B C D E A B C D E A B C D E

63 定理２的证明思路 ②将初等通路变成圈（在充分条件满足前提下） 在下例中，不能将图中的两条初等通路变为圈（不满足定理的充分性条件）。 A B
C D E A B C D E

64 定理2的证明（亮点） 将起点与终点仅与通路中的顶点相邻的初等通路v1, v2, …, vp （v1与vp不相邻接）变成一个圈。
设 v1仅与vi1，vi2，…，vik相邻, 其中2≤ij ≤p-1。则 vp必和 vi1-1，vi2-1，…，vik-1 中一个顶点相邻, 不失一般性设与 vij-1相邻, 构建圈的示意图见图9.15。 · · · · · · vij vij vp-1 vp v1 v2 v vij-1 事实上，对通路的端点有要求如下：“v1与vp仅与通路中的顶点相邻”。这样， d(v1)=k. 而对于vp来说，在除了自己以外的p-1个顶点中，需要排除k个位置，故d(vp) ≤p-k-1. 这样的vij-1一定存在, 否则d(v1)=k，而d(vp) ≤p-k-1。 即d(v1)+d(vp) ≤p-1<n, 与充分性矛盾。

65 例 当n>2时，完全图Kn是哈密尔顿图
✘ ✔ ✔ ✔ 我们称一个没有多重边，没有自环，也没有孤立点的图为简单图，若不声明是简单图，就泛指图或多重图。

66 例 顶点数为6，但任意两个顶点的度数之和为4，即有46，不满足充分性条件，但它仍然是哈密尔顿图。
不满足充分条件，不能由此判断它是否哈密尔顿图． 事实上，它不满足必要条件，故不是哈密尔顿图。

67 例 有12个人围坐一圆桌，边会餐边交流乒乓球技术。已知这12个人中，每个人至少和其余的6人打过球，试问是否有一种坐法，使每个人左、右俩人都和他打过球？请说明原因。
证明：12个人为12 个顶点，两个人若打过球，形成一条边，构造出图G=（V，E）。 因为这12个人中，每个人至少与其余6个人打过球，则对于任意两个顶点u和v， d(u)+d(v)6+6=12， 因此图G存在哈密尔顿圈。沿哈密尔顿圈就座，能使每个人左、右两人都和他打过球。

68 例 设n≥2，有2n个人参加宴会，每个人至少认识其中的n个人，怎样安排座位，使大家围坐在一起时，每个人的两旁坐着的均是与他相识的人？
解 每个人用一个顶点表示，若二人相识，则在其所表的顶点间连边。这样得到一个2n 阶的无向图，因为对于任意的两个顶点u，v，有： d（u）+d（v）≥2n 故图中存在一条哈密顿回路，这条回路恰好对应一个座位的适当安排。

69 例 11个学生要共进晚餐，他们将坐成一个圆桌，计划每次晚餐上，每个学生有完全不同的邻座，这样能共进晚餐几天？
分析： 考察K11。 每个顶点的度数为10， 所以有第1条哈密尔顿回路。 考察K11中去掉第1条哈密尔顿回路后的图。 每个顶点的度数为8， 所以有第2条哈密尔顿回路。 考察K11中去掉前2条哈密尔顿回路后的图。 每个顶点的度数为6， 所以有第3条哈密尔顿回路。 还有没有哈密尔顿回路呢？总共有55条边，最多有5条哈密尔顿回路。能不能找到5条哈密尔顿回路？

70 将学生编号为1，2，…，11，用顶点表示，用边表示相邻关系。因为每个学生可与任何其他人邻座，故构成完全图。
因为11是质数，且1，2，3，4，5都与11互质，所以可分别用1，2，3，4，5作步长，穿程于图中的各个顶点，得到以下的五个回路： 1，2，3，4，5，6，7，8，9，10，11，1 1，3，5，7，9，11，2，4，6，8，10，1 1，4，7，10，2，5，8，11，3，6，9，1 1，5，9，2，6，10，3，7，11，4，8，1 1，6，11，5，10，4，9，3，8，2，7，1

71 例 当n为不小于3的奇数时，完全图Kn上恰有 (n-1)/2 条互相均无任何公共边的哈密尔顿圈。 证明见王元元《离散数学导论》p174.

72 例 设G为n个顶点的简单无向图 (1)若G的边数为m=(n-1)(n-2)/2+2， 证明G为哈密尔顿图。
证: 利用反证法证明满足充分条件。 如果存在两点v1,v2, 使得 d(v1)+d(v2) ≤n-1 则从图G中擦去顶点v1，v2及其与它们关联的边后，考察剩下的n-2个顶点的图的边数m’。 ① 若v1,v2不相关联， 则 m’ ≥m-(n-1)=(n-2)(n-3)/2+1 ② 若v1,v2相关联， 则 m’ ≥m-(n-1-1)=(n-2)(n-3)/2+2 这与剩下的图是简单无向图矛盾。

73 例 设G为n个顶点的简单无向图 (2) 若G的边数为m=(n-1)(n-2)/2+1， 那么G是否一定为哈密尔顿图？
解(2): 结论不成立，下面是3个例子。 n=4 m=3×2/2+1 n=5 m=4×3/2+1 n=6 m=5×4/2+1

74 例 设 G=(V,E)是无向连通图， 证明G中有桥或割点，则 G不是哈密尔顿图。
一个连通图中有一个顶点称为桥或割点，若擦去这个顶点后，图就不连通了。 n=4 m=3×2/2+1 n=5 m=4×3/2+1 n=6 m=5×4/2+1

75 定理3 哈密尔顿通路的充分条件 G=(V,E)是一个无向简单图，|V|=n
定理3 哈密尔顿通路的充分条件 G=(V,E)是一个无向简单图，|V|=n 若对于V中任意两个顶点 u，v∊V， d(u)+d(v) ≥n－１， 那么, G中有哈密尔顿通路。 例 不满足定理２的充分条件，不能由此判断它是否哈密尔顿图． 不满足定理１的必要条件，可以判断它不是哈密尔顿图． 不满足定理３的充分条件，但可以由定义判断它存在哈密尔顿通路．

76 例考虑在七天内安排七门课程的考试，使得同一位教师所担任的两门课程考试不排在接连的两天中。试证明，如果没有教师担任多于四门课程，则符合上述要求的考试安排总是可能的。
证明：设G为具有七个顶点的图，每个顶点对应于一门课程考试，如果这两个顶点对应的课程考试是由不同教师担任的，那么这两个顶点之间有一条边。因为每个教师所任课程数不超过4，故每个顶点的度数至少是7-4=3，任意两个顶点的度数之和至少是6，故G总是包含一条哈密尔顿通路，它对应于一个七门考试科目的一个适当的安排。

77 例 某公司生产的8种不同颜色的纱织成的双色布，已知在品种中，每种颜色至少分别与其它7种颜色中的4种颜色搭配。试用图论的语言证明可以挑选出4种双色布，它们恰有8种不同的颜色。
解: 构造图G=(V,E)如下:以8个顶点表示8种不同的颜色; 若两种颜色出现在双色布品种中,则它们对应的两个顶点之间有边连接。 在图G中，任意一个的度数至少是4，于是任意两个顶点的度数之和至少是8，满足存在哈密尔顿回路的充分条件。因此，在图G中，存在哈密尔顿回路， 按此回路可以找到两组“4种双色布”，各自分别由8种不同的颜色的纱织成。 (2008硕士） 77

78 有向哈密尔顿通路（圈） 一个有向哈密尔顿通路（圈）是一个包含每个顶点恰好一次的有向通路（圈）。 例 考察 A
B C 例 考察 ▲ ABC、BCA、CAB都是哈密尔顿通路。 ▲ ABCA是哈密尔顿圈。

79 ？ 有向完全图 定义：去掉边的方向后所得的无向图（基图）是完全图 A B C A B C 其它定义：每个顶点都邻接到其它顶点的有向图
（该定义见耿素云〈离散数学〉第150页， 屈婉玲〈离散数学及其应用〉第154页）

80 例 有没有哈密尔顿通路? 在左图中，只有一条哈密尔顿通路，亦即给出了一个排序：A、B、C、D。 在右图中， 有1条哈密尔顿圈，即ABCDA；
例 有没有哈密尔顿通路? 在左图中，只有一条哈密尔顿通路，亦即给出了一个排序：A、B、C、D。 A B C D A B C D 在右图中， 有1条哈密尔顿圈，即ABCDA； 有5条哈密尔顿通路。

81 定理4 一个有向完全图总存在哈密尔顿路 证明思路: v1 v2 (v1v2) v1 v2 vx v1 v2 vx (vxv1v2) v2
定理4 一个有向完全图总存在哈密尔顿路 证明思路: v1 v2 (v1v2) 或 v1 v2 vx v1 v2 vx (vxv1v2) v1 v2 vx 或 (v1vxv2) (v1v2vx)

82 定理4的证明思路(续) v1 v2 v3 v2 v3 vx v1 vx (vxv1v2v3) v1 v2 vx v3 (v1v2v3vx)
或 v1 v2 v3 v2 v3 vx v1 vx (vxv1v2v3) v1 v2 vx v3 或 (v1v2v3vx)

83 定理4的证明思路(续) v1 v2 vx v3 v1 v2 vx v3 或 (v1v2vxv3) (v1vxv2v3)

84 定理4 一个有向完全图总存在哈密尔顿通路 证明：设(v1,v2,…,vp)是有向图中的一条初等通路，显然，这样的通路肯定是存在的，最差的情况是仅有一条边的通路。若这条通路包含了G中所有顶点，则即为所求的哈密尔顿通路, 否则设vx是不在这条通路上一个顶点。首先看(vx,v1)是否是E中的边，若(vx,v1)∊E，则我们把vx扩进原来的通路，得到一条扩大了的初等通路。相反，若(vx,v1) ∉E，则(v1,vx)∊E，看(vx,v2)是否是E中的边，…。发展下去结果有两个，其一，存在一个vi，(1≤i≤p-1)，(vi-1,vx) ∊E，(vx,vi) ∊E，则(v1,…,vi-1,vx,vi,…vp)是一条扩大了的初等通路；其二，对于所有的 i，(1≤i≤p)，(vi,vx)∈E，则(v1,…,vp,vx)是一条扩大了的初等通路。 同法，我们可以把不在初等通路上的顶点全部扩展进去得一条哈密尔顿通路。

85 旅行货郎问题 (TSP) 如果现在有一个图G，而这图的每一条弧上都算上一个数字，要怎样才能找到这图的哈密顿回路具有所有的弧上数字的和是最小值的性质，这个问题就是数学上大名鼎鼎的难题：“旅行货郎问题”。 这问题在1932年由德国著名数学家K．Menger提出，是许多人废寝忘食研究的对象。 我们在日常生活中就会遇到这问题，比方说：你为了商业业务，需要乘飞机飞几个城市，你要怎样安排行程，使到你能走遍你要去的城市，最后又回来原出发地，而又能省钱？ “旅行货郎问题”是这么容易明白，可是要找出一个行之有效及能迅速提供解答的方法，目前并不存在。人们现在对于这问题的实际情形都是借助高速的电子计算机来运算。

86 Travelling Salesman Problem (TSP)
设G=(V,E,W)是一个带权完全图，|V|=n，W是边集E 到R+={x∊R│x>0} 的一个函数。对于V中任意的三个顶点vi,vj,vk，有 W({vi,vj})+W({vj,vk}) ≥W({vi,vk})。 要在G中求得一条最短长度的哈密尔顿圈。一个哈密尔顿圈(e1,e2, ⋯,en-1)的长度定义为 ∑ W(ei)，其中ei(1≤i≤n-1)是E中的边。 i=1 n-1

87 旅行货郎问题的最邻近算法 (1) 任选一个顶点作为始点，在与这点相关联的边中，选权值最小的一条边，把这条边作为所求的哈密尔顿圈中的一条路，这条边的两个端点称为被访问过的顶点。 (2) 设x是表示刚加入路中的一条边上的新访问过的顶点，若存在未被访问过的顶点，在x和未被访问过的顶点之间的边中找权值最小的一条边，把这条边加入路中，这条边的另一个顶点是新访问过的顶点。 (3) 若不存在未被访问过的顶点，就新访问过的顶点与始点之间的边加入这条路得一个圈，是一条哈密尔顿圈，否则执行(2)。

88 例 左：从顶点a出发，所求出的哈密尔顿圈总长为 40。 右：从顶点e出发，所求出的哈密尔顿圈总长为 37，这是最短哈密尔顿圈。
b c d e 7 10 12 14 9 5 8 6 13 11 a b c d e 7 10 12 14 9 5 8 6 13 11 左：从顶点a出发，所求出的哈密尔顿圈总长为 40。 见图9.16(f)。 右：从顶点e出发，所求出的哈密尔顿圈总长为 37，这是最短哈密尔顿圈。

89 作业18 选择题 试用两种图论方法判断若干个英文单词是否可以构成这样的序列, 使得相邻的两个单词中前一个单词的末字母等于后一个单词的首字母。 （1）mouse、acm、mom、monday、am （2）mouse、acm、mom、monday、ya

90 课练2. 画欧拉图与哈密尔顿图各两个，满足： 有奇数个顶点、奇数条边； 有偶数个顶点、偶数条边。
A (甲) B(乙) C 课练1. 甲、乙两只蚂蚁分别位于如下图中的结点A，B处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点C处。如果它们的速度相同，问谁先到达目的地？ 课练2. 画欧拉图与哈密尔顿图各两个，满足： 有奇数个顶点、奇数条边； 有偶数个顶点、偶数条边。