当前位置：文档之家 › 第15章 欧拉图与哈密顿图

第15章 欧拉图与哈密顿图

  • 格式：ppt
  • 大小：8.96 MB
  • 文档页数：42

下载文档原格式

  / 42

合集下载

欧拉图与哈密顿图

欧拉图与哈密顿图
哈密顿回路。
.
欧拉图与哈密顿图 1.2 哈密顿图及哈密顿通路
➢ 定义8.21
图G称为可2-着色（2-chromatic），
如果可用两种颜色给G的所有顶点着色， 使每个顶点着一种颜色，而同一边的两端点 必须着不同颜色。
.
欧拉图与哈密顿图 1.2 哈密顿图及哈密顿通路
✓ 定理8.16
设图G是可2-着色的。如果G是哈密顿 图，那么着两种颜色的顶点数目相等；如 果G有哈密顿通路，那么着两种颜色的顶点 数目之差至多为一。
✓定理8.14
设图G为具有n个顶点的简单无向图，如果G的 每一对顶点的度数之和都不小于n – 1 ，那么G中有 一条哈密顿通路；如果G的每一对顶点的度数之和 不小于n，且n≥3，那么G为一哈密顿图。
.
欧拉图与哈密顿图 1.2 哈密顿图及哈密顿通路
✓ 定理8.15
当n为不小于3的奇数时，
Kn上恰有 n 1 条互相均无任何公共边的 2
离散数学导论
.
欧拉图与哈密顿图 1.1欧拉图与欧拉路径
➢ 定义8.19
图G称为欧拉图（Euler graph），
如果图G上有一条经过G的所有顶点、所有
边的闭路径。图G称为欧拉路径（Euler
walk），如果图G上有一条经过G 所有顶点、所有边的路径。
.
欧拉图与哈密顿图 1.1欧拉图与欧拉路径
✓ 定理8.11
.
欧拉图与哈密顿图 1.2 哈密顿图及哈密顿通路
➢ 定义8.20
无向图G称为哈密顿图（Hamilton graph），
如果G上有一条经过所有顶点的回路
（也称这一回路为哈密顿回路）。称无向图有哈密顿 通路(非哈密顿图)，如果G上有一条经过所有顶点的

欧拉图与哈密顿图演示文稿

欧拉图与哈密顿图演示文稿
欧拉回路: 通过图中所有边一次并且仅一次行遍所有顶点 的回路。
欧拉图: 具有欧拉回路的图; 半欧拉图:具有欧拉通路而无欧拉回路的图。
第6页，共40页。
举例
欧拉图
半欧拉图
无欧拉通路
欧拉图
无欧拉通路
无欧拉通路
第7页，共40页。
无向欧拉图的判定定理
定理15.1 无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。 定理15.2 无向图G是半欧拉图当且仅当G是连通的，且G中恰有两个奇度 顶点。
(3)是半哈密顿图。 (4)既不是哈密顿图，也不是半哈密顿图。
第24页，共40页。
定理15.6
定理15.6 设无向图G＝<V,E>是哈密顿图，对于任意V1V，且V1≠，均 有 p(G-V1)≤|V1| 其中，p(G-V1)为G-V1的连通分支数。
证明 设C为G中任意一条哈密顿回路， 易知，当V1中顶点在C上均不相邻时， p(C-V1)达到最大值|V1|， 而当V1中顶点在C上有彼此相邻的情况时， 均有p(C-V1)＜|V1|，所以有 p(C-V1)≤|V1|。 而C是G的生成子图，所以，有p(G-V1)≤p(C-V1)≤|V1|。
设图为G3。G3＝<V1,V2,E>，其中 V1＝{a,c,g,h,e}，V2＝{b,d,i,j,f}， G3中存在哈密顿回路。 如 abcdgihjefa， 所以G3是哈密顿图。
第28页，共40页。
例15.3的说明
哈密顿通路是经过图中所有顶点的一条初级通路。 哈密顿回路是经过图中所有顶点的初级回路。 对于二部图还能得出下面结论：
第17页，共40页。
求欧拉图中欧拉回路的算法
Fleury算法，能不走桥就不走桥
(1) 任取v0∈V(G)，令P0＝v0。 (2) 设Pi＝v0e1v1e2…eivi已经行遍，按下面方法来从

离散数学课件15欧拉图与哈密顿图

离散数学课件15欧拉图与哈密顿图
证明 若G是平凡图，结论显然成立。
下面设G为非平凡图，设G是m条边的n阶无 向图，
并设G的顶点集V＝{v1,v2,…,vn}。 必要性。因为G为欧拉图，所以G中存在欧 拉回路，
设C为G中任意一条欧拉回路，vi,vj∈V， v2i0,2v0/7j/都23 在C上，
定理15.1的证明
充分性。由于G为非平凡的连通图可知，G中边数 m≥1。
2020/7/23
半欧拉图的判定定理
定理15.2 无向图G是半欧拉图当且仅当G是连通的 ，且G中恰有两个奇度顶点。
证明 充分性。设G的两个奇度顶点分别为u0和v0， 对G加新边（u0,v0），得G ＝G∪(u0,v0)， 则G 是连通且无奇度顶点的图， 由定理15.1可知，G 为欧拉图， 因而存在欧拉回路C ，而C＝C -(u0,v0)为G中一 条欧拉通路， 所以G为半欧拉图。
并2行从020/7遍/C23 上G 的i中某的顶欧点拉vr回开路始C行遍i，，i＝每1遇,2,到…v,s*j，i，最就后
半欧拉图的判定定理
定理15.2 无向图G是半欧拉图当且仅当G是连通的 ，且G中恰有两个奇度顶点。
证明 必要性。设G是m条边的n阶无向图，因为G为 半欧拉图， 因而G中存在欧拉通路(但不存在欧拉回路)， 设Г＝vi0ej1vi1…vim-1ejmvim为G中一条欧拉通路， vi0≠vim。 v∈V(G)，若v不在Г的端点出现，显然d(v)为偶 数， 若v在端点出现过，则d(v)为奇数，
欧拉对物理力学、天文学、弹道学、航海学、建筑学、音 乐都有研究！有许多公式、定理、解法、函数、方程、常数等 是以欧拉名字命名的。欧拉写的数学教材在当时一直被当作标 准教程。19世纪伟大的数学家高斯曾说过“研究欧拉的著作永 远是了解数学的好方法”。欧拉还是数学符号发明者，他创设 的许多数学符号，例如π，i，e，sin，cos，tg，Σ，f (x)等等， 至今202沿0/7/2用3 。

