第五章 欧拉图与哈密顿图
主要内容 z 欧拉图 z 哈密顿图 z 带权图与货郎担问题
1
七桥问题
K?nigsberg, River Pregel, (Kaliningrad, Russia)
2
2013/4/8
Leonhard Euler(1707~1783)
瑞士数学家, 最多产的数学家
3
2013/4/8
Euler的解法
1736年, 图论和拓扑学诞生
c A a
4
C d eg b f B D
2013/4/8
一笔画
5
2013/4/8
欧拉通路(Euler trail)
经过图中所有边的简单通路
6
2013/4/8
半欧拉图(semi-Eulerian)
有欧拉通路的图
7
2013/4/8
欧拉回路(Euler tour/circuit)
经过图中所有边的简单回路
8
2013/4/8
欧拉图(Eulerian)
有欧拉回路的图
9
2013/4/8
欧拉图实例
上图中，(1) ,(4) 为欧拉图，(2),(5)为半欧拉图，(3),(6)既不是 欧拉图，也不是半欧拉图. 在(3),(6)中各至少加几条边才能成 为欧拉图 为欧拉图？
10
无向欧拉图的判别法
定理5.1 无向图G是欧拉图当且仅当G连通且无奇度数顶点.
11
证明 证明： ?： G有欧拉链(v0, e1, v1, e2, …, ei, vi, ei+1, …, ek, vk), v0=vk. 其中顶点可以重复出现，而边不重复出现。所以对 其中顶点可以重复出现 而边不重复出现 所以对 于任意vi，每当出现vi，它关联两条边，而vi可以重复出 现，所以d(vi)是偶数。
?：若图G是连通的，则可以构造一条欧拉链： (1)从任 从任一顶点 顶点v0开始，取关联于 开始 取关联于v0的边e1到v1，每边 每边 仅取一次。因为所有顶点为偶数度，并且G是连通的 ，所以可以继续取关联与 所以可以继续取关联与v1的边e2到v2，……，直到 直到 回到顶点v0，得到一条闭链h:(v0, e1, v1, …, v0)。 (2)若h=G，则 则G即为欧拉图；否则 即为欧拉图 否则G-h=h’ G h=h’不是空集， 不是空集 h’中顶点度数均为偶数，又G是连通的，h’与h必有 一个顶点 个顶点vi重合。在 重合 在h’中从vi出发重复(1)，得到一条 得到 条 闭链h2:(vi, e1’, v1’, …, vi) (3)若h∪h’=G，则 则G即为欧拉图: (v0, e1, v1, ……, vi, e1’, v1’, …, vi,……,v0)；否则，重复(2)直至构成一条 包含G中所有边的闭链。 中所有边的闭链
从以上证明不难看出：欧拉图是若干个边不重的圈之 并 见示意图3. 并，见示意图 3
PLAY
14
欧拉图的判别法
定理5.2 无向图G是半欧拉图当且仅当G 连通且恰有两个奇 度顶点. 证 必要性简单. 充分性（利用定理15.1） 设u,v为G 中的两个奇度顶点，令 G ′ =G∪(u,v) 则G ′ 连通且无奇度顶点，由定理5.1知G ′为欧拉图，因而 存在欧拉回路C，令 令 Γ=C?(u,v) 则Γ 为 G 中欧拉通路.
15
有向欧拉图的判别法
定理5.3 有向图D是欧拉图当且仅当D是强连通的且每个顶 点的入度都等于出度. 本定理的证明类似于定理5.1. 定理5.4 有向图D是半欧拉图当且仅当D是单向连通的，且 D中恰有两个奇度顶点，其中 中恰有两个奇度顶点，其中一个的入度比出度大 个的入度比出度大1，另 ，另一个 个 的出度比入度大1，而其余顶点的入度都等于出度. 本定理的证明类似于定理5.1. 定理5.5 G是非平凡的欧拉图当且仅当G是连通的且为若干 个边不重的圈之并. 可用归纳法证定理5.5. 55
16
5.2 哈密顿图
历史背景：哈密顿周游世界问题与哈密顿图
(1)
(2)
17
哈密顿图与半哈密顿图
定义5.2 (1) 哈密顿通路——经过图中所有顶点一次仅一次的通路 经过图中所有顶点 次仅 次的通路. (2) 哈密顿回路——经过图中所有顶点一次仅一次的回路. (3) 哈密顿图——具有哈密顿回路的图. (4) 半哈密顿图——具有哈密顿通路且无哈密顿回路的图. 几点说明 几点说明： 平凡图是哈密顿图. 哈密顿通路是初级通路 哈密顿回路是初级回路. 哈密顿通路是初级通路，哈密顿回路是初级回路 环与平行边不影响哈密顿性. 哈密顿图的实质是能将图中的所有顶点排在同一个圈上
18
实例
在上图中， (1) (2) 是哈密顿图; (1),(2) (3)是半哈密顿图; (4)既不是哈密顿图，也不是半哈密顿图，为什么？ 既不是哈密顿图 也不是半哈密顿图 为什么？
19
无向哈密顿图的一个必要条件
定理5.6 设无向图G=
20
第三章欧拉图与哈密顿图 （七桥问题与一笔画，欧拉图与哈密顿图） 教学安排的说明 章节题目：§3.1环路；§3.2 欧拉图；§3.3 哈密顿图 学时分配：共2课时 本章教学目的与要求：认识七桥问题的实质，理解一笔画问题的解决方法，会正确理解关于欧拉图和哈密顿图的判断定理，并进行识别． 其它：由于欧拉图与一笔画问题密切相关，因此本章首先从一笔画问题讲起，章节内容与教材有所不同。
课堂教学方案 课程名称：§3.1环路；§3.2欧拉图；§3.3哈密顿图 授课时数：2学时 授课类型：理论课 教学方法与手段：讲授法 教学目的与要求：认识七桥问题的实质，理解一笔画问题的解决方法，会正确理解关于欧拉图和哈密顿图的判断定理，并进行识别． 教学重点、难点： （1）理解环路的概念； （2）掌握欧拉图存在的充分必要条件； （3）理解哈密顿图的一些充分和必要条件； 教学内容： 看图1，有点像“回”字，能不能从某一点出发，不重复地一笔把它画出来？这就是中国民间古老的一笔画游戏，而这个图形实际上也是来源于生活。中国古代量米用的“斗”?上下都是四方的，底小口大，从上往下看就是这样的图形。 这类“一笔画”问题中最著名的当属“哥尼斯堡七桥问题”了。 一、问题的提出图1 哥尼斯堡七桥问题。18世纪，哥尼斯堡为东普鲁士的首府，有一条横贯全市的普雷格尔河，河中的两个岛与两岸用七座桥联结起来，见图2（1），当时那里的居民热衷于一个难题：游人怎样不重复地走遍七桥，最后回到出发点。1735年，一群执着好奇的大学生写信请教当时正在圣彼得堡科学院担任教授的著名数学家欧拉。欧拉通过数学抽象成功地解决了这一问题。欧拉发现欧几里得几何并不适用于这个问题，因为桥不涉及“大小”，也不能用“量化计算”来解决。相反地，这问题属于提出的“位置几何”。欧拉想到，岛与河岸陆地仅是桥梁的连接地点和通往地点，桥仅是从一地通往另一地的路径，一次能否不重复走遍七桥与河岸陆地大小是没有
第十五章欧拉图与哈密顿图 15.1 欧拉图 (2) 一、欧拉通路、欧拉回路、欧拉图、半欧拉图的定义 (3) 二、判别定理 (4) 三、求欧拉图中欧拉回路的算法 (6) 1．Fleury算法，能不走桥就不走桥： (6) 2．逐步插入回路法 (7) 四、中国邮路问题 (8) 练习题： (9) 15.2哈密顿图 (11) 一、哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图的定义 (12) 二、哈密顿图与半哈密顿图的一些必要与充分条件 (12) 练习题 (18) 15.3 带权图与货郎担问题 (24) 一、带权图 (24) 二、货郎担问题 (24)
15.1 欧拉图 主要内容： 1. 欧拉通路、欧拉回路、欧拉图、半欧拉图的定义。 2. 判别定理。 3. 求欧拉图中欧拉回路的算法。 学习要求： 1. 深刻理解欧拉通路与欧拉回路的定义以及它们的区别与联系。 2. 以无向欧拉图为例，进一步理解欧拉图的结构，即，欧拉图是若干个边不重的圈之并。 让我们先从两个例子出发，获得有关图的一些直观认识。 图论的研究起源于哥尼斯堡七桥问题。哥尼斯堡城位于Pnsel河畔，河中有两个岛，有7座桥与4块陆地彼此相连，如上图所示。 居住于该城的居民想做这样的游戏：从4块陆地的任一块出发，经过每座桥一次且仅一次，最后返回原出发地。当地的人们进行了许多次尝试，都没有成功。后来，欧拉给出了问题的解。首先欧拉将4块陆地表示成4个结点，凡陆地间有桥相连的，便在两点间连一条边，从而可将左图改画为右图如下：这样，哥尼斯堡七桥问题可描述为：能否有从A、B、C、D任一点出发，经过每条边一次且仅一次而返回出发点的回路? 欧拉证明了这样的回路是不存在的。他的理由是，从图任一点出发，要回到原出发点，要求与每个点关联的边的数目为偶数，才能保证从一条边进入某点再从另一条边出去，一进一出才能回到原出发点。而图中的顶点A、B、C和D均有奇数条边与其相关联，显然这样的回路是不存在的。 另一个例子是20世纪40年代的一个数学游戏。
欧拉图与哈密顿图
Euler and Hamilton Graph
高晓沨 (Xiaofeng Gao)
Department of Computer Science Shanghai Jiao Tong Univ.
2016/12/6
欧拉道路与欧拉回路
Euler Path and Euler Circuit
IntroductionToCS--Xiaofeng Gao
3
目录
1 欧拉道路与欧拉回路 2 哈密顿道路与哈密顿回路
2016/12/6
IntroductionToCS--Xiaofeng Gao
2
欧拉回路
【定义】给定无向连通图G=(V, E)，包含 图G的所有边的简单道路称为欧拉道路(或 欧拉通道、欧拉迹) ， 包含图G的所有边的简单回路称为欧拉回路 (或欧拉闭迹) 。 假设G没有孤立点，若G含有欧拉回路，则 称G是欧拉图。
2016/12/6
IntroductionToCS--Xiaofeng Gao
4
欧拉图定理
【定理】图G是欧拉图的充要条件是G连通 且没有奇点。
【证】必要性 ： 若G中有欧拉回路C,则C过每一条边有且仅 有一次。对任一节点v,如果C由ei进入v, 则 一定通过另一条边ej从v离开。因此v的度是 偶数。
2016/12/6
IntroductionToCS--Xiaofeng Gao
5
证明(3)
G1可能是非连通图，每个顶点的度保持为 偶数。这时，G1中一定存在某个度非零的 节点vi，同时也是C中顶点。否则C的顶点 与G1的顶点之间无边相连，与G是连通图矛 盾。同理，从vi出发，G1中所在的连通分量 内存在一条简单回路C1。C ∪ C1仍然是G 的一条简单回路，但它包括的边数比C多。 继续构造，最终有C’=C ∪ C1 ∪… ∪ Ck是 一条欧拉回路。
2016/12/6
IntroductionToCS--Xiaofeng Gao
7
证明(2)
充分性 ：由于G是有穷图，因此可断定从 G的任一节点v0出发一定存在G的一条简单 回路C。这是因为各节点的度都是偶数，所 以这条简单回路不可能停留在v0以外的某个 节点，而不能再向前伸延以构成闭通道C。
如果E=C, 则C就是欧拉回路，充分性得证。 否则在G中删去C的各边，得到G1=G―C。
2016/12/6
IntroductionToCS--Xiaofeng Gao
6
范例
【例】 判断下图是否欧拉图：
a
b
e
d
c
G
a
b
d
c
H
2016/12/6
IntroductionToCS--Xiaofeng Gao
8