最优回路(未必是简单回路)。 当G是欧拉图，则最优回路即欧拉回路。 若G不是欧拉图，则通过加边来消除G中的奇度顶点，
要求使加边得到的欧拉图G'中重复边的权和最小。
可编辑ppt
23
周游世界的游戏
1859 哈密尔顿 “周游世界”游戏： 20个城市，每个城市恰游一次，回到出发地
用一个正12面体的20个 顶点代表20个城市，
2） u,v不相邻，向着v方向，取(u,u1)删 (u,u1)，以u1为始，重复过程，直至删 (ui,v)后得到欧拉回路，连上所删除的边，得
到——得到欧拉通路。//
可编辑ppt
14
续例 .“一笔划”问题
G连通，从一个奇度点开始画，图只有0或2 个奇度点，则G可一笔画。//
[定理] 对有向图，G有欧拉回路每一结 点入度等于出度。
则从EG−{e1e2……ei}中选ei+1 选择条件：
i. ei与vi相邻 ii. 对EG−{e1e2……ei}而言非割边优先 3) 重复2)，直到不能执行
可编辑ppt
17
讨论这种情况下，会否出现
EG−{e1e2……ei}中有边，而2)之条件i不 成立的情况：
如 vi = v0，则必有某个j<i时刻选ej+1 边 为割边
[推论] 欧拉图G是以任一顶点为始点的随机欧拉图 当且仅当G本身是一个基本回路)
可编辑ppt
21
中国邮递员问题：
问题：邮递员从邮局出发，走过辖区内每条
街道至少一次，如何选择最短路线？
1）每街一次/至少一次 2）环游最短
可编辑ppt
22
中国邮递员问题-模型
数学模型：
构造无向权图G，以道路为边，路长为权 问题的解——G中包含所有边的回路权最小，称为
欧拉图和哈密尔顿图
信号处理中的数学方法 第2-4讲
可编辑ppt
1
一.欧拉回路：一般不限于简单图，一般指无向
图
Eg. 哥尼斯堡七桥问题
原问题：“右边的图中是否存在包含每条边一次且恰好 一次的回路？”
原问题等价于：欧拉图
A
A
C
D C
D
B
B
可编辑ppt
2
<定义>欧拉回路，欧拉通路
图G的一个回路/通路,它经过G中每条边恰 好一次，则回路/通路称为欧拉回路/通路。
可编辑ppt
24
哈密尔顿图
定义：若图G中有经过所有顶点的基本回路，称为 哈密尔顿回路，若G中含哈密尔顿回路，则称G为 H_图。
可编辑ppt
10
3) 1)：
Z1是划分中的一个基回，若{Z1}=E，则Z1就 欧拉回路，G是欧拉图
否则，存在另一回路Z2与Z1有公共点v 构造简单回路，从v经Z1回到v，再经Z2回到v
将Z1UZ2看作Z1，再重复 上述过程，得到穷尽EG 的简单回路。 ∴G—欧拉图。//
可编辑ppt
11
提示
eg.
可编辑ppt
8
[证] 1)2)3) 1)
1) 2):
设Go为G的欧拉回路，可将Go表示为 v1e1v2e2……envn+1(vn+1=v1)，其中vi的
一次出现总关联于左右2条边，对应度数为2 又Go 的e1，e2，……en互不相同，且穷尽了
所有的边，这样任一点vi的度数为vi在Go中 出现的度数之和——必为2的倍数。//
全部是偶度点的连通图中的回路 若干小回路串成欧拉回路
可编辑ppt
12
续例 多米诺骨牌问题
d
(
vvii)源自VG8∴能构成回路，能够连成首尾圈。//
[定理] 连通图G，若G中仅有0或2个奇 度数点G有欧拉通路。
可编辑ppt
13
<证>
0个奇度数，显然欧拉回路 2个奇度数，u，v，分情况：
1）u,v相邻，删(u,v)余图G’为欧拉图， 从u开始在G’中走欧拉回路，回到u，再 走(u,v)——得到欧拉通路
定义：如果图G中含欧拉回路，则图G称为 欧拉图。
定义：如果图G中仅有欧拉通路，但没有欧 拉回路，则图G称为半欧拉图。
可编辑ppt
3
例 “一笔划”问题——G中有欧拉 通路
可编辑ppt
？
4
实例
上图中，(1) ,(4) 为欧拉图
可编辑ppt
5
例 多米诺骨牌，28块
能否排成一圈使两两相邻的半边的点数相同，问 是否可能？
牌 数 C2728种 7
可编辑ppt
6
将0-6看作7个结点，任2点的边看作一块骨牌 这样,该问题转化为G有无欧拉回路的问题
可编辑ppt
7
[定理]对连通图，下列命题等价
1）G是欧拉图 2）G的每个结点为偶度数 3）G的边集能划分成为基本回路，即
k
边 集 C 1 ,C 2 , ,C k 不 重 叠 之 基 本 回 路 ， 且 U i= 1 C i E G
注，若G是以v为始点的随机欧拉 图，则任何一个以v为始点的不包含G 中所有边的回路都应该能扩充成欧拉 回路。反之，若G不是以v为始点的随 机欧拉图，则一定存在已经包含了v 所关联的所有边，却未包含G中所有 边的简单回路。
可编辑ppt
20
随机欧拉图的判定
[定理] 欧拉图G是以v为始点的随机欧拉图当且仅 当G中任一回路均包含v。
——与2）之ii条件相矛盾，∴不可能 出现，即vi ≠ v0 如vi ≠ v0 ，则vi 的度数为奇数
——与欧拉图相矛盾
可编辑ppt
18
提示：
在画欧拉回路时，已经经过的边不能再用； 在走回路中的任何时刻，将已经经过的边删
除，剩下的边必须仍在同一连通分支当中
×
可编辑ppt
19
随机欧拉图
<定义>G是欧拉图，vVG，从v开始，每一步从当前 点所关联边中随机选边，均可构造欧拉回路，则G称为 以v为始点的随机欧拉图。
可编辑ppt
15
安排国展中心参观路线
A
B
C
I
J
KL
MN
H
O
G
F
参观区域实景
A
B
C
I
J
D
K LM
D N
H
O
E
E
G
F
图G
设E为起始点
E,N,M,O,L,K,I,L,M,J,N可编,D辑p,Cpt ,J,B,I,A,K,H,G,O,F,E 16
<欧拉回路-Fleury算法 >
1) 任取一点v0，置w0=v0 2) 设简单回路wi= v0e1v1e2……eivi 已选定，
可编辑ppt
9
2) 3):
G连通，不妨设G是非平凡图
由2）每个结点度数至少为2，所以G中含一基回 Z1，Z1的度数为偶度数，删去Z1的边得到G’， 原G为偶度数，删去G’的每个点仍为偶度数
除孤立点外其余点至少为2度，即余连通点所图 至少2连通
如法炮制，直至余图不含边 {Z1}，{Z2 }，…..,{Zk }为E的一个划分。 //