欧拉图与哈密顿图

欧拉图与哈密顿图

例15.3 在图15.6中给出的三个图都是 二部图。它们中的那些是哈密顿图？哪些 是半哈密顿图？为什么？ 解 在（1）中，易知互补顶点子集 V1={a,f},V2={b,c,d,e}。设此二部图为G1， 则G1=<V1,V2,E>. p(G1-V1)=4>|V1|=2，由 定理15.6及其推论可知，G1不是哈密顿 图，也不是半哈密顿图。
是在G'中存在u到v的路径Г2，显然Г1 与Г2边不重，这说明u,v处于Г1∪Г2 形成的简单回路上。
三、求欧拉图中欧拉回路的算法
设G为欧拉图，一般来说G中存 在若干条欧拉回路，下面介绍两种求 欧拉回路的算法。
1．Fleury算法，能不走桥就不走桥： （1）任取v0∈V(G)，令P0=v0. （2）设Pi=v0e1v1e2…eivi已经行遍， 按下面方法来从E(G)-{e1,e2,…,ei}中选 取ei+1： （a）ei+1与vi相关联； （b）除非无别的边可供行遍， 否则ei+1不应该为Gi=G-{e1,e2,…,ei}中的 桥。 （3）当（2）不能再进行时，算法停止。
p(C-V1)达到最大值|V1|，而当V1中顶点在C 上有彼此相邻的情况时，均有p(C-V1)<|V1|， 所以有p(C-V1)≤|V1|.而C是G的生成子图， 所以，有p(G-V1)≤p(C-V1)≤|V1|. 本定理的条件是哈密顿图的必要条件， 但不是充分条件。可以验证彼得松图（图 14.3中（1）所示）满足定理中的条件，但 它不是哈密顿图。当然，若一个图不满足 定理中的条件，它一定不是哈密顿图。
2．逐步插入回路法 设G为n阶无向欧拉图，V(G)={v1,v2,…,vn}， 求G中欧拉回路的逐步插入回路法的算法如下： 开始 i←0，v*=v1，v=v1，P0=v1， G0=G. 1．在Gi中任取一条与V关联的边 e=(v,v')，将e及v’加入到Pi中得到Pi+1. 2．若v '=v*，转3，否则i←i+1,v=v' ， 转1.

欧拉图和哈密而顿图

欧拉图和哈密而顿图

17
15.欧拉图与哈密顿图 欧拉图与哈密顿图
15.2 哈密顿图
证明： 证明： 是图的一条哈密尔顿回路， 设 C是图的一条哈密尔顿回路， 则对于 的任一 是图的一条哈密尔顿回路 则对于V的任一 非空真子集S可知 可知： 非空真子集 可知： w(C-S) ≤|S| w(C-S)表示 删去 顶点集后得到的图的连通分 表示C删去 表示 删去S顶点集后得到的图的连通分 图的个数。由于G是由 和一些不在C中的边构 是由C和一些不在 图的个数。由于 是由 和一些不在 中的边构 成的， 的生成子图， 成的，C-S是G-S的生成子图，所以 是 的生成子图 w(G-S) ≤ w(C-S) ≤|S|
11
15.欧拉图与哈密顿图 欧拉图与哈密顿图
15.1 欧拉图
定理15.5 G是非平凡的欧拉图当且仅当 是连通 是非平凡的欧拉图当且仅当G是连通 定理 是非平凡的欧拉图当且仅当 的且为若干个边不重的圈的并。 的且为若干个边不重的圈的并。
12
15.欧拉图与哈密顿图 欧拉图与哈密顿图
15.1 欧拉图
Fleury算法： 算法： 算法 1) 任取 0∈V(G)，令P0=v0; 任取v ， 2) 设 Pi=v0e1v1e2…eivi 已经行遍 ， 按下面方法 来从E(G)-{e1,e2…ei}中选取 i+1： 中选取e 来从 中选取
4
15.欧拉图与哈密顿图 欧拉图与哈密顿图
15.1 欧拉图 现从G’中取二个顶点 中取二个顶点v 现从 中取二个顶点 i和vj，且vi和vj没有直接联 之间加一根联线变为图G， 现在v 线，现在 i和vj之间加一根联线变为图 ，则变 为奇数点，则从v 一定存在一条欧拉通路 通路。 为奇数点，则从 i到vj一定存在一条欧拉通路。

第十五章欧拉图与哈密顿图

第十五章欧拉图与哈密顿图

