从七桥问题说起
从七桥问题说起 ——窥视数学的后花园
2008-6-5
1
下列图形分别能几笔画成？
2008-6-5
2
下列图形分别能几笔画成？
2008-6-5
3
七桥问题
时间：18世纪 地点：普鲁士的哥尼斯堡城（Königsberg）， 普雷格尔（Pregel）河 人物：悠闲的市民们， 欧拉
问题：能否经过每座桥一次且仅一次回到出发点？
2008-6-5 [email protected] 4
Euler闭迹(closed trail, tour, circuit)：经过图G的 每条边恰好一次的闭迹。 Euler迹（trail）：经过每条边恰好一次的迹。 Euler图：有Euler闭迹的图。 图中顶点的度：顶点关联的边的条数。
2008-6-5
5
定理1 一个非空连通图是Euler图当且仅当它没有奇度顶点。 证明 必要性：设图G是Euler图，C是G中一个Euler闭迹。对G中任 一个 顶点 v，v必在C上出现。因C每经过v一次，就有两条与v关联的边被使 用。设C经过v共k次，则C经过了2k条于v关联的边，故v的度为2k。 充分性：无妨设图Ｇ的顶点个数n >1。因G连通，故至少有一条边。下 面用反证法证明充分性结论。 假设图G无奇度顶点，但它不是Euler图。令 S = {G | G是至少有一条边的n阶连通图，无奇度顶点，且不是Euler图} 则S非空。取S中边数最少的一个，记为G0 。因G0无奇度顶点，故G0中 顶点的度至少为 2，因此G0含有圈，从而含有闭迹。设C是中一条最长 的闭迹。由假设，C不是G0的Euler闭迹。因此G0中将C的边去掉后必有 一个连通分支至少含有一条边。记这个连通分支为G1。由于C是闭迹， 故G1中没有奇度顶点，且G1 的边少于G0 的边。由G0的选择可知， G1必 有Euler闭迹，记为 C1。因此C＋C1是的一条闭迹，且它比C更长，这与 C的选取矛盾。证毕。
2008-6-5 [email protected] 6
重返七桥
问题：能否经过每座桥一次且仅一次回到出发点？ 答案：不能 为什么？因右图中不存在欧拉闭迹，因此不能一笔画 完且回到出发点。 新问题：不要求回到出发点能否一笔画完？到底几笔 能画完？——好奇是创新的钥匙！
2008-6-5
7
定理2 一个连通图有Euler迹当且仅当它最多有两个奇度顶点。 证明 必要性：设连通图G有Euler迹T。若T是Euler闭迹，则G中无奇度 顶点。否则，设T的起点和终点分别为u, v。在G的基础上，给u, v间添 加一条边e（若G中有边uv，则e是重边），所得之图记为G*，则T+e是 G*的Euler闭迹。由定理1，图G*无奇度顶点。故G最多只可能有两个 奇度顶点。 充分性： 若G无奇度顶点，则由定理1，G有Euler闭迹，自然有Euler迹。 若G只有两个奇度顶点，设其为u,v，则在u,v间给G添加一条新边e，所 得之图G +e的每个顶点都是偶度顶点，由定理1，G +e有Euler闭迹， 因
此G有Euler迹。证毕。 推论 一个连通图可k笔画成当且仅当它最多有2k个奇度顶点。
2008-6-5 [email protected] 8
再返七桥
问题：七桥问题对应的图几笔能画完？
2008-6-5
9
下列图形分别能几笔画成？
2008-6-5
10
下列图形分别能几笔画成？
Herschel图
Petersen图
2008-6-5
11
如何求欧拉图中的欧拉闭迹？ ——Fleury算法
基本思想：从图中一个顶点出发，用深度优先方法找图的迹，在任何 一步，尽可能不使用剩余图的割边，除非没有别的选择。 Fleury算法步骤： 输入：欧拉图G 输出：G的欧拉闭迹 step1. 从G的任一个顶点v0开始，令w0=v0，i:=0。 step2. 设迹wi=v0e1v1···eivi已取定。从E\{e1,e2, ···,ei}中选取一条边ei+1， 使得 （1） ei+1和vi相关联； （2） ei+1不是图G\{e1,e2, ···,ei}的割边，除非没有别的选择。 step3. 当step2不能再执行时，停止。
2008-6-5 [email protected] 12
用Fleury算法求下图的欧拉闭迹
2008-6-5
13
用Fleury算法求下图的欧拉闭迹
2008-6-5
14
用Fleury算法求下图的欧拉闭迹
2008-6-5
15
用Fleury算法求下图的欧拉闭迹
2008-6-5
16
用Fleury算法求下图的欧拉闭迹
2008-6-5
17
用Fleury算法求下图的欧拉闭迹
2008-6-5
18
用Fleury算法求下图的欧拉闭迹
2008-6-5
19
用Fleury算法求下图的欧拉闭迹
2008-6-5
20
用Fleury算法求下图的欧拉闭迹
2008-6-5
21
用Fleury算法求下图的欧拉闭迹
2008-6-5
22
用Fleury算法求下图的欧拉闭迹
2008-6-5
23
用Fleury算法求下图的欧拉闭迹
2008-6-5
24
中国邮递员问题
问题（管梅谷，1960）：一位邮递员从邮局出发投递邮 件，经过他所管辖的每条街道至少一次，然后回到邮局。请 为他选择一条路线，使其所行路程尽可能短。 图论模型：求赋权连通图中含所有边的权最小的闭途径。这 样的闭途径称为最优邮路。
2008-6-5
25
中国邮递员问题
思路：（1）若G是Euler图，则G的Euler闭迹便是最优邮路，可用 Fleury算法求得； （2）若G不是Euler图，则含有所有边的闭途径必须重复经过一些 边，最优邮路要求重复经过的边的权之和达到最小。闭途径重复经 过一些边，实质上可看成给图G添加了一些重复边（其权与原边的 权相等），最终消除了奇度顶点形成一个Euler图。因此，在这种情 况下求最优邮路可分为两步进行：首先给图G添加一些重复边得到 一个Euler图G*，使得添加边的权之和最小；然后用Fleury算法求G* 的一条Euler闭迹。这样
便得到G的最优邮路。 问题是：如何给图G添加重复边得到Euler图G*，使得添加边的权之 和最小？
2008-6-5 [email protected] 26
解中国邮递员问题的算法
将上述问题中的Euler图G*称为图G的最优邮路Euler图。 方法一：图上作业法 定理3 设C是一条经过赋权连通图G的每条边至少一次的闭途 径，则C是G的最优邮路当且仅当C对应的最优邮路欧拉图 G*满足： (1) G的每条边在G*中至多重复出现一次； (2) G的每个圈上在G*中重复出现的边的权之和不超过该圈总 权的一半。
2008-6-5
27
解中国邮递员问题的算法
奇偶点图上作业法 算法口诀 先分奇偶点，奇点对对联； 联线不重迭，重迭要改变； 圈上联线长，不得过半圈。
2008-6-5
28
解中国邮递员问题的算法
方法二：Edmonds-Johnson方法 定理4 设G是赋权连通图，G中有2k个奇度顶点。G*是G的一 个最优邮路Euler图，令 E0={e|在由G得到G*时，e被添加重复边}。 则E0中的边形成的子图G[E0]是以G的奇度顶点为起点和终点 的k条无公共边的最短路之并。
2008-6-5
29
解中国邮递员问题的算法
Edmonds-Johnson方法的基本思想：
先求出G中所有2k个奇度顶点间的最短路。为了从中选出k条权最 小且无公共端点的最短路，以G的所有奇度点为顶点构造赋权 完全图K2k，两顶点连边上的权为这两个奇度点在G中最短路的 权。求赋权完全图K2k的最小权完美匹配，该完美匹配的k条边 对应的k对顶点间的最短路必定无公共边（否则，若两条路有公 共边，则删去公共边后可得到两条连接奇度顶点的更短路，从 而对应出权更小的完美匹配，矛盾）。沿这k条最短路添加重复 边，便可得到最优邮路Euler图G*。然后找出G*的Euler闭迹， 即得到最优邮路。
2008-6-5 [email protected] 30
解中国邮递员问题的算法
Edmonds-Johnson算法：
Step1. 若G中无奇度顶点，令G*=G，转step2；否则转step3。 Step2. 求G*中的Euler闭迹，结束。 Step3. 求G中所有奇度顶点对之间的最短路。 Step4. 以G中奇度顶点集为顶点集，构作赋权完全图K2k ，其中各 边的权为对应两顶点在G中最短路的权。 Step5. 求K2k中最小权完美匹配M。 Step6. M中每条边所匹配的两点在G中都对应有一条最短路，在G 中沿这些最短路添加重复边，得Euler图G*，转step2。
2008-6-5 [email protected] 31
例 求下图的最优投递路线，其中A点为邮局。
B 3 A 4 F 8
5
C 5 10 9
14 6
D
E
2008-6-5
32
解：该图只有两个奇度点B和E，B到E的最短路为BAFE，权为13。 按算法Step4，令，构造出赋权完全图（如下图a），其最小权 完美匹配由其唯一的边BE构成。再按照算法的Step6，沿匹配 边BE在G中对应的最短路BAFE添加重复边
，得到相应的Euler 图G*（如图b）。易求得G*的Euler闭迹，从而得到最优邮路。
B 3 B 13 E A 4 F
图a: 按算法Step4 构造出 的赋权完全图K2。
5 8 14 6
C 5 10 9 E D
图b: 按算法Step6 构造出 的Euler图G*。
2008-6-5
33
计算机鼓轮的设计
计算机旋转鼓轮如下图所示。一个圆环被等分为2n个单元， 每个单元标有0或1（分别表示该单元为绝缘体或导体）。鼓轮 有n个触点，当鼓轮每旋转一个单元时，n个触点便读出一个n元 二进制数。现在希望设计各个单元的0、1标识，使得鼓轮旋转 一周后，恰好能得到所有个不同的n元二进制数。
触点
2008-6-5
34
求解思想：以所有n-1位二进制数为顶点，每两个形如p1p2···pn-1 和p2p3···pn的二进制数对应的顶点之间连一条有向边（从前一个 数指向后一个数）。这样获得一个有向图G，G的每个顶点的出 度和入度都为2。按欧拉图的判定条件，G是欧拉图。找出G的 一条有向欧拉闭迹，沿欧拉闭迹前行一步，相当于鼓轮转动一 格。因此只需沿欧拉闭迹将遇到的每个顶点取最后一位数字， 将得到的字符串顺序抄入鼓轮的格子即可。
000
0 1 1 0 1 0 0 1 1 1 1 0 0 0 0 1
001
100 010 101
触点
011 111
110
2008-6-5
35
Hamilton问题
Hamilton图的研究起源于一种十二面体上的游戏。1857年， 爱尔兰著名数学家William Rowan Hamilton爵士（他也是第一个 给出复数的代数描述的人）制作了一种玩具，它是一个木制的 正十二面体，在正十二面体的每个顶点上有一个木栓，并标有 世界著名城市的名字。游戏者用一条细线从一个顶点出发，设 法沿着十二面体的棱找出一条路，通过每个城市恰好一次，最 后回到出发点。这个游戏当时称为Icosian游戏，也称为周游世界 游戏。
2008-6-5
36
经过图G的每个顶点恰一次的路称为G的Hamilton路， 简称为H路。 经过图G的每个顶点恰一次的圈称为G的Hamilton圈， 简称为H圈。 具有Hamilton圈的图称为Hamilton图，简称为H图。
2008-6-5 [email protected] 37
Hamilton图的判定
定理1 设G是二部图，若G是H图，则G必有偶数个顶点。 定理 2 若G是H图，则对V(G)的每个非空真子集S，均有： 连通分支数W(G－S) ≤ | S |。
u
v Herschel图不是H图
2008-6-5 [email protected]
w
38
Hamilton图的判定
定理3 设G是至少含 3个顶点的简单图，如果G中每个顶点 的度都不小于点数的一半，则G是Hamilton图。 定理4 设G是至少含 3个顶点的简单图，如果G中任意两个 不相邻顶点的度数之和都不小于G的点数，则G是 Hamilton图。
2008-6-5
39
旅行商问题（TSP）
旅行商问题：一个旅行商从n个城镇中的某一城镇出发，欲经 过其余个城镇一
次且仅一次，最后回到出发点。他应该如何设 计旅行路线，才能使所走路程最短？ 图论描述：将城镇作为顶点，两顶点连边当且仅当对应的两城 镇能直达，每条边上以道路的里程作为权。从而获得一个赋权 图G。旅行商问题现在可以叙述为： 给定赋权图G，求G的一个权最小的Hamilton圈。
2008-6-5
40
TSP-近似算法
最小生成树法 算法基本思想为：先求出的一棵最小生成树T，给T的每条 边添加一条重边，使其成为Euler图。然后沿Euler图的一条 Euler闭迹遍历的所有顶点。在每个顶点处，若沿Euler闭迹 前行时遇到的顶点已被访问过，则跳过它直接访问Euler闭 迹的下一个顶点。直至遍历的所有顶点后回到出发点。注意 我们的对象是一个完全图，故上述跳跃方式的访问总是可行 的，且最终能得到一个Hamilton圈。
2008-6-5
41
TSP-近似算法
最小生成树法：求中最小权Hamilton圈。 输入：赋权完全图。 输出：近似的最小权Hamilton圈。 step1. 求的一棵最小生成树T； step2. 将T中各边均添加一条重边，设所得图为； step3. 求的从某点v出发的一条Euler闭迹； step4. 按如下方法求出G的一条Hamilton路：从顶点v出发，沿Ev 访问G*中各顶点。在此过程中，一旦遇到重复顶点，就跳过它直 接走到Euler环游上的下一个顶点。直到访问完所有顶点为止。
2008-6-5 [email protected] 42
TSP-近似算法
例 用最小生成树法求如下赋权完全图的最小权Hamilton圈。 解：求解过程图示如下。先求出一棵最小生成树T，T的各边加重边后得 G*，G*从a点出发的一条Euler闭迹为C = aeadabcba，从a点出发沿C依 次访问各点，遇到已访问过的点时直接跳到C的下一个点，这样便得到 近似的最小权Hamilton圈aedcba。
a 5 b 9 12 c 8 7 16 9
G
a 5 e 5 8 d b 5 9 c d
最小生成树T
a 5 e b 9 c d
加重边后得G*
a 5
5
5
5
5 e b 9 c 9
5 e 8 d
近似最优H圈
2008-6-5
43
TSP-近似算法
定理5 设赋权完全图的各边之权均为正数，且对∀vi , v j , vk ∈V， c0 都有w(vi v j ) + w(v j vk ) ≥ w(vi vk ) ， 则 *
* w(T ) ≤ w(T0 )
2008-6-5 [email protected] 44
思考题
1. 教室里有6排椅子，每排5张椅子，每张椅子坐一名学生。 现在班主任老师考虑每周调整一次学生们的座位，使得每个 学生都调到本次调整前与他相邻的某个座位上（前后左右视 为相邻），一个学期内每个
学生都不能调回到他已经坐过的 座位上。请帮老师制定一个调整方案。如果老师现在改变了 主意，希望每次将每个学生调到本次调整前与他不相邻的某 个座位上，且一个学期内每个学生都不能调回到他已经坐过 的座位上。问是否可行？应怎样调整?
2008-6-5
45
思考题
2.若围一张圆桌坐着至少6个人，那么一定可以调整他们的 位置，使得每个人两侧都挨着新邻居 ? 3.下图是某超市的平面示意图，一名保安人员在一次巡逻 中欲穿过每道门一次且仅一次并回到出发点，问他是否能 够做到？试加以解释。
2008-6-5
46
思考题
4.某楼层的平面结构示意图如下。试说明从前门进去经过 每个门口恰好一次且从后门出去是不可能的。
后门
前门
2008-6-5
47
思考题
5.一个博物馆称为设计良好的，如果存在经过每个房间恰 好一次的参观路线。某博物馆的楼层平面设计如下图，试 证明这个博物馆的设计不是良好的。
2008-6-5
48
谢 谢！
49