第三章 欧拉图和哈密顿图
自荐材料-
第三章
欧拉图与哈密顿图
（七桥问题与一笔画，欧拉图与哈密顿图）
教学安排的说明
< br>章节题目
：
§
3.1
环路；
§
3.2
欧拉图；
§
3.3
哈密顿图
学时分配：
共
2
课时
< br>本章教学目的与要求：
认识七桥问题的实质，
理解一笔画
问题的解决方法，
会正确
理解关于欧拉图和哈密顿图的判断定理
，并进行识别．
其它：
由于欧拉图与
一笔画问题密切相关，因此本章首先从一笔画问题讲起，章节
内容与教材有所不同。
1
课
堂
教
学
方
案
课程名称：
§
3.1
环路；
§
3.2
欧拉图；
§
3.3
哈密顿图
授课时数
：
2
学时
授课类型
：理论课
< br>教学方法与手段
：
讲授法
教学目的与要求
：
认识七桥问题的实质，<
/p>
理解一笔画问题的解决方法，
会正确理解
关于欧拉图和哈密顿图的判断定理，并进行识别．
教学重点、难点：
（
1
）
理解环路的概念；
（
2
）
掌握欧拉图存在的充分必要条件；
（
3
）
理解哈密顿图的一些充分和必要条件；
教学内容：
看图
1
，有点像
“
回
< br>”
字，能不能从某一点出发，不重复地一笔把它画出来？这
就是中国民间古老的一笔画游戏，
而这个图形实际上也是来源于生活。
中国古代量
米用的
“
斗
”?
上下都是四方的，底小口大，从上往下看就是这样的图形。
这类
“
一笔画
”
问题中最著名的当属
“
< br>哥尼斯堡七桥问题
”
了。
一、问题的提出
图
1 <
/p>
哥尼斯堡七桥问题。
18
世纪，哥尼斯堡
为东普鲁士的首府，有一条横贯全市
的普雷格尔河，河中的两个岛与两岸用七座桥联结起
来，见图
2
（
1
）
，当时那里的
居民热衷于一个难题：游人怎样不重复地走遍
七桥，最后回到出发点。
1735
年，
一群执着好奇的大学生写信请教当时正在圣彼得堡科学院担任教授的著名数学家
欧拉。<
/p>
欧拉通过数学抽象成功地解决了这一问题。
欧拉发现欧几里得几何
并不适用
于这个问题，因为桥不涉及
“
大小
”
，也不能用
“
< br>量化计算
”
来解决。相反地，这问题
属于提出的
“
位置几何
”
。
欧拉想到，
岛与河岸陆地仅是桥梁的连接地点
和通往地点，
桥仅是从一地通往另一地的路径，
一次能否不重复
走遍七桥与河岸陆地大小是没有
2
本质联系的，与桥的宽窄也是没有关系的。所以，相对问题而言，可舍弃之，而仅
考虑与
问题有密切联系的本质特征：岛和岸地可以是仅有位置而没有大小的
“
< br>点
”
，
桥梁可以是仅有连接作用
而没有宽窄的连接两点的线，那么可以把这四处地点用
A,B,C,D
< br>四个点来表示，
同时将七座桥表示成连结其中两点的七条线，
就得到这样
一张图．
于是，
欧拉建
立了一个数学模型，一个人不重复地走遍所有的七座桥，就
相当于从图中某一点出发，<
/p>
不重复地一笔画出图来．
这样，
“
七桥问题
”
就转化为
“
一
笔画
”
问
题了。
欧拉注意到，
如果一个图能一
笔画成，
那么一定有一个起点开始画，
也有一个终点。
图上其它的点是
“
过路点
”——
画的时候要经过它。
这些点有什么特征呢？先来看看
“<
/p>
过路点
”
，它应该是
“
有进有出
”
的点，有一条
边进这点，那么就要有一条边出这点，
不可能是有进无出，
如果有进无出，它就是
终点，也不可能有出无进，如果有出无进，它就是起
点。因此，在
“
过路点
”
进出的
边总数应该是偶数。
如果起点和终点是同一点，
那么它也是属于
“
有进有出
”
的点，因此必须连着偶
数条边，这样图上所有点都连偶数条边。
如果起点
和终点不是同一点，
那么这两点连有奇数条边，这也是图中仅有的连
着奇数条边的点。
现在
对照七桥问题的图，
B
点连有
3
条边，
A
点连有
5<
/p>
条边，
C
点
D<
/p>
点各连
3
条边，哥尼斯堡七桥问题就变成
了图
2(2)
中，是否存在经过每条边一次且仅一次，
经过所有的顶点的闭链问题了。所以欧拉得出的结论是这个图肯定不能一笔画成，
也就是说要想不重复的走遍这七座桥是不可能的。
1736
年瑞士数学家欧拉
（
Euler
）
发表了图论的第一篇
论文
“
哥尼斯堡七桥问题
”
。
欧拉在论文中指出，这样的闭链
是不存在的。
图
2
3
欧拉解决问题的关键是两步，<
/p>
先从实际问题中抽象出形式结构，
再对形式结构
< br>进一步分析，
抽象出其本质数量特征，由此得出判别准则，问题获得答案。哥尼斯
堡七桥问题的解决远远超出了它的娱乐价值，欧拉用了最简单的图形
——
点和线，
把一个实际问题抽象成数学问题，
巧妙地彻底解决了
“
七桥问题
”
。
这充分显示了数
学抽象的形式
化和量化特征。
由此提出的新思想开辟了数学的一个新的领域
—
—
图
论，
同时也为拓扑学的研究提供了
一个初等的例子。
此后许多著名的数学游戏成为
图论和拓扑学发
展的催化剂和导引，
如哈密顿问题
（绕行世界问题）
、
四色猜想等。
直到<
/p>
20
世纪中期，这两门学科才逐步完善并迅速发展。
二、欧拉图
定义
1
<
/p>
给定图
G
=<
V
，
E
>
，通过
G
中的每一条边一次且恰好一次的闭链，称
为欧拉闭链。存在欧拉闭链的图称为欧拉图。
欧拉图另一
定义：如果图
G
的所有点均为偶数，则称图
G
为欧拉图。
实际上，
在图中，
如果所有的边可以排起来而不重复，
则
该图为一链，
或者是开链，
或者是闭链，当是开链时，
链中的点为偶数度，
起点和终点皆为奇数度。当是闭链
< br>时，链中的点皆为偶数度。
定理
1
：无向图
G
为欧拉图当且仅当
G
连通，并且所有顶点的度都是偶数。
证明：设
G
为一欧拉图，那么
G
显然是连通的。另一方面，由于
G
本身为一
闭路径，它每经过一个顶点一次，便给
这一顶点增加度数
2
，因而各顶点的度均为
该路径经历此顶点的次数的两倍，从而均为偶数。反之，设
G
连通，且每个顶点
的度均为偶数，欲证
G
为一欧拉图。为此，对
G
的边数归纳。当
< br>m
= 1
时，
G
必
定为顶点的环，
如图
3<
/p>
（
a
）
所示，<
/p>
显然这时
G
为欧拉图。
< br>设边数少于
m
的连通图，
在顶点
度均为偶数时必为欧拉图，现考虑有
m
条边的图
G
。设想从
G
的任一点出
发，
沿着边构画，
使笔不离开图且不在构画
过的边上重新构画。
由于每个顶点都是
偶数度，
笔在进入一个顶点后总能离开那个顶点，
除非笔回到了起点。
< br>在笔回到起
点时，
它构画出一条闭路径，
记为
H
。
从图
G
中删去
H
的所有边，
所得图记为
G’
，
G
’
未必连通，但其各顶点的度数仍均为偶数（为什么？）
。考虑
G
的各连通分支，
由于它们都连通，顶
点度数均为偶数，而边数均小于
m
，因此据归纳假设，它们
都是欧拉图。此外，由于
G
连通，它们都与
H
共有一个或若干个公共顶点（如图
3
（
b
）所示）
，
因此，它们与
H
一起构成一个闭路径
。
这就是说，
G
是一个欧拉图。
4
(a)
(b)
图
3
三、
一笔画问题。
< br>要求笔不离纸，
而且每条线只画一次，
不准重复。
显然哥尼斯堡七桥问题是一笔画
问题。对于图来说，如果全部边（或有
向边）可以排成一条链，则称这个图为一个
一笔画。
下列图形能否一笔画成
?
图
4
定理<
/p>
2
设
G
是无向连
通图，则
G
是一笔画
G
中只有
0
或
2
个奇数度顶点（他们
分别是起点和终点）
。即：
即全为偶数度，闭链，欧拉图
奇数顶点的个数为
0
一笔画
奇
数顶点的个数为
2
开链
证明：设
G
的链是点边序列
v
0
e
1
v<
/p>
1
e
2
v
2
v
k
1
e
k
v
k
，其中顶点可能重复，但边不重复。
对于任一非端点顶点
v
i
，在欧拉路中每当
v
i<
/p>
出现一次，必关联两条边，故
v
i
虽可重
复出现，
但是
deg
v
i
必是偶数。对于端点
,
若
v
0
v
k
，则
d
e
< br>g
v
0
必是偶数，
即
G
< br>中
无奇数度顶点
。若
v
0<
/p>
v
k
，则
deg
v
0
必是奇数，
deg
v
k
必
是奇数
,
即
G
中有两
个奇数度顶点
。上述定理的逆定理也成立，即：
定
理
3
：
设
G<
/p>
是无向连通图，
G
中只有
0
或
2
个奇数度顶点
G
是一笔画。此定
理分两步证：奇数度顶点是
0
，奇数度
顶点是
2
。
证明思路：只证明奇数度顶点是
0
的
情形，
(
证明过程给出了一种构造方法
)
（
1
）
首先证明任取
G
中点
< br>v
0
，
必存在包含
v
0
的圈。
由于
G
中点为偶数度
,
则从<
/p>
其中一个顶点开始构造一条圈
,
即从
v
0
出发经关联边
e
1
进入
v
1
,
则必可由
v
1
再经关联
5
边
e
2
进入
v
2
,
如此下去
,
每边仅取一次
,
必存在到达
v
0
的圈
,
v
0
e
1
v
1
e
2
v
2
与
G
中点为偶数度矛盾）
（
2
）若
P:
v
0
e
1
v
1
e
2
v
2
一条闭链。
（
3
）
否则，若
G
中去掉
P:
v
0
e
1
v
1
e
2<
/p>
v
2
v
k
1
e
k
v
0
（否则便
v
k
1
e
k
v
0
就是
v
k
1
e
k
v
0
通过了
G
的所有边
, P:
v
0
e
1
v
1
e
2
< br>v
2
v
k
1
e
k
v
0
后得到子图
G
,
则
G
中每个顶点
v
k
1
e
k
v
0
与
G
至少有一个
度数都为偶数
,
因为原来的图
G
是连通的
,<
/p>
故
P:
v
0<
/p>
e
1
v
1
e
2
v
2
顶点
v
i
重合
,
在
G
中由
v
i
出发重复
(1)
的方法
,
得到闭链
L
。
(4)
当
P
与
L
组合
,<
/p>
若恰是
G
,
得欧
拉路
,
否则重复
(3),
可得闭链
M,
依此类推可得
一条欧拉路。
奇数度顶点是
2
的情形可类似证明。
因此，定理
2
与
3
可总结为
设
G
是无向连通图，
G
中只有
0
或
2
个奇数度顶点
G
是一笔画。
例
1
：下列图
5
中各图是否可以一笔画出？
图
5
解：
(1)
有
个奇度顶点，无欧拉闭链或通路，不能一笔画成。
个奇度顶点，
其余均为偶度顶点，
具有欧拉通路，
可一笔画成。
(2)
与
(
3)
都是
(4)
均为偶度顶点，具有欧拉通路，可一笔画成。
例
2
、
“
两只蚂蚁比赛问
题
”
。
两只蚂蚁甲、
< br>乙分别处在图
6
左图
最后到达顶点
解：
图
中的顶点
处，
并设图中各边长度相等。
甲提出同乙比赛：
从它们所在顶点出
发，
走过图中所有边
处。如果它们速度相同，问谁最先到达目的
地？
，因此存在从
到
的开链，蚂蚁乙走到
只
，至少要先
中，有两个奇度顶点
< br>
要走一条欧拉通路，边数为
一条边到达
，而蚂蚁甲要想走完图中所有边到达
条边到达
，再走一条欧拉通路，故它至少要走
，所以乙必胜。
6
例
3:
甲
乙两个邮递员去送信，两人以同样的速度走遍所有的街道，
甲从
A
点出发，
乙从
B
点出发，最后都回到邮局（
C
点）。如果要选择最短的线路
，谁先回到邮
局？
图中
A
，
C
为奇点，其余都是偶
点。甲从
A
点出发，可以不重复到达
C
点。
乙从
B
出
发一定会走重复的路，所以甲先回到邮局。
例
4
图
6
右图是一个公园的平面
图，能不能使游人走遍
每一条路不重复？入口和出口又应
设在哪
儿？
H
点和
B
点是奇点，其余都是
偶点，
所以入后
和出口应设在
H
点
和
< br>B
点。
图
6
四、中国邮递员问题
一名邮
递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮
件后又返回邮局．<
/p>
如果他必须至少一次走过他管辖范围内的每一条街道，
如何选择<
/p>
投递路线，
使邮递员走尽可能少的路程．
这个问题是由我国数学家管梅谷先生
（山
东师范大学数学系教授
）在
1962
年首次提出的，因此在国际上称之为中国邮递员<
/p>
问题．
用图论的述语，在一个连通的赋权
图
G
（
V
，<
/p>
E
）中，要寻找一条闭链，使该
闭链包含
G
中的每条边至少一次，且该闭链的权数最小．也就是说要从包
含
G
的
每条边的闭链中找一条权数最小
的闭链．
如果
G<
/p>
是欧拉图，则很容易由弗罗莱算法求出一个欧拉闭链，但是若
G<
/p>
不是
欧拉图，
即存在奇度数的顶点，
则中国由递员问题的解决要困难得多．
本节的主要
< br>目标是给出在有奇度数顶点的连通图中寻找最小权数的闭链的方法．
首先注意到，若图
G
有奇数度顶点，则
G
的奇数度顶点必是偶数个．把奇数
度顶点
分为若干对，每对顶点之间在
G
中有相应的最短路，将这些最短
路画在一
起构成一个附加的边子集
E
．令
G
/
<
/p>
=G+E
/
，即把附加边子集
E
/
叠加在原图
G
上
形成一个多重图
G
/
，这时
G
/
中连接两个顶点之间的边不止一条．显然
G
< br>/
是一个欧
7
拉图，因而可以求出
G
/
的
欧拉闭链．该欧拉闭链不仅通过原图
G
中每条边，同时
还通过
E
/
中的每条边，
且均仅一次．
邮递员问题的难点在
于当
G
的奇数度顶点较
多时，可能有很
多种配对方法，应怎样选择配对，能使相应的附加边子集
E
/<
/p>
的权
数
ω(E
/
)
为最小？为此有下列定理．
定理
4
设
G
（
V
，
E
）
为一个连通
的赋权图，
则使附加边子集
E
/
的权数
ω(E
/<
/p>
)
为最小的充分必要条件是
G+E
/
中任意边至多重复一次，
且
G+E
/
中的任意闭链中
重复边的权数之和不大于该闭链总权数的一半．
证明：
必
要性．用反证法．设存在一种奇顶点集的配对，使其附加边子集
E
/
权数
ω(E
/
)
为最小．若
G+E
/
中
有一条边重复
n
(
n
< br>
2
)
次，
由于
G+E
/
为欧拉图，所
以删去相应的二次重复边后仍为欧拉图．这样，相应的附加边子集的权数将减小，
这与
ω(E
/
)
为最小的假设矛盾．这说明
E
< br>/
中的边均互不相同．
其次，
若
G+E
/
中存在一个闭链，
使它的重复边的权数之和大于该闭链总权数<
/p>
的一半，则在
E
/
中删去这些重复边（注意：这些边均在
E
< br>/
中）
，而代之以该闭链
的其余
部分的边再重复一次．经过这种替代后所得到的边子集
E
//<
/p>
仍为附加子集，
且
ω(E
//
)<ω(E
/
)
，又产生矛盾．
充分性．设有两个附加边子集
E
/
和
E
//
，均使
G+E
/<
/p>
和
G+E
//
中
每条边至多重复
一次，且每个闭链中的重复边的权数和不大该闭链权数的一半，我们来证
明
ω(E
/
)=ω(E
//
)
．
首
< br>先
注
意
到
，
由
E
/
和
E
//
不
相<
/p>
同
的
部
分
组
成
的
图
（
记
为
G
[
E
/
E
//
（
E
/
E
//
）
]
）是由一个或若干个欧拉子图所组
成的．这是因为
E
/
＋
E
//
中
每
< br>个
顶
点
的
度
数
均
为
偶
数
，
而
E
/
和
E
//
的
公
共
边
数
也
是
偶
数
，
故
所以它若为连通图时是
一个欧
G
[
E
/
E
//
（
E
/
E
//
）
]
中每个顶点的度数仍为偶数，
拉图；若为非连通图时则由若干个欧拉子图
组成．
G
[
E
/
E
//
（
E
/
E
//
）
]
的任何闭链都由
E
/
和
E
//
中的边组成
，而
E
/
和
E
//
在闭链
中的权数分别不大于该闭链
权数的一半，因而任何闭链中属于
E
/
中的权数之和与
属于
E
//
中的边数之和必定相等，
所以
ω(E
/
)=ω(E
//
)
．
它就是最优附加边子集的权数，
即
E
/
和
E
//
均为使附加边子集的权数达到最小的最优附加边子集．
< br>
由定理
4
可
得一个寻找邮递员问题最优解的方法．现举例如下：
8