Gk＝G-{e1,e2,…,ei}中的桥；
3. 当Gk为零图时，算法结束；否则，返回2。
2020/5/11
计算机学院
14
例13-1.5
在右图所示的欧拉图中，某 人用算法求Ｇ中的欧拉回路时，
v1
走了简单的回路：
e8
v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2
G-E（C）仍然无奇数度结点。
?
由于G是连通的，C中应至少存在一点v，使G-
E（C）中有一条包含v的回路C′。（见示意图）
2020/5/11计算机学院7Cv
C'
这样，就可以构造出一条由C和C′组成的 G的回路，其包含的边数比C多，与假设矛盾。 因此，C必是Euler回路，结论成立。
2020/5/11
冯伟森
Email：fws365@ 2020年5月11日星期一
主要内容
Euler图及其应用
① 欧拉道路（回路）的定义 ② 如何判别欧拉图 ③ 一个图含有欧拉道路的条件 ④ 连通有向图G中含有有向欧拉道路和回路的充
要条件 ⑤ Fleury算法 ⑥ Euler图的应用(中国邮递员问题算法)
证明： “”
由于在回路C 中边不可能重
设G是Euler图，则G必然存复在出一现条包含所有边
（也包含所有结点）的回路C，对uV，u必然在
C中出现一次（可出现多次），每出现u一次，都
关联着G中的两条边，而当u又重复出现时，它又
关联着G中的另外的两条边，（为什么？）
因而u每出现一次，都将使得结点u的度数增
2020/5/11
计算机学院
4
例13-1.1
v1
v2
v5
v3 v4 a)
v1
v1
v2
v5
v4
v3 v4 b)
v2 c) v3
图a是欧拉图；图b不是欧拉图，但存在欧拉道 路；图c不存在欧拉道路。
2020/5/11
计算机学院
5
定理13-1.1 无向连通图G＝<V，E>是欧拉图当
且仅当G的所有结点的度数都为偶数。
V2
V5 V2
现V在5 ，我们是
不是已经解决
V3
V4
(a)
V3
了V哥桥4 尼问斯题V2 堡？七
V3
(b)
(c)
由定理13-1.1及推论13-1.1.1容易看出：
a) 是欧拉图； b) 不是欧拉图，但存在欧拉道路； c) 既不是欧拉图，也不存在欧拉道路。
2020/5/11
计算机学院
10
有向图的欧拉道路、欧拉图
类似于无向图的讨论，对有向图我们有以下 结论： 定理13-1.2 ⅰ）有向连通图G含有有向欧拉道路，当且仅当
除了两个结点以外，其余结点的入度等于出度， 而这两个例外的结点中，一个结点的入度比出 度大1，另一个结点的出度比入度大1。 ⅱ）有向连通图G含有有向欧拉回路，当且仅当G 中的所有结点的入度等于出度。
“”
路的端点。
⑴若 G没有奇度数结点，则结论显然成立；
⑵若G有两个奇度数结点u和v，则G+uv是Euler图，从而
存在Euler回路C。从C中去掉边uv，则得到一条简单
道路L（起点u和终点v），且包含了G的全部边，即L是
一条Euler道路。
2020/5/11
计算机学院
9
例13-1.2
V1
V1
V1
V4
计算机学院
8
推论13-1.1.1非平凡连通图G＝<V，E>含有欧拉道 路当且仅当G仅有零个或者两个奇数度结点。
证明：“” 设G具有一注意条：Eu若le有r道两路个L奇，则在L中除起 点和终点外，其余每个度结数点结都点与，偶则数它条们边相关联，所
以，G中仅有零个（Eule是r回G路中）每或条者欧两拉个通奇数度结点。
同样，有向Euler图的结点度数都为偶数；含有有 向Euler道路的图仅有零个或者两个奇度数结点。
2020/5/11
计算机学院
11
例13-1.3
V2
V2
V1
V2
V3
V1
V3 V1
V3
V8
V4
V4
V4
V7
V6
V5
(a)
(b)
(c)
▪ 图a)存在一条的欧拉道路：v3v1v2v3v4v1；
▪ 图(b)中存在欧拉回路v1v2v3v4v1v3v1，因而(b) 是欧拉图；
设G＝<V，E>是一个欧拉图 即如果ei+1是割
1. 任取v0∈V，令P0＝v0；
边，同时还有其 它边与vi相关联，
2. 设P0＝v0e1v1e2…eivi，按下则面不的能方选法ei+从1
GK=E-{e1,e2,…,ei}中选取ei+1：
1) ei+1与vi相关联；
2) 除非无别的边可选取，否则ei+1不应该为
2020/5/11
计算机学院
2
哥尼斯堡七桥问题
哥尼斯堡城市有一条横贯全城的普雷格尔(Pregel) 河，城的各部分用七座桥联接，每逢假日，城中居民进 行环城逛游，这样就产生了一个问题：能不能设计一次 “遍游”，使得从某地出发对每座跨河桥只走一次，而 在遍历了七桥之后却又能回到原地？
A
b1
b2
b5
C
加2度，若u在通路中重复出现j次，则deg(u)＝2j。
即u的度数必为偶数。
2020/5/11
计算机学院
6
“”
设连通图G的结点的度数都是偶数，则G必
含有简单回路（可对结点个数进行归纳证明） 。
设C是一条包含G中边最多的简单回路：
⑴ 若C已经包含G中所有的边，则C就是Euler回
路，结论成立。
⑵ 若C不能包含G中所有的边，则删边子图 Why
b(乙)
a(甲) c
解
，仅有两个度数为奇数的结点b，c，因而存
在从b到c的欧拉通路，蚂蚁乙走到c只要走一条欧拉通路，
边数为9条。而蚂蚁甲要想走完所有的边到达c，至少要
先走一条边到达b，再走一条欧拉通路，因而它至少要走
10条边才能到达c，所以乙必胜。
2020/5/11
计算机学院
13
Fleury算法（构造Euler回路）
b6
D
b3
b4 b7
2020/5/11
B
计算机学院
3
Euler图
定义13-1.1 设G是一个无孤立结点的图，包含
G的每条边的简单道路（回路）称为该图的一条
欧拉道路（回路）。具有欧拉回路的图称为欧
拉图。 规定平凡图为欧拉图。
为什么？
显然，每个欧拉图必然是连通图。
因此，一条欧拉道路（回路）是经过图中每 边一次且仅一次的道路（回路）。
▪ 图 (c) 中 有 欧 拉 回 路 v1v2v3v4v5v6v7v8v2v4v6v8v1 因而(c)是欧拉图。
2020/5/11
计算机学院
12
例13-1.4
甲、乙两只蚂蚁分别位于右图 中的结点a，b处，并设图中的边长 度是相等的。甲、乙进行比赛：从 它们所在的结点出发，走过图中的 所有边最后到达结点c处。如果它们 的速度相同，问谁先到达目的地？