具有哈密顿回路的图称为半哈密顿图。平 凡图是哈密顿图。
图中所示的三个无向图都有哈密顿回路， 所以都是哈密顿图。有向图中，（）具有哈 密顿回路，因而它是哈密顿图。（）只有哈 密顿通路，但无哈密顿回路，因而它是半哈 密顿图，而（）中既无哈密顿回路，也没有 哈密顿通路，因而不是哈密顿图，也不是半 哈密顿图。
∈()，若不在Г的端点出现，显然 ()为偶数，若在端点出现过，则()为 奇数，因为Г只有两个端点且不同，因而 中只有两个奇数顶点。另外，的连通 性是显然的。
充分性: 设的两个奇度顶点分别 为 和，对加新边（），
得' ∪()，则'是连通且无奇度 顶点 的图，由定理可知，‘为欧拉 图，因而存在欧拉回路'，而' () 为中一条欧拉通路，所以为半欧拉图。
图
由定理立即可知，图()图 为欧拉图，本图既可以看成圈， ，，之并（为 清晰起见，将个圈画在（）中），也 可看成圈与圈 之并（两个圈画在（）中）。将（） 分解成若干个边不重的圈的并不是（） 图特有的性质，任何欧拉图都有这个性 质。
定理 是非平凡的欧拉图当且仅 当是连通的且为若干个边不重的圈的并。
证 读者用定理证明。
下面给出一些哈密顿图和半哈密顿图 的充分条件。
定理 设是阶无向简单图，若对
于中任意不相邻的顶点，均有
()()≥
()
则中存在哈密顿通路。
证： 首先证明是连通图。否则至少 有两个连通分支，设是阶数为 的两个连通分支，设∈()，∈()， 因为是简单图，所以 ()()
()()≤≤
这与（）矛盾所以必为连通图。
可以证明，当算法停止时所得简单回路 …()为中一条欧拉回路。
例 图()是给定的欧拉图。某人用算法 求中的欧拉回路时， 走了简单回路 之 后(观看他的错误走法)，无法行遍了，试 分析在哪步他犯了错误?

第十五章-欧拉图与哈密顿图

第十五章-欧拉图与哈密顿图

（4）半欧拉图
具有欧拉通路而无欧拉回
路的图.
3
2. 无向欧拉图的判定 定理15.1 无向图G是欧拉图当且仅当G连通且无 奇度结点。 证明:若G为平凡图结论显然成立。
下面设G为n阶m条边的无向图。 必要性 设C为G中一条欧拉回路。
（1）G连通显然。
（2）viV(G),vi在C上每出现一次获2度，所 以vi为偶度结点. 由vi的任意性，结论为真。 4
e5
e4 e2
e5
e4
e3
e3
e3
欧拉图
半欧拉图
不是欧拉图 不是半欧拉图
11
a(甲)
b (乙)
图G
例:两只蚂蚁比赛问题：两只 蚂蚁甲、乙分别处在图G 中 的结点a,b处,并设图中各边长 c 度相等。甲提出同乙比赛：
从它们所在结点出发，走过 图中所有边最后到达结点c处。 如果它们速度相同，问谁最 先到达目的地？
17
（2）若G恰有两个奇数度结点vi和vj,则G具有 欧拉通路，且邮局位于结点vi，则邮递员走遍所 有的街道一次到达结点vj ;从vj返回vi可选择其间 的一条最短路径。这样,最短邮路问题转化为求 vi到vj的欧拉通路和vj到vi的最短路径问题。
（3）若G中度数为奇数的结点多于2个,则回路 中必须增加更多的重复边。分两步:
19
例:在下图中确定一条从v1到v1的回路,3使其权值最小.
8
半欧拉图的判定
定理15.2 无向图G是半欧拉图当且仅当G连通 且恰有两个奇度结点。若有两个奇数度结点,则 它们是每条欧拉通路的端点。
证明:必要性
G的连通性是显然的。设G是m条边的n阶无向 图,因为G为半欧拉图，因而G中存在欧拉通路 （但不存在欧拉回路），设=vi0ej1vi1…vim为G 中一条欧拉通路， vi0vim。对任意的v,若v不在 的端点出现，d(v)必为偶数，若v在端点出现 过，则d(v)为奇数，因为只有两个端点不同， 因此G中只有两个奇度结点。

欧拉图和哈密尔顿图

欧拉图和哈密尔顿图
欧拉回路是指不重复地走过所有路 径的回路，而哈密尔顿环是指不重复地
走过所有的点，并且最后还能回到起点的回 路
哈密尔顿图
定义：通过图G的每个结点一次且仅一次的环称为哈密尔顿环。具 有哈密尔顿环的图称为哈密尔顿图。通过图G的每个结点一次且仅 一次的开路称为哈密尔顿路。具有哈密尔顿路的图称为半哈密尔 顿图。
f：说法语、日语和俄语；
g：说法语和德语.
c f
g
解 设7个人为7个结点, 将两个懂同一语言的人之间连一条边
(即他们能直接交谈), 这样就得到一个简单图G, 问题就转化为
G是否连通. 如图所示, 因为G的任意两个结点是连通的, 所以
G是连通图. 因此, 上述7个人中任意两个人能交谈.
解二
c
英
意
e
a
例
半哈密尔顿图
哈密尔顿图 哈密尔顿图
N
周游世界的游戏——的解
哈密顿图
哈密顿图
无哈密顿 通路
哈密顿图
存在哈密 顿通路
实例
在上图中， (1),(2) 是哈密顿图;
实例
已知有关人员a, b, c, d, e, f, g 的有关信息
a：说英语；
b：说英语或西班牙语；
c；说英语，意大利语和俄语；
a：说英语； b：说英语或西班牙语；
英
德
c；说英语，意大利 语和俄语；
b
g
d：说日语和西班牙语 e：说德语和意大利语； f：说法语、日语和俄语； g：说法语和德语.
西
d
日
法
f
如果题目改为：试问这7个人应如何安排座位, 才能使每个人都能与
他身边的人交谈？
解：用结点表示人，用边表示连接的两个人能说讲一种语言，够造

第十五章 欧拉图与哈密顿图

第十五章 欧拉图与哈密顿图

