当前位置：文档之家 › 大学离散数学 欧拉图和哈密尔顿图

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

  • 格式：ppt
  • 大小：1.01 MB
  • 文档页数：31

下载文档原格式

  / 31

合集下载

图论讲义第4章-欧拉图与hamilton图

图论讲义第4章-欧拉图与hamilton图
[1] E. Lucas，Récréations Mathématiques IV, Paris, 1921.
Fleury 算法的步骤如下：
输入：欧拉图 G 输出：G 的欧拉闭迹。
step1. 任取 v0 ∈V (G) ，令 w0 := v0 ， i := 0 。 step2. 设迹 wi = v0e1v1 eivi 已取定。从 E \ {e1, e2 , , ei }中选取一条边 ei+1 ，使得 （1） ei+1 和 vi 相关联； （2） ei+1 不选 Gi = G \ {e1, e2 , , ei }的割边，除非没有别的选择。
个顶点都是偶度顶点。从而 G +e 有 Euler 闭迹。故 G 有 Euler 迹。证毕。
一个图 G 如果有一条欧拉迹或欧拉闭迹，则我们可以沿着欧拉迹或欧拉闭迹连续而不 重复地把 G 的边画完。因此存在欧拉迹或欧拉闭迹的图通常称为可一笔画的图，或者说它 可一笔画成。如果图 G 可分解为两条迹或闭迹的并，则 G 的边可用两笔不重复地画完。同 样地，如果图 G 可分解为 k 条迹或闭迹的并，则 G 可 k 笔画成。
获得 2k 个同类 u−v 迹。这种分类构成一个等价关系，因此形成了对有重复点的 u−v 迹集合
的划分。划分出的每一个等价类有偶数个条 u−v 路。这说明有重复点的 u−v 迹总共有偶数条。
有以上两方面知， G′ = G − e 中共有奇数条顶点不重复的 u−v 迹（即 u−v 路），因此，
G 中共有奇数个含有边 e 的圈。
step3. 当 step2 不能再执行时，停止。
定理 4.1.3 若 G 是 Euler 图，则 Fleury 算法终止时得到的是 G 的 Euler 闭迹。

离散数学课件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 。

【离散数学讲义】7.Euler图52

【离散数学讲义】7.Euler图52

中国邮递员问题（E-图？） (The Chinese postman problem)
一个邮递员送信, 每次要走遍他负责投递范围内 的街道, 然后再回到邮局. 问他应该按怎样的路线 走, 使所走的路程最短? 如果用点表示交叉路口, 用点之间的连线表示对 应的街道, 每条线上对应一个实数, 它是相应街道 的长度. 原问题变成一个图论问题. 中国邮递员问题: 在赋以非负权的连通图G上, 求 一条最小权环游.(称为最优环游或最佳邮路)。 环游：经过一个图G的每条边至少一次的闭回路。
定理7:(必要条件) 若图G=<V,E>有H-圈,则对V的任
何非空子集S, 均有W(G-S)≤|S|, 其中W(G-S)是从G 中删去S中所有结点及与这些结点关联的边所得到的子图
的连通分支数.
证明:设C是图G的一条H-圈,则对于V的任何非空子集S,
在C中删去S中任意一个结点v1后, 则C-v1仍是连通的路, 若再删去S中的另一个结点v2, 则W(C-v1 - v 2)≤2, 若|S|=k，则删去S中的k个结点,
2.哈密顿图的判定:
1
6 2
5 3 4
定理1 (充分条件):G是至少有3个点的完全图,则G是H图.










K2
K3
K4
K5
定理2. G是简单图, 且n≥3,若对G中任一对不相邻点 u, v, 都有d(u)+d(v)≥n . 则G是Hamilton图
引理1. 设u, v是G的一对不相邻点, d(u)+d(v) ≥n. 若G+uv是H-图G是H-图.
有W(C-v1 - v 2 -...-vk)≤k, 所以
W(C-v1 - v 2 -...-vk)≤|S| . 因为C是H回路,所以它包含了G的所有结点, 即C是G的生

离散数学结构第十五章欧拉图与哈密顿图

离散数学结构第十五章欧拉图与哈密顿图

第十五章欧拉图与哈密顿图15」欧拉图—、欧拉通路、欧拉回路、欧拉图、半欧拉图的定义務定义15・1通过图（无向图或有向图）中所有边一次jl仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。

具有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图。

从定义不难看出，欧拉通路是图中经过所有边的简单的生成通路（经过所有顶点的通路称为生成通路），类似地，欧拉回路是经过所有边的简单的生成回路。

在这里做个规定，即平凡图是欧拉图。

