当前位置：文档之家 › 概率论-第二十一讲--欧拉图与哈密尔顿图(略)

概率论-第二十一讲--欧拉图与哈密尔顿图(略)

  • 格式：pdf
  • 大小：269.08 KB
  • 文档页数：20

下载文档原格式

  / 20

合集下载

“欧拉图”例及哈密尔顿图

“欧拉图”例及哈密尔顿图

非哈密尔顿图G中 存在一条从 到 的哈密尔顿链 的哈密尔顿链u 非哈密尔顿图 中，存在一条从u到v的哈密尔顿链 v1v2 … vmv
令
S={vi|[u, vi+1] ∈ E}，T={vi|[vi, v] ∈ E} ，
可知： 可知：S ∩ T= ∅，即|S ∩ T|= 0 又因为v 又因为 ∉ S ∪ T，故|S ∪ T|< n ， 所以： 所以：d(u)+d(v)=|S|+|T|=|S ∪ T|+|S ∩ T|< n 故 δ (G) ≤(d(u)+d(v))/2 < n/2 ， u v1 v2 vi vi+1 vm-1 vm 与δ (G) ≥ n/2矛盾 矛盾 故定理得证 v
货郎问题： 货郎问题：
哈密尔顿图
一个货郎要去n个城市卖货，希望开始于 最后回到v 一个货郎要去 个城市卖货，希望开始于v1，最后回到 1 个城市卖货 每两个城市之间都有一条直接通路， 的距离是W(vi,vj) 每两个城市之间都有一条直接通路，记vi到vj的距离是 问题是：如何找到一条最短路径？ 问题是：如何找到一条最短路径？ 将该问题用图论描述为： 个结点的无向完全图， 将该问题用图论描述为：G=<V,E,W>是n个结点的无向完全图， 是 个结点的无向完全图 对于V中任意三点 对于 中任意三点u, v, k，满足：W(u, v)+W(v, k) ≥ W(u,k) 中任意三点 ，满足： 求G中最短的哈密尔顿图 中最短的哈密尔顿图 至今没有精确有效的算法对货郎问题求解， 至今没有精确有效的算法对货郎问题求解，但是有若干近似算法
公务员考试中的“欧拉图”
三段论是古希腊的亚里士多德发现的推理规律， 三段论是古希腊的亚里士多德发现的推理规律，基本理论 及证明近乎完美。但在公务员的考试中， 及证明近乎完美。但在公务员的考试中，一般只考查直言 三段论，三段论是一种具有固定格式的推理形式，如： 三段论，三段论是一种具有固定格式的推理形式，

欧拉图和哈密而顿图

欧拉图和哈密而顿图

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一定存在一条欧拉通路。

欧拉图和哈密尔顿图

欧拉图和哈密尔顿图

（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个人应如何安排座位, 才能使每个人都能与
他身边的人交谈？
解：用结点表示人，用边表示连接的两个人能说讲一种语言，够造

欧拉图和哈密尔顿图ppt课件

欧拉图和哈密尔顿图ppt课件
有欧拉通路
全部结点为偶结点， 有欧拉回路
有欧拉通路
。a
a、b、c、e
。a
全部结点为
b。 。c 都为奇结点， 。 。 。 无欧拉通路
b。
。c
d
e
f 与欧拉回路 。 。 。
偶结点， 有欧拉回路
d e f 有欧拉通路
ppt课件
8
例7-8 如图街道，是否存在一条投递线路使 邮递员从邮局a出发通过所有街到一次在回 到邮局a?
可达的：在图G中，结点u和结点v之间存在一
条路，则称结点u到结点v是可达的。
ppt课件
2
无向图的连通性
连通：在无向图G中，结点u和结点v之间存在一 条路，则称结点u与结点v是连通的。约定：任一 结点与自身总是连通的。 连通图：若图G中，任意两个结点均连通，则称G 是连通图，否则称非连通图。对非连通图可分成几
个无公共结点的连通分支。无向图中结点间的连通
关系是等价关系。 图是连通的判定法则：从图中任意一结点出发，
通过某些边一定能到达其它任意一结点，则称
图是连通的。
ppt课件
3
练习1：连通图的判定
指出下列各图是否连通
(1)
(2)
(3)
(4)
(5)
(6)
ppt课件 (7)
(8)
4
欧拉图
设G=<V，E>是连通无向图 欧拉通路：在图G中存在一条通路，经过图G 中每条边一次且仅一次。
第二节 图的连通性
通路和回路 无向图的连通性 有向图的连通性 欧拉图 哈密顿图
ppt课件
1
通路和回路 给定图G V , E
通路： G中前后相互关联的点边交替序列 w=v0e1v1e2…envn称为连接v0到vn的通路。 W中边的数目K称为通路W的长。