长度大于或等于3的圈，设C为G中一个圈，
删除C上的全部边，得G的生成子图G'，
, G2 , 设G'有s个连通分支 G1
公共顶点为，i=1, 2, … , s.
, 每个连通分支 , Gs
至多有k条边，且无奇度顶点，并且设G'i与C的
, G2 , 由归纳假设可知， G1
, 都是欧拉图， , Gs
并设G的顶点集 V={v1, v2, … , vn }.
必要性. 因为G为欧拉图，所以G中存在欧拉回路， 设C为G中任意一条欧拉回路， vi , vj ∈V，
vi, vj都在C上，因而vi , vj 连通，所以G为 连通图.
又vi∈V，vi在C上每出现一次获得2度，
若出现k次就获得2k 度，即d(vi)=2k .
点的入度都等于出度.
Байду номын сангаас
由定理15.3和15.4立即可知，图15.1中所示3个
有向图中只有（4）是欧拉图，没有半欧拉图.
图15.1
由定理15.1立即可知，图15.3(1)图为欧拉图.
图15.3
本图既可以看成圈
v1v2v8v1 , v2v3v4v2 , v4v5v6v4 , v6v7v8v6 之并(为清晰起见，
vim -1e jm vim为G中一条欧拉
vi 0 vim . v V (G ), 若v不在Г的端点出现， 通路，
显然d(v)为偶数，若v在端点出现过，则d(v)为奇数，
因为Г只有两个端点且不同，因而G中只有两个
奇数顶点. 另外，G的连通性是显然的.
充分性. 设G的两个奇度顶点分别为u0和v0，对G加 新边（u0, v0），得G ' =G∪(u0,v0)，则G '是 连通且无奇度顶点的图，由定理15.1可知，G ' 为欧拉图，因而存在欧拉回路C ' ，而

离散数学课件15欧拉图与哈密顿图

离散数学课件15欧拉图与哈密顿图

04
欧拉图与哈密顿图的应用 场景
欧拉图的应用场景
路径规划
欧拉图可以用于表示从一 个点到另一个点的路径， 常用于物流、交通和旅行 等领域。
网络流问题
欧拉图可以用于解决最大 流和最小割等问题，在网 络优化、资源分配和计划 制定等方面有广泛应用。
组合优化
欧拉图可以用于表示组合 优化问题，如旅行商问题、 排班问题等，是求解这些 问题的常用工具。
一个图存在哈密顿回路当且仅当其所有顶点的度都大于等于2 。
哈密顿图的性质
哈密顿图中的所有顶点的度都 大于等于2。
一个图存在哈密顿回路当且仅 当其所有顶点的度都大于等于2。回 路。
哈密顿图的构造方法
添加边法
在所有顶点的度都大于等于2的图 中，不断添加边，直到所有顶点的 度都大于等于2，最后得到的图就 是哈密顿图。
哈密顿图的应用场景
社交网络分析
哈密顿图可以用于表示社交网络 中的路径，分析人际关系和信息
传播路径。
生物信息学
哈密顿图可以用于表示基因组、蛋 白质组等生物信息数据，进行基因 序列比对、蛋白质相互作用分析等。
推荐系统
哈密顿图可以用于表示用户和物品 之间的关系，进行个性化推荐和智 能推荐。
欧拉图与哈密顿图在计算机科学中的应用
欧拉图的构造方法
欧拉图的构造方法1
总结词
通过添加一条边将所有顶点连接起来， 从而形成一个欧拉图。
详细描述了两种构造欧拉图的方法， 为实际应用中构造欧拉图提供了思路。
欧拉图的构造方法2
通过将两个欧拉图合并，并连接它们 的所有顶点，从而形成一个新的欧拉 图。
02
哈密顿图
哈密顿图的定义
哈密顿图（Hamiltonian Graph）是指一个图存在一个遍历其 所有边且每条边只遍历一次的路径，这个路径称为哈密顿路径， 如果该路径的起点和终点是同一点，则称这个路径为哈密顿回 路。

欧拉图与哈密顿图s

欧拉图与哈密顿图s
说明：该推论是充分条件但不是必要的。 例如：
该五边形是哈密顿图，但任意两个不相邻的顶点度 数之和为4，图形阶数为5。
座位问题
例 在某次国际会议的预备会中，共有8人参加，他 们来自不同的国家。如果他们中任两个无共同语言的人 与其余有共同语言的人数之和大于或等于8，问能否将这 8个人排在圆桌旁，使其任何人都能与两边的人交谈。
例15.2（P296） v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2
例15.2（P296）
利用欧拉图可以解决哥尼斯堡七桥问题： 从某地出发，对每座跨河桥只走一次，而在遍历 了七座桥之后，却又能回到原地。
由定理15.1（无向欧拉图的判定定理）可知该问题无解。
思考 如下图所示，从一房间出发，问能否不重复地
（1）
（2）
（3）
（4）
（5）
（6）
（1）（2）（3）（4）为哈密顿图 （5）为半哈密顿图 （6）既不是哈密顿图，又不是半哈密顿图。
到目前为止，还没有找到判断哈密顿图简单的充分必 要条件。
下面介绍哈密顿图和半哈密顿图的必要条件
定理15.6 设无向图G=<V,E>是哈密顿图，V1是V的任意 非空子集，则有p(G-V1)≤|V1|,其中p(G-V1)为G-V1的连 通分支数。
定义（哈密顿通路和哈密顿回路） 经过图（有向图或无向图）每个顶点一次
且仅一次的通路称为哈密顿通路。 经过图每个结点一次且仅一次的回路（初
级回路）称为哈密顿回路。 定义（哈密顿图和半哈密顿图）
存在哈密顿回路的图称为哈密顿图。 存在哈密顿通路但不存在哈密顿回路的图 称为半哈密顿图。 平凡图是哈密顿图。
由两判定定理，立即可知 （4）为欧拉图， （5）、（6）即不是欧拉图，也不是半欧拉图。

欧拉图及哈密顿

欧拉图及哈密顿
哈密顿路径是指一条遍历图的所有顶 点的路径，这条路径的起点和终点是 同一点，但路径上的边可以重复。
哈密顿图的性质
哈密顿图具有连通性，即任意两 个顶点之间都存在一条路径。
哈密顿图的顶点数必须大于等于 3，因为至少需要3个顶点才能 形成一条遍历所有顶点的路径。
哈密顿图的边数必须为奇数，因 为只有奇数条边才能形成一条闭
欧拉图及哈密顿
• 欧拉图 • 哈密顿图 • 欧拉图与哈密顿图的应用 • 欧拉回路与哈密顿回路 • 欧拉路径与哈密顿路径
目录
01
欧拉图
欧拉图的定义
总结词
欧拉图是指一个图中存在一条路径，这条路径可以遍历图中的每条边且每条边 只遍历一次。
详细描述
欧拉图是由数学家欧拉提出的一种特殊的图，它满足特定的连通性质。在欧拉 图中，存在一条路径，这条路径从图的一个顶点出发，经过每条边一次且仅一 次，最后回到起始顶点。
互作用网络的研究。
04
欧拉回路与哈密顿回路
欧拉回路的概念与性质
概念
欧拉回路是指一个图形中，从一点出 发，沿着一条路径，可以回到起始点 的路径。
性质
欧拉回路必须是连续的，不能中断， 也不能重复经过同一条边。此外，欧 拉回路必须是闭合的，起始点和终点 必须是同一点。
哈密顿回路的概念与性质
概念
哈密顿回路是指一个图形中，存在一 条路径，该路径经过了图中的每一条 边且每条边只经过一次。
随机构造法
通过随机选择边和顶点，不断扩展图，直到满足哈密顿图的条件。这种方法需要大量的计 算和随机性，但可以用于构造大规模的哈密顿图。
03
欧拉图与哈密顿图的应用
欧拉图在计算机科学中的应用
算法设计
欧拉图理论是算法设计的重要基础，特别是在图算法和动态规划 中，用于解决诸如最短路径、最小生成树等问题。

离散数学15 欧拉图与哈密顿图

离散数学15 欧拉图与哈密顿图
穿过每一道门，通过所有房间？
15.2 哈密顿图
1859年，爱尔兰数学家威廉·哈密尔顿发明 了一个旅游世界的游戏。将一个正十二面体的 20个顶点分别标上世界上大城市的名字，要求 玩游戏的人从某城市出发沿12面体的棱，通过 每个城市恰一次，最后回到出发的那个城市。
哈密尔顿游戏是在左图中如何 找出一个包含全部顶点的圈。
定义（哈密顿通路和哈密顿回路） 经过图（有向图或无向图）每个顶点一次
且仅一次的通路称为哈密顿通路。 经过图每个结点一次且仅一次的回路（初
级回路）称为哈密顿回路。 定义（哈密顿图和半哈密顿图）
存在哈密顿回路的图称为哈密顿图。 存在哈密顿通路但不存在哈密顿回路的图 称为半哈密顿图。 平凡图是哈密顿图。
由两判定定理，立即可知 （4）为欧拉图， （5）、（6）即不是欧拉图，也不是半欧拉图。
例15.2（P296） v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2
◼ Fleury算法
◼ （1）任取v0V(G)，令P0=v0。 ◼ （2）设Pi=v0e1v1e2…..eivi已经行遍，则按下面
判断所示两图是否为欧拉图、半欧拉图？
无向欧拉图与无向半欧拉图的判断方法
定理15.1（无向欧拉图的判定）无向图G是欧拉图当 且仅当G是连通图，且G中没有奇度顶点。
定理15.2（无向半欧拉图的判定）无向图G是半欧拉 图当且仅当G是连通图，且G中恰有两个奇度顶点。
（1）
（2）
（3）
有向欧拉图与有向半欧拉图的判断方法
（1）
（2）
（3）
（4）
（5）
（6）
（1）（2）（3）（4）为哈密顿图 （5）为半哈密顿图 （6）既不是哈密顿图，又不是半哈密顿图。

大学离散数学欧拉图和哈密尔顿图

大学离散数学欧拉图和哈密尔顿图

(a)
(b)
推论1:哈密尔顿图无割点.
2020/9/28
24
计算机科学学院 刘芳
15.2.3 Hamilton图的判定方法
例3：
▪ 证明下述各图不是哈密顿图。
2020/9/28
25
计算机科学学院 刘芳
15.2.3 Hamilton图的判定方法
推论2：
▪ 对二部图G＝＜ V1,V2,E＞
若| V1 |≠| V2 |，则一定不是H图。 证明：
2020/9/28
14
计算机科学学院 刘芳
15.1.4 中国邮路问题
例如：
2020/9/28
15
计算机科学学院 刘芳
15.1.4 中国邮路问题
判断条件
▪ 定理：
▪ 设L是图G的包含所有边的回路，则L具有最小长 度的充分必要条件是： ▪ 每条边最多重复一次； ▪ G的每个回路上，所有重复边的长度之和，不 超过该回路长度的一半。
2020/9/28
16
计算机科学学院 刘芳
15.2 Hamilton 图
15.2.1 问题引入 15.2.2 Hamilton图的定义 15.2.3 Hamilton图的判定方法 15.2.4 应用举例
2020/9/28
17
计算机科学学院 刘芳
15.2.1 问题引入
周游世界问题(W.Hamilton, 1859年)
▪ 可以用结点表示城市，城市间的交通路线用边表示，而 城市间的交通线路距离可用附加于边的权表示。
▪ 这样，上述问题可以归结为寻找一条权的总和为最短的 哈密尔顿回路的问题。
2020/9/28
30
计算机科学学院 刘芳
分析
▪ 穷举法 ▪ 近似算法 ▪ …………

15欧拉图与哈密顿图

15欧拉图与哈密顿图
问题转化为在图中找一条哈密顿回路. ABDFGECA即可.
哈密顿图的判定 定理1(必要条件): 设无向图G=<V, E>是哈密顿 图, V1是V的任意非空子集, 则p(G-V1)≤V1. 推论: 设无向图G=<V, E>是半哈密顿图, V1是V 的任意非空子集, 则p(G-V1)≤V1+1.
在Peterson图中, 虽然对任意顶 点集V1, 都满足p(G-V1)|V1|,但 它不是哈密顿图.
基本思想：能不走桥就不走桥
15.2 哈密顿图 定义1. 经过无向(有向)图中所有顶点恰好一次 的路(圈)称为哈密顿路(圈). 定义2. 具有哈密顿圈的图称为哈密顿图. 定义3. 具有哈密顿路但不具有哈密顿圈的图 称为半哈密顿图. 例1. 判断下列图形是否哈密顿图或半哈密顿图.
半哈密顿图 哈密顿图
都不是
例4. 判断下列有向图是否欧拉图或半欧拉图.
都不是 半欧拉图
欧拉图
一笔画问题:从某点出发,不间断地画完整个图. 即在图中找出欧拉通路（回路）.
Fleury算法: (1) 任取v0∊V(G), (2) 设Pi=v0e1v1e2eivi,
若E(G)-{e1,e2,ei}中没有与vi关联的边, 则计 算停止; 否则在vi关联的边中优先选择非桥的边 添加. (3) 令i=i+1, 返回(2).
定理2(充分条件): 设G＝<V, E>是无向简单图. 若对任意两个不相邻顶点u,vV, 均有 d(u)+d(v)|V|-1, 则G中存在哈密顿路； 若对任意两个不相邻顶点u,vV, 均有 d(u)+d(v)|V|, 则G是哈密顿图.
推论: n阶无向简单图G中, n>2, (G)n/2, 则G是

欧拉图与哈密顿图

欧拉图与哈密顿图

求欧拉图中欧拉回路的算法
Fleury算法;能不走桥就不走桥
1 任取v0∈VG;令P0＝v0; 2 设Pi＝v0e1v1e2…eivi已经行遍;按下面方法来从
EGe1;e2;…;ei中选取ei+1： a ei+1与vi相关联； b 除非无别的边可供行遍;否则ei+1不应该为
Gi＝Ge1;e2;…;ei中的桥; 3当2不能再进行时;算法停止;
例15 1
例15 1 设G是非平凡的且非环的欧拉图;证明： 1λG≥2; 2对于G中任意两个不同顶点u;v;都存在简单回路C含u和v;
证明 1由定理15 5可知;e∈EG;存在圈C;e在C中; 因而pGe＝pG;故e不是桥; 由e的任意性λG≥2;即G是2边连通图;
例15 1
例15 1 设G是非平凡的且非环的欧拉图;证明： 1λG≥2; 2对于G中任意两个不同顶点u;v;都存在简单回路C含u和v;
可以验证彼得松图满足定理中的条件;但不是哈密顿图;
若一个图不满足定理中的条件;它一定不是哈密顿图;
推论
推论 设无向图G＝<V;E>是半哈密顿图;对于任意的V1V且 V1≠;均有 pGV1≤|V1|+1
证明 设P是G中起于u终于v的哈密顿通路; 令G ＝G∪u;v在G的顶点u;v之间加新边; 易知G 为哈密顿图; 由定理15 6可知;pG V1≤|V1|; 因此;pGV1 ＝ pG V1u;v ≤ pG V1+1 ≤ |V1|+1
若vi与vj有哈共密同语顿言图;就是在v能i;vj将之间图连中无向所边有vi;v顶j; 由此组成点边都集合能E;安则G排为8在阶无某向个简单初图级; 回路 vi∈V;上dvi为的与图vi有;共同语言的人数;

第十五章 欧拉图

第十五章 欧拉图

e 讲德国和意大利语；
以用来判定某些图不是哈密 解 用结点表示人，用边表示连接的两个人能讲同一种语言，构造出图G如下：
设G = <V, E, W>为一个n阶完全带权图Kn, 各边的权非负, 且有些边的权可能为∞。
顿图, 但不便于应用。因为要 C3 = C5, W(C3) = 12
deg(v1) + deg(vp) ≤ r + p – r – l = p – 1＜n – 1 有向图D是半欧拉图的充要条件D是单向连通的且恰有两个奇度的顶点，其中一个顶点的入度比出度大1，另一个顶点出度比入度大1，
2 12
1 1 1
2、右图中每个小正方形的边长都是100米。小明 沿线段从A点到B点，不许走重复路，他最多能走 多少米？
该题应该采用的办法？ 删除某些边，除去奇点对，将A、B变为基点！
解：这道题大多数同学都采用试画的方法，实际上还是用欧拉
图的判定定理来求解更合理、快捷。首先，图中有8个奇点，在8个 奇点之间至少要去掉4条线段，才能使这8个奇点变成偶点；其次， 从A点出发到B点，A，B两点必须是奇点，现在A，B都是偶点，必 须在与A，B连接的线段中各去掉1条线段，使A，B成为奇点。所 以至少要去掉6条线段，也就是最多能走1800米，走法如下图。
3.1) 存在v’r(1 r k), 有: <v’i,vk+1>E(D)
(i = 1..r-1), <vk+1,v’r>E(D), 如下图(a)所示, 则 = v’1v’2…v’r-1vk+1v’r…v’k为D中哈密顿通路。
3.2) i { 1, 2, …, k }, 均有: <v’i, vk+1> E(D), 见下图(b)所示, 则 = '∪<v’k, vk+1>为D中哈密顿通 路。