(1) ⑵图15.1在图15」所示各图中QiSSgs为（1冲的欧拉回路所以（1禺为欧拉图oCiGSGb 为（2）中的一条欧拉通路，但图中不存在欧拉回路（为什么？），所以（2 ）为半欧拉图。

（3 ）中既没有欧拉回路，也没有欧拉通路（为什么？），所以（3 ）不是欧拉图，也不是半欧拉图。

CI6C3C4为（4）图中的欧拉回路，所以（4）图为欧拉图。

（5 ） , （ 6 ）图中都既没有欧拉回路，也没有欧拉通路（为什么？）二、判别定理拓定理15・1无向图G是欧拉图当11仅当G是连通图，11 G中没有奇度顶点。

证若G是平凡图，结论显然成立，下面设G为非平凡图，设G是m条边的n阶无向图。

并设G的顶点集V ={v h v2,...,v n}.必要性。

因为G为欧拉图，所以G中存在欧拉回路，设C为G中任意一条欧拉回路，VVi,VjeV , v 都在C上，因而Vi,Vj连通，所以G为连通图。

又V Vi eV，"在C 上每出现一次获得2度，若岀现k次就获得2k度，即d(Vi)二2k ,所以G中无奇度顶点。

充分性，由于G为非平凡的连通图可知，G中边数m21.对m作归纳法。

(1) m=l时，由G的连通性及无奇度顶点可知，G只能是一个环，因而G为欧拉图。

(2) 设mwk(k21)时结论成立，要证明m二K+1时，结论也成立。

由G的连通性及无奇度顶点可知，&(G)、2•类似于例14.8 ,用扩大路径法可以证明G中存在长度大于或等于3的置，设C为G中一个圏，删除C上的全部边，得G的生成子图G,设G有s个连通分支G I,G‘2,...,G；,每个连通分支至多有k条边，且无奇度顶点，并且设G i与C*的公共顶点为, i=l,2，…,S ,由归纳假设可知，G I,G‘2，…,G；都是欧拉图,因而都存在欧拉回路Cl , i=l,2，…,s.最后将C还原(即将删除的边重新加上)，并从C上的某顶*点*开始行遍,每遇到% ,就行遍G'i中的欧拉回路Cl , i二1,2,…,s ,最后回到v r,得回路V「... ... ... "... "... b ... b ...Vr，此回路经过G中每条边一次且仅一次并行遍G中所有顶点，因而它是G中的欧拉回路(演示这条欧拉回路)，故G为欧拉图。

欧拉图和哈密尔顿图

欧拉图和哈密尔顿图