二部图欧拉图哈密尔顿图平面图教学课件

二部图欧拉图哈密尔顿图平面图教学课件

网络设计：用于设计网络拓扑结构，如路由器、交换机等设备的连接
电路设计：用于设计电路板布局，如PCB板、集成电路等
地图绘制：用于绘制地图，如城市地图、交通地图等
建筑设计：用于设计建筑布局，如房屋、办公楼等
物流规划：用于规划物流网络，如仓库、配送中心等
城市规划：用于规划城市布局，如道路、公园等
汇报人：
哈密尔顿图是平面图的一种特殊情况，即每个顶点的度数都是2
哈密尔顿图定义：每个顶点的度数等于图中的边数
哈密尔顿图的性质：哈密尔顿图是欧拉图
哈密尔顿图的判定方法：通过计算每个顶点的度数来判断
哈密尔顿图的应用：在图论、计算机科学等领域有广泛应用
PART FIVE
平面图是一种特殊的图，其顶点和边都在同一个平面上
哈密尔顿图是一种特殊的图，其每个顶点的度数都是2或0。
哈密尔顿图是一种特殊的欧拉图，其每个顶点的度数都是2。
哈密尔顿图是一种特殊的平面图，其顶点和边都可以在平面上表示出来。
哈密尔顿图是一种特殊的图，其每个顶点的度，即每个顶点的度数都是2
哈密尔顿图是二部图的一种特殊情况，即每个顶点的度数都是2
在数学中，哈密尔顿图可以用于研究图的性质，如图的连通性、图的色数等。
哈密尔顿图在图论中具有重要的应用价值，特别是在网络流、电路设计等领域。
在计算机科学中，哈密尔顿图可以用于解决一些NP-hard问题，如旅行商问题、背包问题等。
在物理学中，哈密尔顿图可以用于描述量子系统的状态空间，从而进行量子计算和量子信息处理。
汇报人：
,
CONTENTS
PART ONE
PART TWO
二部图是一种特殊的图，由两个部分组成，每个部分包含一组节点每个节点只能与另一部分的节点相连，不能与同一部分的节点相连二部图的节点可以分为两个集合，每个集合中的节点只能与另一个集合中的节点相连二部图的边可以分为两种类型，一种是连接两个不同集合的边，另一种是连接同一集合中的边二部图的性质包括：每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边数，每个节点度数之和等于边

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


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

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


例5 设G是非平凡的欧拉图，且v ∈V(G)。证明：G 的每条具有起点v的迹都能扩展成G的欧拉环游当且仅当 G-v是森林。
证明：“必要性”
若不然，则G-v有圈C。 考虑G1=G-E(G)的含有顶点v的分支H。
由于G是非平凡欧拉图，所以G1的每个顶点度数为偶数， 从而，H是欧拉图。
12
1
0.5 n 0
15
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
16
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
17
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
18
1
0.5 n 0
如果邮路图本身是非欧拉图，那么为得到行走环游，必须重 复行走一些街道。于是问题转化为如何重复行走街道？
25
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
2、管梅谷的结论
定理2 若W是图G中一条包含所有边的闭途径，则W在 这样的闭途径中具有最短的长度当且仅当下列两个条件被 满足：
在vi与vi+k间连新边ei得图G*（1≦i≦k).则G*是欧拉图， 因此，由Fleury算法得欧拉环游C.
在C中删去ei （1≦i≦k).得k条边不重的迹Qi （1≦i≦k):
E(G) E(Q1) E(Q2 )
E(Qk )

欧拉图与哈密顿图


*
例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. 哈密顿图是一个连通图，即图中的每两个顶点之间都存在通路。

2. 图中每个顶点都是度数大于等于2的点，即每个顶点都至少连接着两条边。

二、欧拉图的定义与性质欧拉图是指一种可以通过图中每条边恰好一次的路径来穿越图的图。