欧拉图与哈密顿图

欧拉图与哈密顿图

*
例6 求图中(1) 所示带权图K4中最短哈密顿回路.
(1) (2)
*
解 C1= a b c d a, W(C1)=10 C2= a b d c a, W(C2)=11 C3= a c b d a, W(C3)=9 可见C3 (见图中(2)) 是最短的，其权为9.
算法： (1) 任取v0V(G)，令P0=v0. (2) 设Pi = v0e1v1e2…eivi 已经行遍，按下面方法从 E(G){e1,e2,…,ei }中选取ei+1： (a) ei+1与vi 相关联； (b) 除非无别的边可供行遍，否则ei+1不应该为 Gi = G{e1,e2,…,ei }中的桥. (3) 当 (2)不能再进行时，算法停止. 可以证明算法停止时所得简单通路 Pm = v0e1v1e2…emvm (vm=v0)为G 中一条欧拉回路. 用Fleury算法走出上一页图(1),(2)从A出发（其实从任何一点 出发都可以）的欧拉回路各一条.
欧拉图的判别法
#2022
*
定理15.3 有向图D是欧拉图当且仅当D是强连通的且每个顶 点的入度都等于出度. 本定理的证明类似于定理15.1. 定理15.4 有向图D是半欧拉图当且仅当D是单向连通的，且 D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个 的出度比入度大1，而其余顶点的入度都等于出度. 本定理的证明类似于定理15.1. 定理15.5 G是非平凡的欧拉图当且仅当G是连通的且为若干 个边不重的圈之并. 可用归纳法证定理15.5.
证明
证（着重关键步骤） (1) 由()及简单图的性质，用反证法证明G连通. (2) = v1v2…vl 为极大路径，l n, 若l = n（结束）. 下面讨论l<n的情况，即要证G中存在过上所有顶点的圈. ① 若(v1,vl)在G中，则(u,v)为G中圈
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