（b）中去掉结点u1和u2以后，p（G–{ u1，u2}）=3， 由此 可以判定，这两个图都不是哈密尔顿图。
用正十二面体代表地球。游戏题的内容是：沿着正十二面体的棱寻
找一条旅行路线，通过每个城市恰好一次又回到出发城市。这便是 Hamilton回路问题。
欧拉回路是指不重复地走过所有路 径的回路，而哈密尔顿环是指不重复地
走过所有的点，并且最后还能回到起点的回 路
哈密尔顿图
定义：通过图G的每个结点一次且仅一次的环称为哈密尔顿环。 具有哈密尔顿环的图称为哈密尔顿图。通过图G的每个结点一次 且仅一次的开路称为哈密尔顿路。具有哈密尔顿路的图称为半哈 密尔顿图。
解一
a
a：说英语； b：说英语或西班牙语； C: 说英语,意大利语和俄语； d：说日语和西班牙语 e：说德语和意大利语； f：说法语、日语和俄语； g：说法语和德语.
b
d
c
e g
f
解 设7个人为7个结点, 将两个懂同一语言的人之间连一条边 (即他们能直接交谈), 这样就得到一个简单图G, 问题就转化为 G是否连通. 如图所示, 因为G的任意两个结点是连通的, 所以 G是连通图. 因此, 上述7个人中任意两个人能交谈.
欧拉图算法
int main() { memset(g,0,sizeof(g)); cin >> n >> e; for (i = 1; i <= e; i++) { cin >> x >> y; g[y][x] = g[x][y] = 1; du[x]++; //统计每个点的度 du[y]++; } start = 1; // 如果有奇点，就从奇点开始寻找，这样找到的就是 for (i = 1; i <= n; i++) // 欧拉路。没有奇点就从任意点开始， if (du[i]%2 == 1) // 这样找到的就是欧拉回路。(因为每一个点都是偶点) start = i; circuitpos = 0; find_circuit(start); for (i = 1; i <= circuitpos; i++) cout << circuit[i] << ' '; cout << endl; return 0; }

欧拉图和哈密尔顿图

欧拉图和哈密尔顿图
欧拉回路是指不重复地走过所有路 径的回路，而哈密尔顿环是指不重复地
走过所有的点，并且最后还能回到起点的回 路
哈密尔顿图
定义：通过图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个人应如何安排座位, 才能使每个人都能与
他身边的人交谈？
解：用结点表示人，用边表示连接的两个人能说讲一种语言，够造

欧拉图与哈密顿图


求欧拉图中欧拉回路的算法
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有;共同语言的人数;

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


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

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

第十五章 欧拉图与哈密顿图
本章的内容 欧拉图 哈密顿图 带权图与货郎担问题 本章的先行知识是第十四章
第一节 欧拉图
历史背景：哥尼斯堡七桥问题与欧拉图
（1） 图1
（2）
其实，欧拉图是一笔画出的边不重复的回路.
一、 欧拉图的定义与判别法 1. 欧拉图的定义 定义 15.1 （1）欧拉通路——经过图中每条边一次且仅一次行遍所有顶点的 通路. （2）欧拉回路——经过图中每条边一次且仅一次行遍所有顶点的 回路. （3）欧拉图——具有欧拉回路的图. （4）半欧拉图——具有欧拉通路而无欧拉回路的图. 几点说明： 规定平凡图为欧拉图. 欧拉通路是生成的简单通路，欧拉回路是生成的简单回路. 环不影响图的欧拉性.
（1）
（2）
（3）
（4）
（5） 图2
（6）
易知，图 2 中， （1）（4）为欧拉图， 、 （2）（5）为半欧拉图， ， （3）（6） ， 既不是欧拉图，也不是半欧拉图. 在（3）（6）中各至少加几条边才能 ， 成为欧拉图？ N 为何值时，无向完全图是欧拉图？为何值时，为半欧拉 图？什么样的完全二部图是欧拉图？
2. 无向欧拉图的判别法 定理 15.1 必要性 无向图 G 是欧拉图当且仅当 G 连通且无奇度数顶点. 设 C 为 G 中一条欧拉回路. 证 若 G 为平凡图无问题. 下设 G 为 n 阶 m 条边的无向图. （1）G 连通显然. （2）viV(G)，vi 在 C 上每出现一次获 2 度，所以 vi 为偶 度顶点. 由 vi 的任意性，结论为真. 充分性 对边数 m 做归纳法（第二数学归纳法）. （1）m=1 时，G 为一个环，则 G 为欧拉图. （2）设 mk（k1）时结论为真，m=k+1 时如下证明：
几点说明： 定理 15.7 是半哈密顿图的充分条件，但不是必要条件. 长度为 n1（n4）的路径构成的图不满足（）条件， 但它显然是半哈密顿图. 定理 15.7 的推论同样不是哈密顿图的必要条件，G 为 长为 n 的圈，不满足（）条件，但它当然是哈密顿 图. 由定理 15.7 的推论可知，Kn（n3）均为哈密顿图.

欧拉图和哈密尔顿图-精


哈密尔顿 图
定义：若图G中有经过所有顶点的基本回路， 称为哈密尔顿回路，若G中含哈密尔顿回路， 则称G为H_图。
定义：经过图G中所有顶点的
○ 基本通路称为哈密尔顿通路， ○ 若G中含哈密尔顿通路， ○ 但不含哈密尔顿回路，则称 ○ G为半哈密尔顿图。
周游世界的游戏—— 的解
哈密顿图
存在哈密顿通路
则G称为以v为始点的随机欧拉图。
随机欧拉 图
注，若G是以v为始点的随机欧拉图，则任何一个以 02 v为始点的不包含G中所有边的回路都应该能扩充成
欧拉回路。反之，若G不是以v为始点的随机欧拉图，
则一定存在已经包含了v所关联的所有边，却未包
含G中所有边的简单回路。
随机欧拉图的判定
[定理] 欧拉图G是以v为始点的随机欧拉图当且仅当G中任一回 路均包含v。
定义：如果图G中仅有欧拉通路，但没有欧拉回路，则图G称为半欧拉 图。
定义：如果图G中含欧拉回路，则图G称为欧拉图。
图G的一个回路/通路,它经过G中每条边恰好一次，则回路/通路称为欧 拉回路/通路。
例 “一笔划”问题——G 中有欧拉通路
实例
上图中，(1) ,(4) 为 欧拉图
例 多米诺骨牌，28块
能否排成一圈使两两相邻的半边的点数相
C 牌 同数 ，问是否可能2？728种 7
将0-6看作7个结点，任2 点的边看作一块骨牌
这样,该问题转化为G有无 欧拉回路的问题
[定理]对连通图，下列命题等价
一．G是欧拉图 二．G的每个结点为
k
边 集 C 1 ,C 2 , ,C k 不 重 叠 之 基 本 回 路 ， 且 偶i U 度= 1 C 数 i E G
短的一条 eg：含20个顶点的完全图中不同的哈密尔顿回路有约6000万亿条-(1.21645 1017)/2，
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2013-6-26 14
计算机科学学院
刘芳
15.1.4 中国邮路问题
例如：
2013-6-26
15
计算机科学学院
刘芳
15.1.4 中国邮路问题
判断条件
定理：
设L是图G的包含所有边的回路，则L具有最小长 度的充分必要条件是：
每条边最多重复一次；
G的每个回路上，所有重复边的长度之和，不 超过该回路长度的一半。
于是有： p（G－ V1 ）≤| V1 | 成立。
2013-6-26 22
计算机科学学院
刘芳
15.2.3 Hamilton图的判定方法
例1：
G | V1 |＝3， p（G－ V1 ）＝4
2013-6-26
G－V1
p（G－ V1 ）≤| V1 |不成立，故G非H图。
23
计算机科学学院
刘芳
15.2.3 Hamilton图的判定方法
2013-6-26
12
计算机科学学院
刘芳
15.1.4 中国邮路问题
问题描述： 设有某邮递员为送信，从邮局出发，到所管辖的街道投
递邮件，最后返回邮局，若必须走遍所辖各街道中每一 条最少一次，则怎样选择投递路线使所走的路程最短？
问题抽象： 将街区用一个图G进行表示，上述问题可以用图论的语
言来描述： 在一个赋权图中，能否找到一条包含每条边最少一次 且长度最短回路？
2013-6-26 13
计算机科学学院
刘芳
15.1.4 中国邮路问题
问题分析
若G不连通，则无解 否则：
若G是欧拉图，则G的欧拉回路就是问题的最优解。 若G是半欧拉图，且邮局就是其中一个奇度点 问题转化为求G的欧拉通路和两点的最短路径问题。 若G中次数为奇数的结点多于2 则回路中必须增加更多的重复边，这时，怎样使 重复边的总长度最小？
定理15.2
无向图G是半欧拉图 G是连通的，且G中恰有2个奇 度顶点
2013-6-26
6
计算机科学学院
刘芳
15.1.3 欧拉图的判定定理
例1：
无欧拉通(回)路
欧拉图
欧拉图
半欧拉图
2013-6-26
半欧拉图
无欧拉通(回)路
7
计算机科学学院
刘芳
15.1.3 欧拉图的判定定理
例2：
A
B
D
C
2013-6-26 8
哥尼斯堡七桥问题
Seven bridges of Kö nigsberg problem A
B
D
问题分析：
2013-6-26
C
3
计算机科学学院
刘芳
15.1.2 欧拉图
定义15.1：
设Ｇ＝＜V，E＞是连通图
欧拉通路（Euler Path） 半欧拉图 (Eulerian) 欧拉回路（Euler Circuit） 欧拉图
2013-6-26 28
计算机科学学院
刘芳
15.2.4 应用举例
例1（排座问题） 有7个人, A会讲英语, B会讲英语和汉语, C会讲英语、意大利
语和俄语, D会讲日语和汉语, E会讲德语和意大利语, F会讲 法语、日语和俄语, G会讲法语和德语.
问：能否将他们沿圆桌安排就坐成一圈, 使得每个人都能与
刘芳
15.2.3 Hamilton图的判定方法
例4：
a
b c
证明右图不是哈密顿图
证：
d
f e 设存在一条哈密顿回路, ∵a,f,g是2度顶点, ∴边(a,c), (f,c)和(g,c)必在这条哈密顿回路上,
g
从而点c出现3次, 与假设矛盾.
故该图不是哈密顿图
2013-6-26 27
说明
规定平凡图是欧拉图； 欧拉通路是简单通路, 欧拉回路是简单回路； 环不影响图的欧拉性。
2013-6-26 4
计算机科学学院
刘芳
15.1.2 欧拉图
实例
2013-6-26
5
计算机科学学院
刘芳
15.1.3 欧拉图的判定定理
无向欧拉（半欧拉）图的判定定理
定理15.1
无向图G是欧拉图 G是连通的且无奇度顶点。
例2：
证明下述各图不是哈密顿图:
(a)
(b)
推论1:哈密尔顿图无割点.
2013-6-26 24
计算机科学学院
刘芳
15.2.3 Hamilton图的判定方法
例3：
证明下述各图不是哈密顿图。
2013-6-26
25
计算机科学学院
刘芳
15.2.3 Hamilton图的判定方法
推论2：
对二部图G＝＜ V1,V2,E＞
规定平凡图是哈密顿图
2013-6-26
20
计算机科学学院
刘芳
15.2.2 Hamilton图的定义
例：判断下图是否为H图？
2013-6-26
21计算机科学学院源自刘芳15.2.3 Hamilton图的判定方法
定理15.6 （必要条件）
设G＝＜V，E＞是H图，则对V的每个非空子集V1均有下
式成立：
计算机科学学院
刘芳
第15章 欧拉图和哈密顿图
15.1 欧拉图 15.2 哈密尔顿图
2013-6-26
1
计算机科学学院
刘芳
15.1 欧拉图
15.1.1 问题引入
15.1.2 欧拉图 15.1.3 欧拉图的判定定理 15.1.4 中国邮路问题
2013-6-26 2
计算机科学学院
刘芳
15.1.1 问题引入
若| V1 |≠| V2 |，则一定不是H图。 证明：
对二部图G＝＜ V1,V2,E＞ 设| V1 |＜| V2 |，则 p(G－ V1)＝| V2 |＞ | V1 | ， 这与定理15.6 p(G－ V1) ＜ | V1 | 相矛盾,故G不是
H图。
2013-6-26 26
计算机科学学院
两旁的人交谈? G A F 解： B 作无向图, 每人是一个顶点, E C 2人之间有边他们有共同的语言. D ACEGFDBA是一条哈密顿回路，按此顺序就坐即可. 2013-6-26
29
计算机科学学院
刘芳
15.2.4 应用举例
例2 货郎担问题（旅行商问题）
（Traveling Salesman Problem）：
12 7
a
d
10
a
a
d
d
b 13
d a
a
5
a
a
a
9
d
e 8
d a
a
6
a
d a a
d
a
a
c
a
11
d
a
d
2013-6-26
31
2013-6-26
18
计算机科学学院
刘芳
15.2.1 问题引入
Willam Rowan Hamilton(1805~1865):
2013-6-26
19
计算机科学学院
刘芳
15.2.2 Hamilton图的定义
定义15.2：
设图G＝＜V，E＞
哈密顿通路 哈密顿回路 半哈密顿图 哈密顿图
说明：
2013-6-26
16
计算机科学学院
刘芳
15.2 Hamilton 图
15.2.1 问题引入
15.2.2 Hamilton图的定义
15.2.3 Hamilton图的判定方法
15.2.4 应用举例
2013-6-26 17
计算机科学学院
刘芳
15.2.1 问题引入
周游世界问题(W.Hamilton, 1859年)
2013-6-26
10
计算机科学学院
刘芳
15.1.3 欧拉图的判定定理
例1
欧拉图
无欧拉通路
无欧拉通路
半欧拉图
2013-6-26
无欧拉通路
半欧拉图
11
计算机科学学院
刘芳
15.1.3 欧拉图的判定定理
例2：
1 0 1 1
0 0 0 1
A B C
问题描述
计算机鼓轮设计中模数转换 问题
问题分析
计算机科学学院
刘芳
15.1.3 欧拉图的判定定理
例3：一笔画问题及推广
问题描述 问题分析
设图中有2k个奇度点，
若k ＝0，可以 一笔画成，且起点和终点相同； 若k ＝1，可以 一笔画成，起点和终点恰为图中 的两个奇度点； 若k ＞1，可以 k笔画成，每笔的起点和终点恰 为图中的两个奇度点；
计算机科学学院
刘芳
15.2.3 Hamilton图的判定方法
哈密顿回路(通路)的充分条件
定理15.7：
设G是n(n3)阶无向简单图, 若任意两个不相邻的顶点u,v有： d(u)+d(v) ≥n-1， 则G中存在哈密顿通路;
推论：
设G是n(n3)阶无向简单图, 若任意两个不相邻的顶点u,v有：d(u)+d(v) ≥n G中存在哈密顿回路，G为哈密顿图;
2013-6-26 9
计算机科学学院
刘芳
15.1.3 欧拉图的判定定理
有向欧拉（半欧拉）图的判定定理
定理15.3
有向图D是欧拉图 D是强连通且所有顶点的入度等 于出度。
定理15.4
有向图D是半欧拉图 D是单向连通的且D中恰有两 个奇度顶点，其中一个顶点的入度比出度大1,一个顶 点的入度比出度小1, 其余的顶点的入度等于出度。