下载文档原格式
电⼦科技⼤学《图论及其应⽤》复习总结--第四章欧拉图与哈密尔顿图第四章欧拉图与哈密尔顿图(⼀)、欧拉图及其性质(1)、问题背景---欧拉与哥尼斯堡七桥问题问题：对于图G，它在什么条件下满⾜从某点出发，经过每条边⼀次且仅⼀次，可以回到出发点？注：⼀笔画----中国古⽼的民间游戏（存在欧拉迹）要求：对于⼀个图G, 笔不离纸, ⼀笔画成.拓展：三笔画：在原图上添加三笔，可使其变为欧拉图。
定义1 对于连通图G，如果G中存在经过每条边的闭迹，则称G为欧拉图，简称G为E图。
欧拉闭迹⼜称为欧拉环游，或欧拉回路。
定理1 下列陈述对于⾮平凡连通图G是等价的：(1) G是欧拉图；(2) G的顶点度数为偶数；(3) G的边集合能划分为圈。
推论1 连通图G是欧拉图当且仅当G的顶点度数为偶。
推论2 连通⾮欧拉图G存在欧拉迹当且仅当G中只有两个顶点度数为奇数。
证明：若G和H是欧拉图，则G×H是欧拉图。
若G是⾮平凡的欧拉图，则G的每个块也是欧拉图。
(⼆)、Fleury算法(欧拉图中求出⼀条具体欧拉环游的⽅法)⽅法是尽可能避割边⾏⾛(三)、中国邮路问题（最优欧拉环游，管梅⾕）定理2 若W是包含图G的每条边⾄少⼀次的闭途径，则W具有最⼩权值当且仅当下列两个条件被满⾜：(1) G的每条边在W中最多重复⼀次；(2) 对于G的每个圈上的边来说，在W中重复的边的总权值不超过该圈⾮重复边总权值。
(四)、哈密尔顿图的概念定义1 ：如果经过图G的每个顶点恰好⼀次后能够回到出发点，称这样的图为哈密尔顿图，简称H图。
所经过的闭途径是G的⼀个⽣成圈，称为G的哈密尔顿圈。
定义2: 如果存在经过G的每个顶点恰好⼀次的路，称该路为G的哈密尔顿路，简称H路。
(五)、哈密尔顿图性质与判定1、性质定理【必要条件】；定理1 (必要条件) 若G为H图，则对V(G)的任⼀⾮空顶点⼦集S，有：w(G−S)≤|S|注：不等式为G是H图的必要条件，即不等式不满⾜时，可断定对应图是⾮H、图。
1-tough条件下哈密尔顿图的一个充分条件的开题报
告
哈密尔顿图是一种特殊的图，指包含一条经过所有节点的路径（即
哈密尔顿路径）的无向图。
而对于哈密尔顿路径的研究，则可以得到哈
密尔顿回路，即由哈密尔顿路径组成的闭合路径。
在实际应用中，哈密尔顿图在计算机科学中扮演着重要的角色，如
在旅行推销员问题、电路设计、图形路由、自动化制造等领域中都有广
泛应用。
然而，在某些情况下，哈密尔顿图的计算问题变得异常困难。
例如，在NP难问题条件下，哈密尔顿图的求解可能会变得不可行。
因此，研究哈密尔顿图的充分条件可以帮助我们理解其计算难度并找到更高效的解
决方法。
在该项目中，我们将探讨哈密尔顿图的充分条件之一：tough条件。
tough条件是由图论家F.T. Leighton于1979年首次提出的，它被定义为：
对于任意无向图G，设L(G)表示其最长路径的长度，n表示其节点数，则G满足tough条件当且仅当：
对于所有2 <= k <= n/2，有：
k <= L(G)/(n-k+1)
即对于每个k，一个由图上取任意k个节点组成的子集，不会比大于n-k+1个节点的子集短得太多。
tough条件是充分而非必要条件，即如果一个图满足tough条件，则它一定是哈密尔顿图；但如果一个图不满足tough条件，则不能确定它
是不是哈密尔顿图。
因此，我们将研究一些样例并比较它们是否满足tough条件和是否是哈密尔顿图，以更深入地理解这个条件的特性和重要性。
最后，我们将讨论tough条件的实际应用以及与其他哈密尔顿图条件的关系，以展示该充分条件对于哈密尔顿图研究的价值和意义。
哈密尔顿图的刻画Characterization of Hamiltonian Graphs哈密尔顿图问题属于NPC问题哈密尔顿图的刻画一直是图论中的重要课题之一本节将介绍几个基本结果哈密尔顿图中一定不存在悬挂边存在哈密尔顿道路的图中不存在孤立顶点n > 2时，K n 是哈密尔顿图14233412 1 2 4 3 1 2 4 3只要图G中有“足够多”的边，那么它就会是哈密尔顿图定理设G是n（n≥2）阶简单图，如果G中任一对顶点u和v，都满足deg(u)+deg(v)≥n-1，则G 中存在哈密尔顿道路（ Ore ，1960 ）设G 是n（n≥3）阶简单图，如果G中任一对顶点u 和v，都满足deg(u)+deg(v)≥n，则G是哈密尔顿图推论1（Dirac，1952 ）设G是n（n≥3）阶简单图，如果G中任一顶点的次数都至少是n/2，则G是哈密尔顿图推论2设G是一(n, m)简单图，若m≥(n2-3n+6)/2，则G是哈密尔顿图。
如果图中存在2个顶点u, v 使得deg(u)+deg(v)<n则在图G中删去这2个点，构成n-2 阶简单图G ’G ’中的边数为m’≥m-(deg(u)+deg(v))> (n2-3n+6)/2-n= (n-2)(n-3)/2与G ’是简单图矛盾。
因此，G中任一对顶点u 和v，都满足deg(u)+deg(v)≥nG是哈密尔顿图u vG G’注意上述结果都是充分条件，不满足这些条件的图也可能是哈密尔顿图n=6deg(v)=2<n/2for any vertex vm=6(n2 3n+6)/2=12例假设在n（n≥4）个人中，任意两人合在一起能认识其余的n-2个人，则他们可以围成一圈，使相邻者相识。
证明以每个人为一顶点，相识者之间加边，便构成一个图G问题转化为证明图G是哈密尔顿图对于任意两顶点u, v，若u, v代表的两人相识，则deg(u)+deg(v) ≥n-2 +1+1 = nu vn-2哈密尔顿图的刻画证明对于任意两顶点u, v，若u, v 代表的两人不相识他们两人合在一起能认识其余的n-2个人假设存在顶点w与u相邻，则必然有w与v相邻，否则u, w代表的两人合在一起仍然不认识v代表的人同理，若存在顶点w与v 相邻，则必然有w 与u 相邻这说明u,v 代表的两人都认识其余的全部n-2个人，于是deg(u)+deg(v) = n-2+n-2 ≥n可知图中存在哈密尔顿回路，即所有人可以围成一圈，使相邻者相识11 u vwE nd。
图论中的哈密尔顿回路与最短路径问题在图论中，哈密尔顿回路与最短路径问题是两个重要的研究方向。
本文将主要讨论这两个问题的定义、性质以及解决方法，并分析它们在实际应用中的重要性。
一、哈密尔顿回路问题哈密尔顿回路问题是指在给定的无向图中，是否存在一条包含每个顶点且只经过一次的闭合路径。
如果存在这样的路径，我们称之为哈密尔顿回路；否则，该图没有哈密尔顿回路。
1.1 哈密尔顿回路的定义与性质对于一个含有n个顶点的图，哈密尔顿回路可以定义为一条包含n 个顶点的简单回路。
具有哈密尔顿回路的图称为哈密尔顿图，没有哈密尔顿回路的图则称为非哈密尔顿图。
哈密尔顿回路问题具有以下性质：（1）哈密尔顿回路是NP完全问题：寻找哈密尔顿回路的过程是一个指数级的搜索问题，目前还没有找到多项式时间内解决该问题的算法。
（2）哈密尔顿回路问题的判定问题是NP问题：判断一个给定图是否存在哈密尔顿回路可以在多项式时间内完成。
1.2 解决哈密尔顿回路问题的方法由于哈密尔顿回路问题的复杂性，目前没有找到通用的解决方法。
但是对于一些特殊类型的图，可以使用一些常见的算法来求解。
（1）回溯法：回溯法是一种穷举搜索算法，通过遍历图中所有可能的路径，判断是否满足哈密尔顿回路的条件。
然而，由于搜索空间巨大，回溯法在大规模图中的效率较低。
（2）启发式算法：启发式算法是一种基于经验和启发性规则的优化算法。
例如，蚁群算法和遗传算法在解决哈密尔顿回路问题上取得了一定的成果。
二、最短路径问题最短路径问题是指在给定的带权有向图或无向图中，寻找两个顶点之间具有最短路径的问题。
最短路径可以根据路径上的边权重之和来定义。
2.1 最短路径问题的定义与性质对于一个含有n个顶点的图，最短路径可以定义为一条连接两个顶点的路径，且路径上的边权重之和最小。
如果没有这样的路径存在，则称两个顶点之间不存在最短路径。
最短路径问题具有以下性质：（1）最短路径问题是一个经典的优化问题：寻找最短路径是一种典型的组合优化问题，目前已经有多种高效的算法可以解决该问题。