e5
v3
v2 e1 v1
e2
e3
e4
v4
e5
v3 e3 e4 v4
v2 v1 v5
e2 e3
e1 e5
v3 e4 v4 v6
v1
e6 v5 e7 e8 v6 e2 e3
e8 v5
e8 v6 v5 e2 v6
e7
G
v2 e1 v1 v5 v6 v3 e4 v4 v5 v2
G1
e2 v3 e4 v2 e1 v1 v5 e1
定理15.7
定理15.7 设G是n阶无向简单图，若对于G中任意不相邻的顶 点vi,vj，均有 d(vi)+d(vj)≥n-1 (15.1) 则G中存在哈密顿通路。 证明 首先证明G是连通图。 否则G至少有两个连通分支， 设G1,G2是阶数为n1,n2的两个连通分支， 设v1∈V(G1)，v2∈V(G2)，因为G是简单图，所以 dG(v1)+dG(v2)＝dG1(v1)+dG2(v2)≤n1-1+n2-1≤n-2 这与(15.1)矛盾，所以G必为连通图。
例15.3的说明
哈密顿通路是经过图中所有顶点的一条初级通路。 哈密顿回路是经过图中所有顶点的初级回路。 对于二部图还能得出下面结论： 一般情况下，设二部图G＝<V1,V2,E>，|V1|≤|V2|，且 |V1|≥2，|V2|≥2，由定理15.6及其推论可以得出下面结 论： (1) 若G是哈密顿图，则|V1|＝|V2|。 (2) 若G是半哈密顿图，则|V2|＝|V1|+1。 (3) 若|V2|≥|V1|+2，则G不是哈密顿图，也不是半哈密 顿图。
§15.2 哈密顿图
设图为G2，则G2＝<V1,V2,E>，其中 V1＝{a,g,h,i,c}，V2＝{b,e,f,j,k,d}， 易知，p(G2-V1)＝|V2|＝6>|V1|＝5， 由定理15.6可知，G2不是哈密顿图， 但G2是半哈密顿图。 baegjckhfid为G2中一条哈密顿通路。 设图为G3。G3＝<V1,V2,E>，其中 V1＝{a,c,g,h,e}，V2＝{b,d,i,j,f}， G3中存在哈密顿回路。 如 abcdgihjefa， 所以G3是哈密顿图。
®
(a) 制造满足归纳假设的若干个小欧拉图.由连通及 无奇度定点可知，(G) ≥2，用扩大路径法可得G 中长度≥3的圈C1.删除C1上所有边（不破坏G中顶 点度数的奇偶性）得G ，则G 无奇度顶点，设它 有s ≥1个连通分支G1 ,G2 ,…,Gs ，它们的边数均 ≤k，因而它们都是小欧拉图. (b) 将C1上被删除的边还原，从C1上某点出发走出 G的一条欧拉回路C.
十二面体
哈密尔顿把该游戏以25英镑的价格买给了J.Jacques and Sons公司 (该公司如今以制造国际象棋设备而著 名) ，1859年获得专利权。但商业运作失败了。
该游戏促使人们思考点线连接的图的结构特征。这 就是图论历史上著名的哈密尔顿问题。
哈密尔顿(1805---1865),爱尔兰数学家。个人生活很 不幸，但兴趣广泛：诗歌、光学、天文学和数学无所 不能。他的主要贡献是在代数领域，发现了四元数(第 一个非交换代数)，他认为数学是最美丽的花朵。
§15.2 哈密顿图
推论 设无向图G＝<V,E>是半哈密顿图，对于任意的V1V且 V1≠，均有 p(G-V1)≤|V1|+1 证明 设P是G中起于u终于v的哈密顿通路， 令G ＝G∪(u,v)(在G的顶点u,v之间加新边)， 易知G 为哈密顿图， 由定理15.6可知，p(G -V1)≤|V1|。 因此，p(G-V1) ＝ p(G -V1-(u,v)) ≤ p(G -V1)+1 ≤ |V1|+1
®
实例
(1)
(2)
(3)
(4)
在上图中， (1),(2) 是哈密顿图; (3)是半哈密顿图; (4)既不是哈密顿图，也不是半哈密顿图，为什么？
与判断一个图是否为欧拉图不一样，到目前为止，人们还 没有找到哈密顿图简单的充分必要条件。
§15.2 哈密顿图
定理15.6 设无向图G＝<V,E>是哈密顿图，对于任意V1V，且 V1≠，均有 p(G-V1)≤|V1| 其中，p(G-V1)为G-V1的连通分支数。 证明 设C为G中任意一条哈密顿回路， 易知，当V1中顶点在C上均不相邻时， p(C-V1)达到最大值|V1|， 而当V1中顶点在C上有彼此相邻的情况时， 均有p(C-V1)＜|V1|，所以有 p(C-V1)≤|V1|。 而C是G的生成子图，所以，有p(G-V1)≤p(C-V1)≤|V1|。 说明 本定理的条件是哈密顿图的必要条件，但不是充分条件。 可以验证彼得松图满足定理中的条件，但不是哈密顿图。 若一个图不满足定理中的条件，它一定不是哈密顿图。
第十五章 欧拉图与哈密顿图
第十五章 欧拉图与哈密顿图
欧拉图
哈密顿图
最短路问题与货郎担问题 知 识 点：欧拉图、汉密尔顿图、Fleury算法、Dijkstra 算法、货郎担问题 。 教学要求：深刻理解和掌握欧拉图与汉密尔顿图的性质。
教学重点：欧拉图与汉密尔顿图的性质。
学时: 2
§15.1 欧拉图
两个与可行遍问题有关的问题
§15.2 哈密顿图
定义15.2 通过图(无向图或有向图)中所有顶点一 次且仅一次的通路称为哈密顿通路. 通过图(无向图或有向图)中所有顶点一 次且仅一次的回路称为哈密顿回路(哈密顿圈). 具有哈密顿回路的图称为哈密顿图 具有哈密顿通路但不具有哈密顿回路的图称为半哈 密顿图 规定平凡图是哈密顿图 环与平行边不影响哈密顿性.
从以上证明不难看出：欧拉图是若干个边不重 的圈之并，见下图.
PLAY
§15.1 欧拉图
定理15.2 无向图G是半欧拉图当且仅当G是连通的且 恰有两个奇度顶点 证 必要性简单. 充分性（利用定理15.1） 设u,v为G 中的两个奇度顶点，令 G =G(u,v) 则G 连通且无奇度顶点，由定理15.1知G 为欧拉图，因而 存在欧拉回路C，令 =C(u,v) 则 为 G 中欧拉通路.