具体来说，欧拉图是一个简单图，其中经过图中每条边且路径不重复的路径称为欧拉路径，而形成闭合回路的欧拉路径称为欧拉回路。

欧拉图具有以下的性质：1. 每个顶点的度数都是偶数，即每个顶点都连接着偶数条边。

2. 欧拉图中至少有两个连通分量，即图中有至少两个不同的部分可以从一部分通过路径到达另一部分。

三、哈密顿图与欧拉图的应用哈密顿图和欧拉图在实际生活中有广泛的应用，下面将分别介绍它们的应用领域。

1. 哈密顿图的应用：哈密顿图在旅行商问题中有着重要的应用。

旅行商问题是指一个旅行商要依次拜访若干个城市，然后返回起始城市，而要求找到一条最短的路径使得每个城市都被访问一次。

哈密顿图可以解决这个问题，通过寻找一条哈密顿路径来确定最短的路径。

2. 欧拉图的应用：欧拉图在电路设计和网络规划中发挥着重要的作用。

在电路设计中，欧拉图可以帮助我们确定如何安排电线的布线以最大程度地减少电线的长度和复杂度。

在网络规划中，欧拉图可以用于确定如何正确地连接不同的网络节点以实现高效的信息传输。

四、结论哈密顿图和欧拉图是图论中的两个重要概念。