一个要求行遍图的每条边恰好一次, 这就是欧拉回路问 题,对应的图称为欧拉图

一个要求行遍图的每个顶点恰好一次, 这就是哈密顿圈 问题,对应的图称为哈密顿图
C
A
D
B
哥尼斯堡七桥问题 周游世界问题
®
§15.1 欧拉图
定义15.1 通过图(无向图或有向图)中所有边一次且仅一 次行遍所有顶点的通路称为欧拉通路. 通过图(无向图或有向图)中所有边一次且仅一 次行遍所有顶点的回路称为欧拉回路. 具有欧拉回路的图称为欧拉图 具有欧拉通路而无欧拉回路的图称为半欧拉图 规定平凡图是欧拉图
例15.3 在下图中给出的三个图都是二部图。它们中的哪些是 哈密顿图？哪些是半哈密顿图？为什么？ 易知互补顶点子集 V1＝{a,f} V2＝{b,c,d,e} 设此二部图为G1，则G1＝<V1,V2,E>。 p(G1-V1)＝4>|V1|＝2， 由定理15.6及其推论可知，G1不是哈 密顿图，也不是半哈密顿图。
®
§15.1 欧拉图
定理15.3 有向图D是欧拉图 当且仅当 D是强连通的且
每个顶点的入度等于出度
定理15.4 有向图D是半欧拉图当且仅当 D是单向连通的且 恰有两个奇度顶点,其中一个顶点的入度比出度大1, 另一个顶点出度比入度大1,而其余顶点入度等于出度 定理15.5 G是非平凡的欧拉图当且仅当G是连通的且是 若干个边不重的圈的并
G2
v3 v4 v6 v5
G3
v2
e1 v1 v6 v4 v3
v1
v6
v4
G4
®
G5
G6
G7
W =v e v3 e v e ve W v e =v W8=v0e6v e W v0 =v e v e e v v e v e v v e W =v W =v W =v W =v e v W =v 5 6 5 7 6 8 1 5 3 0 3 4 0 57 7 6 8 0 1 6 50 5 3 7 6 8 4 1 4 5 3 3 2 3 2 4 1 4 1 1e 0 6 2 0 6 5 7 6 3 0 6 5 7 6 8 6 5 7 6 4 8 0 1 6 5 5 3 7 3 6 4 8 4 1 5 2v5 3 2
例15.4
例15.4 设G是n阶无向连通图。证明：若G中有割点或桥，则 G不是哈密顿图。 证明 (1)证明若G中有割点，则G不是哈密顿图。 设v为连通图G中一个割点，则V ＝{v}为G中的点割集， 而 p(G-V )≥2＞1＝|V | 由定理15.6可知G不是哈密顿图。 (2)证明若G中有桥，则G不是哈密顿图。 设G中有桥，e＝(u,v)为其中的一个桥。 若u,v都是悬挂点，则G为K2，K2不是哈密顿图。 若u,v中至少有一个，比如u，d(u)≥2，由于e与u关联，e 为桥，所以G-u至少产生两个连通分支，于是u为G中割点 由(1)的讨论可知，G不是哈密顿图。
§15.2 哈密顿图
背景
1857年， 哈密尔顿发明了一个游戏(Icosian Game). 它是由一个木制的正十二面体构成，在它的每个棱角 处标有当时很有名的城市。游戏目的是“环球旅行”。 为了容易记住被旅游过的城市 ，在每个棱角上放上一 个钉子，再用一根线绕在那些旅游过的城市上(钉子), 由此可以获得旅程的直观表示。
彼德森图
K5
K3,3
®
§15.1 欧拉图
Fleury(弗罗莱)算法

⑴ 任取 v0∈V(G),令 P0 = v0 , i=0 ⑵ 设 Pi = v0e1v1e2…eivi , 如果 E(G)-{e1 , e2 , … ,ei}中没有与vi关联的边,则 计算停止。否则按下述条件从 E(G) - {e1 , e2 , … ,ei} 中任取一条边ei+1 (a) ei+1和vi相关联; (b) 除非没有别的边可选择,