哈密顿图是一种包含了图中所有顶点的路径的图，而欧拉图是一种可以通过图中每条边恰好一次的路径来穿越图的图。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
16
二、哈密尔顿图
例5. 证明下图中没有汉密尔顿路径。 图中，3个顶点标记为A，5个顶点 A 标记为B，相差2个，不可能存在 一条汉密尔顿路径。 B B 如果在标记过程中，遇到相邻结 点出现相同标记时，如果有一个 结点的度数为2，可在此对应边上 A A 增加一个结点，并标上相异标 A 记。 B B B B B
11
二、哈密尔顿图
定理3：若无向图G=<V,E>是哈密尔顿图， V1是V的任意非空 真子集，则 ω(G- V1)≤| V1 |。 证明：设C是G的一条哈密尔顿回路，对于V的每个非空真子集 V1有：ω(C-V1) ≤|V1|
ω(C- V1)是C删去V1中所有顶点及关联的边后所得图
的连通分支数。 又因为C - V1是G - V1的生成子图，故有
13
二、哈密尔顿图
定义3：若无向图G＝<V,E>的顶点集合V可以划分成两个子集X 和Y，使G中的每一条边e的一个端点在X中，另一个端点 在Y中，则称G为二部图或偶图。二部图可记为 G＝<X,E,Y>，X和Y称为互补结点子集。 二部图不会有自回路。
14
二、哈密尔顿图
定理4：设二部图G=<X, E, Y>，设|X|=m，|Y|=n。若m≠n，则G 必不是汉密尔顿图。 证明：方法1. 用汉密尔顿图的性质证明。 因为|X|≠|Y|，不妨设|X|<|Y|。 显然有ω(G-X)=|Y|>|X|， 这与汉密尔顿图的必要条件ω(G-X)≤|X|矛盾。 因此G必不是汉密尔顿图。
定理2：一个有向连通图具有欧拉路径，当且仅当它 的每个顶点的引入次数等于引出次数，可能 有两个顶点除外，其中一个的引入次数比它 的引出次数大1，另一个的引入次数比它的 引出次数小1。 推论： 一个有向连通图具有欧拉回路，当且仅当它 的每个顶点的引入次数等于引出次数。
5
一、欧拉图
例2
(a)
(b)
(c)
15
二、哈密尔顿图
定理4：设二部图G=<X, E, Y>，设|X|=m，|Y|=n。若m≠n，则G 必不是汉密尔顿图。 证明：方法2. 用二部图的性质证明。 因为|X|≠|Y|,不妨设 |X|<|Y|。 假设G是汉密尔顿图，则G中存在汉密尔顿回路C。因为 |X|<|Y|，所以在C中必然存在u,v∈Y，且u,v在C中邻接。因 此边(u, v) ∈E，这与二部图中任何一条边一个端点在X中另 一个端点在Y中矛盾。 因此G必不是汉密尔顿图。 推论：设二部图G=<X, E, Y>，设|X|=m，|Y|=n。若|m-n|>1， 则G中必不存在汉密尔顿路径。
10
二、哈密尔顿图
目前还没有找到一个简明的条件来作为哈密尔顿回路存 在的充要条件。 必要条件： 定理3：若无向图G=<V,E>是哈密尔顿图， V1是V的任意非空 真子集，则 ω(G- V1)≤| V1 |。 | V1 |：V1的基数，
ω(G- V1)：G删去V1中所有顶点及关联的边后所得图
的连通分支数。
欧拉图与哈密尔顿图
一、欧拉图
Konigsberg(哥尼斯堡)七桥问题：
1
一、欧拉图
定义1：设G=<V,E>是不含孤立顶点的无向图， 若G中存在一条路径经过G中每条边一次且仅一次的路径， 称为欧拉路径； 若G中存在一条回路经过G中每条边一次且仅一次的回路称 为欧拉回路；具有欧拉回路的图称为欧拉图。 即“一笔画问题”，每条边画且仅画一次，一笔画完。若回 到出发点，则为欧拉图；回不到出发点，则有欧拉路径。
7
二、哈密尔顿图
环球航行问题： 英国数学家Hamilton１８５９年提出的一种 游戏。一个实心的正十二面体的20个顶点标上世 界著名大城市的名字，要求游戏者从某一城市出 发，遍历各城市一次且仅一次，最后回到原地。 即“周游世界”问题。
8
二、哈密尔顿图
9
二、哈密尔顿图
定义2：在无向图G=<V,E>中， 经过G中的每个顶点一次且仅一次的路径称为哈密尔 顿路径。 经过G中的每个顶点一次且仅一次的回路称为哈密尔 顿回路。具有哈密尔顿回路的图称为哈密尔顿图。
2
一、欧拉图
定理1：无向连ቤተ መጻሕፍቲ ባይዱ图G具有一条欧拉路径，当且仅当 G具有零个或者两个奇数次数的顶点。 推论：无向连通图G具有一条欧拉回路，当且仅当 其顶点次数都是偶数。
3
一、欧拉图
例1
(a) (a)是欧拉图；
(b)
(c)
(b)不是欧拉图，但存在欧拉路径； (c)既不是欧拉图，也不存在欧拉路径。
4
一、欧拉图
A 若图具有哈密尔顿路径，则A和B 数目要么相等，要么相差1。 （逆不成立）
17
二、哈密尔顿图
充分条件： 定理4：设G=<V,E>是具有n≥3个顶点的简单无向图， 若在G中每一对顶点的次数之和大于等于n， 则在G中存在一条哈密尔顿回路。 定理5：设G=<V,E>是具有n≥3个顶点的简单无向图， 若在G中每一对顶点的次数之和大于等于n-1， 则在G中存在一条哈密尔顿路径。 注意：定理4、5的逆定理不成立。
ω(G- V1)≤ ω(C- V1) ≤ | V1 | 。
该定理可用来判定某些无向图不是哈密尔顿图。
12
二、哈密尔顿图
例4(a)
V
令V1＝{v}, ω(G- V1)=2>|V1| 所以G非哈密尔顿图。
G
(b) 任意非空集 V 1 ⊆ V 有 ω(G- V1) ≤ | V1 | 但G却非哈密尔顿图－－典型例子。 说明定理3逆定理不成立。
18
二、哈密尔顿图
判断下图是不是哈密尔顿图?
图中 (1), (3),不是哈密尔顿图,(2) 为哈密尔顿图。
19
作业 P262 8-2习题 14，15
20
(a)是欧拉图； (b)不是欧拉图，但存在欧拉路径； (c)既不是欧拉图，也不存在欧拉路径。
6
一、欧拉图
例3. 一块多米诺骨牌排是由两个半面组成的。这些方块被 表明1、2、3、4、5、6个点或空白。问：是否可能将 28块不同的多米诺骨牌排成一个圆环,使得在这个排列 中,每两块相邻的多米诺骨牌其相邻的两个半面是相同 的。 解：构造一个具有7个顶点的图,这些顶点对应于空白、1、 2、3、4、5和6,在每两个顶点之间都有一条边,我们把 这条边当作一块多米诺骨牌,并且把这条边相关联的两 个顶点当作它的两个半面。图中28条边恰好对应28块 不同的多米诺骨牌，因此圆环排列问题对应于图中是 否存在一条欧拉回路，因为每个顶点的度数都为8，所 以欧拉回路是存在的。