下载文档原格式
离散数学-图论-哈密顿图及其应⽤哈密顿图⼀、定义概念1.哈密顿通路设G=<V,E>为⼀图（⽆向图或有向图）.G中经过每个顶点⼀次且仅⼀次的通路称作哈密顿通路2.哈密顿回路G中经过每个顶点⼀次且仅⼀次的回路（通路基础上+回到起始点）称作哈密顿回路3.哈密顿图若G中存在哈密顿回路，则称它是哈密顿图4.定义详解：（1）存在哈密顿通路（回路）的图⼀定是连通图；（2）哈密顿通路是初级通路，哈密顿回路是初级回路；（3）若G中存在哈密顿回路，则它⼀定存在哈密顿通路，反之不真（看课本的话，是必要条件，⽽不是充分条件，故不可反推！）（4）只有哈密顿通路，⽆哈密顿回路的图不叫哈密顿图；即，哈密顿图是回路⼆、判定定理注意：⽬前还没有找到哈密顿图的简单的充要条件（1）设⽆向图G=<V,E>为哈密顿图，V1是V的任意真⼦集，则（注：n阶xx图指的是n个顶点，不要迷！）p(G-V1)<=|V1|其中，p(G-V1)为G中删除V1后的所得图的连通分⽀数⽬，|V1|为V1集合中包含的顶点个数。
【哈密顿图存在的必要条件】推论：有割点的图⼀定不是哈密顿图设v是图中的割点，则p(G-v)>=2,由上述定理知G不是哈密顿图（2）设G是n(n>=3)阶⽆向简单图，若对于G中的每⼀对不相邻的顶点u,v,均有d(u)+d(v)>=n-1则G中存在哈密顿通路。
⼜若d(u)+d(v)>=n则G中存在哈密顿回路，即G为哈密顿图。
【哈密顿图存在的充分条件，不是必要条件】其中d(u),d(v)分别代表顶点u,v的度数。
推论：设G是n(n>=3)阶⽆向简单图，若G的最⼩度>=n/2,则G是哈密顿图。
由推论知，对于完全图Kn,当n>=3时，是哈密顿图，完全⼆部图Kr,s当r==s>=2时是哈密顿图。
（3）在n(n>=2)阶有向图D=<V,E>中，如果略去所有有向边的⽅向，所得⽆向图中含⽣成⼦图Kn,则D中存在哈密顿通路。
离散结构哈密顿图教学目标基本要求（1）哈密顿图的定义（2）哈密顿图的充分条件与必要条件（3）哈密顿图的应用重点难点（1）哈密顿图的判定（2）哈密顿图的应用1859年提出一个名叫“周游世界”的游戏，问题是：能否遍历正12面体的每个顶点一次且仅一次后回到原地。
？哈密顿（爱尔兰数学家）定义•哈密顿通路——经过图中所有顶点一次仅一次的通路.•哈密顿回路——经过图中所有顶点一次仅一次的回路.•哈密顿图——具有哈密顿回路的图.•半哈密顿图——具有哈密顿通路且无哈密顿回路的图.•几点说明：–平凡图是哈密顿图.–哈密顿通路是初级通路，哈密顿回路是初级回路.–环与平行边不影响哈密顿性.–哈密顿图的实质是能将图中的所有顶点排在同一个圈上实例在上图中，•(1),(2) 是哈密顿图;•(3)是半哈密顿图;•(4)既不是哈密顿图，也不是半哈密顿图，为什么？哈密顿图的必要条件•定理设无向图G =<V ,E >是哈密顿图，对于任意V 1⊂V 且V 1≠∅，均有p (G −V 1) ≤|V 1|•推论设无向图G=<V ,E>是半哈密顿图，对于任意的V 1⊂V 且V 1≠∅均有p (G −V 1) ≤|V 1|+1•几点说明–定理中的条件是哈密顿图的必要条件，但不是充分条件（例如彼得松图）–由定理可知，K r ,s 当s ≥r +1时不是哈密顿图. 易知K r ,r （r ≥2）时都是哈密顿图，K r ,r +1都是半哈密顿图.哈密顿图的充分条件•定理设G是n阶无向简单图，若对于任意不相邻的顶点v,v j，均有id(v i)+d(v j) ≥n−1则G 中存在哈密顿通路.,v j，均有•推论设G为n(n≥3) 阶无向简单图，若对于G中任意两个不相邻的顶点vid(v i)+d(v j) ≥n则G中存在哈密顿回路，从而G为哈密顿图.•几点说明–定理是半哈密顿图的充分条件，但不是必要条件. 长度为n−1（n≥4）的路径构成的图不满足条件，但它显然是半哈密顿图.–推论同样不是哈密顿图的必要条件，G为长为n的圈，不满足条件，但它当然是哈密顿图.例在给出的三个图中哪些是哈密顿图？哪些是半哈密顿图？为什么？例试判断下面在给出的图是欧拉图还是哈密顿图？判断某图是否为哈密顿图至今还是一个难题.哈密尔顿图的应用例：一只蚂蚁可否从立方体的一个顶点出发，沿着棱爬行，它爬过每一个顶点一次且仅一次，最后回到原出发点？试利用图作解释。
文献综述信息与计算科学哈密顿图的判定与应用图论(graphic theory)是一门既古老又年轻的学科. 它诞生于18世纪上半叶. 到19世纪下半叶这个领域才发展成为数学的一个系统的分支, 直到20世纪上半叶, 这门学科才有自己的著作出现. 自20世纪下半叶开始, 随着计算机科学与技术的发展, 图的理论研究和应用研究才得到迅速广泛的重视, 图论作为一个数学的分支, 才真正确立了自己的地位.哈密顿(爱尔兰科学家)在1859年提出一个名叫“周游世界”游戏问题是: 能否遍历正12面体的每个顶点一次且一次后回到原地. 由此引申出哈密顿图的定义: 如果图G 上有一条经过图G 所用顶点一次且仅一次的回路, 则称此回路为哈密顿回路, 具有哈密顿回路的图称为哈密顿图.哈密顿图具有六个领域: 哈密顿圈, H 连通, 泛圈, 点泛圈, 边泛圈, 泛连通. 哈密顿图是有哈密顿圈的图. 至今没有一个像欧拉图的充要条件那样的“非平凡的” (不是定义的同义反复)关于哈密顿图、哈密顿通路的充分必要条件, 但关于他们的充分性和必要性分别有一些研究成果. 而哈密顿图不光在金字塔图、扇面蜂巢图及马图上有体现它性质的研究, 且在四正则连环图和彼得森中有它独特的应用. 而且哈密顿图在哈密顿通路、哈密顿轨、多哈密顿轨问题上也有很多细致的研究和应用.1984年时在连续10年排名加拿大第一大学的范更华教授得到名垂青史的“范定理”: 2连通n 阶图G 的距离是2的任意两点,x y 均有max{(),()}/2d x d y c ≥, 则G 是有c 圈, 当c n =时是哈密顿图. 当然, 关于如此著名的范定理, 各国不少专家也对范定理企求做出改进发展. 1987年Wojda 院士和欧洲最古老的著名大学之一的法国奥大的运筹学科创建奠基人Benhocine 教授2人合作仅局部推广上面范定理. 又如法国 Benhocine 教授1977年发表在法国科学院学报的哈密顿图论文就一直有国际影响, 但他至今仅有25篇数学论文且18篇是哈密顿图的, 他是排名哈密顿图研究前30名大师之一.哈密顿图已经历了一个多世纪的跋涉, 容易攀登的时代已经过去了, 其进展已非常不容易, 如此即使是世界级的大师泰斗, 不论你多么聪明利害都好, 面对的下一个问题猜想都永远是相关学科的全世界的专家经过多年仍不能解决的, 就是想做点进展都非常不容易, 每一篇论文都是超越最权威大师的成果. 哈密顿图的难如两个权威说“非常不容易”. 但它却具有重大历史意义以及广泛而重要的应用价值.现国际数学联盟主席是哈密顿图权威, 并且琼州大学赵克文和美国权威等合作改进耶鲁大学Ore 院士等大师权威的代表性结果已在“哈密顿图”居世界领先.在国内, 宁宣熙和宁安琪提出了哈密顿圈自组织算法的实证研究结果和其在哈密顿图判定上的应用, 介绍了SOA 算法在大约 12000个规模不同(104000,208000n m =-=-)的一般任意图中构造哈密顿圈的实证研究结果, 验证了SOA 算法的可靠性和时间的多项式性. 在此基础上论证了SOA 算法用于判断一般任意图是否为哈密顿图的可行性, 并用一些实例进行了实证研究. 在阻塞流理论的研究中, 利用网络最小阻塞流与哈密顿轨之间的关系建立了哈密顿轨问题的无环最小支撑流模型. 通过这个模型可以把一步内构造无环最小支撑流这一数学难题分解成分别在多项式时间内完成的两个阶段, 从而为解决这一数学难题找到了新的思路, 开发研制了在一般任意图中构造哈密顿圈的自组织算法(或SOA 算法). 在文献[14]-, 全面详细地介绍了作者经过10多年潜心研究这一算法的理论及进行12000余例实证研究的结果. 到目前为止尚未遇到反例. 由于不少学者根据NPC 理论认定这是绝对不可能的, 因此作者只好通过大量的实证研究来显示这一多项式算法存在的可能性. 况且, 作者进行这项研究的目的并不是为了解决计算复杂性理论中NP 是否等于P 的问题, 而是为学术研究和工程应用提供一种在一般图中构造哈密顿圈的实用有效工具. 即便有人能找到反例, 说明SOA 算法只不过是像线性规划单纯形算法那样, 是一个实用的好算法, 应当说这也是一个很幸运的结果. 因为有了它, 不但可以在用相关定理(如范定理或者其它更新的定理)判定存在哈密顿圈的一般图中构造出至少一条具体的哈密顿圈, 也可以对超出这些定理范围之外的一般图进行是否是哈密顿图的判定, 这岂不也是一项有实用价值的成果. 如果这些研究结果还能对数学家们在解决哈密顿图判定的理论研究上有所启迪和帮助, 那么这项研究就更有意义了.回溯法是一种按照深度优先的策略从根结点开始搜索解空间树的算法, 该算法可以用来求出问题的全部解, 也可以在求出问题的一个解之后停止对问题的求解, 即只求该问题是否有解[5]. 哈密顿通路就是判断图中是否存在一条通过所有顶点一次且仅一次的路径. 宁夏大学数学计算机学院的刘向娇博士在他的《用回溯法求哈密顿通路》论文中论述了用回溯法来求解一个任意的图中是否存在一条哈密顿通路的问题, 并用具体的算法来实现它. 算法搜索至解空间树的任一结点时, 总是先判断该结点是否肯定不包含问题的解. 如果肯定不包含, 则跳过对以该结点为根的子树的系统搜索, 逐层向其祖先结点回溯. 否则, 进入该子树, 继续按深度优先的策略进行搜索. 回溯法在用来求问题的所有解时, 要回溯到根, 且根结点的所有子树都已被搜索遍才结束[6]. 而回溯法在用来求问题的任一解时, 只要搜索到问题的一个解就可以结束. 这种以深度优先的方式系统地搜索问题的解的算法称为回溯法, 它适用于解一些组合数较大的问题.在求解一些问题(如走迷宫、地图着色等问题)时, 题目的要求可能是求出原问题的一种或所有可能的解决方案. 这类问题的解往往是由一个一个的步骤或状态所构成的, 每一步骤又有若干种可能的决策方案; 由于没有固定、明确的数学解析方法, 往往要采用搜索的做法, 即从某一个初始状态出发, 不断地向前(即下一个状态)搜索, 以期最终达到目标状态, 从而得到原问题的一个解或所有的解. 在搜索的过程中, 由于问题本身及所采取的搜索方法的特点(如在缺乏全局及足够的前瞻信息的情况下进行搜索等)[7], 会导致走到某一状态就走不下去的情况, 这时, 就必须回头(即回到上一步, 而不是回到最初的状态), 再尝试其他的可能性, 换一个方向或方法再试试. 这样, 不断地向前探索、回溯, 再向前、再回溯, 直至最终得出问题的解, 或者一路回溯到出发点(出现这种情况即表示原问题无解)[8]. 注意, 这种搜索过程并不是尝试搜索问题解空间中所有的可能状态和路径, 而是采用深度优先的方式, 沿着一条路径, 尽可能深入地向前探索.用回溯法解哈密顿通路问题首先要画出问题的解空间树, 该解空间树是一棵最大度是n的树(其中n为图中的顶点数), 树中只有第一个结点的度是n, 其余结点的度都为n (该结点不用与其自身相连). 在编写算法时可以通过判断该边在图的邻接矩阵中的值1来剪枝, 如果其值不是1则说明该边不存在则剪枝不用搜索. 由于在求图的哈密顿通路时走过的顶点不能再重复走, 所以要对已经遍历过的顶点做一个标记, 如果在搜索时找到的是一个带有标记的顶点, 那么该路径也是不可行的, 应剪去.参考文献[1] 宁宣熙, 堵塞流理论及其应用[M]. 北京: 科学出版社, 2005.[2] Xuanxi Ning and Angelika Ning, The Blocking Flow Theory and its Application to Hamiltonian Graph Problems[J]. Shaker Verlag. Aachen, 2006, 21(2): 286~318.[3] Ning Xuanxi. The Minimum Spanning Flow in a Network and its Self-organization Principle[J]. The International Journal of Systems & Cybernetics, 2004, 33(2): 331~338. [4] Xuanxi Ning and Angelika Ning, The Minimum Spanning Flow Model of the Hamiltonian Path Problem in a Digraph and its Polynomial Algorithm[J]. Information Processing and Management, 2006, 38(3): 356~361.[5] 同济大学应用数学系. 离散数学[M]. 上海: 同济大学出版社, 2003.[6] 同济大学应用数学系. 离散数学[M]. 上海: 同济大学出版社, 2003.[7] 王小东. 算法分析与设计[M]. 北京: 清华大学出版社, 1900.[8] 付寒冰, 周恒为. 数据结构中常用的三类算法[J]. 伊犁师范学院学报, 1997, 17(2): 12~138.[9] 宁安琪, 宁宣熙. 金字塔图的哈密顿图性质研究[J]. 南京航空航天大学经济与管理学院学报, 2006, 21(3): 17~23.[10] 田媛, 刘铎. 金字塔图存在哈密顿回路的构造性证明[J]. 清华大学学报, 2007, 13(2): 38~52.[11] 屈婉玲, 耿素云. 离散数学[M]. 北京: 高等教育出版社, 2008.[12] J.邦詹森, G.古廷. 有向图的理论、算法及其应用[M]. 北京: 科学出版社, 2009.[13] 左孝凌. 离散数学[M]. 北京: 经济科学出版社, 2000.。
定义4.3.1 经过图G 的每个顶点恰一次的路称为G 的Hamilton 路，简称为H 路。
经过图G 的每个顶点恰一次的圈称为G 的Hamilton 圈，简称为H 圈。
具有Hamilton 圈的图称为Hamilton 图，简称为H 图。
Hamilton 图的研究起源于一种十二面体上的游戏。
1857 年，爱尔兰著名数学家William Rowan Hamilton 爵士（他也是第一个给出复数的代数描述的人）制作了一种玩具，它是一个木制的正十二面体，在正十二面体的每个顶点上有一个木栓，并标有世界著名城市的名字。
游戏者用一条细线从一个顶点出发，设法沿着十二面体的棱找出一条路，通过每个城市恰好一次，最后回到出发点。
这个游戏当时称为Icosian 游戏，也称为周游世界游戏。
将正十二面体从一个面剖开并铺展到平面上得到的图形如下图所示，称为十二面体图。
周游世界游戏用图论术语来说就是判断十二面体图是否Hamilton 图，并设法找出其Hamilton 圈。
其中一条Hamilton 圈如图中粗边所示。
十二面体图是H 图判断一个图是否Hamilton 图与判断一个图是否Euler 图似乎很相似，然而二者却有本质的不同。
目前为止尚没有找到判别一个图是否是Hamilton 图的有效充要条件。
这是图论和计算机科学中未解决的重要难题之一。
本节给出一些经典的充分条件和必要条件。
一、必要条件定理4.3.1 设G 是二部图，若G 是H 图，则G 必有偶数个顶点。
证明：设G = (X, Y ) ，由于G 的边全在X 和Y 之间，因此如果G 有Hamilton 圈C，则G的所有顶点全在C 上，且必定是X 的点和Y 的点交替在C 上出现，因此G 必有偶数个顶点。
证毕。
这个定理给出了一个二部图不是Hamilton 图的简单判断条件：如果一个二部图有奇数个顶点，则它必定不是Hamilton 图。
例如，下列Herschel 图是二部图，但有奇数个顶点，故不是H 图。
图论中的哈密顿图与欧拉图图论是数学的一个分支，研究图的性质及其应用。
在图论中，哈密顿图和欧拉图是两个重要的概念。
本文将介绍哈密顿图和欧拉图的定义、性质和应用，并探讨它们在现实生活中的实际应用。
一、哈密顿图的定义与性质哈密顿图是指一种包含了图中所有顶点的路径的图。
具体来说，哈密顿图是一个简单图，其中任意两个不同的顶点之间都存在一条路径，使得该路径经过图中的每个顶点且不重复。
哈密顿图具有以下的性质：1. 哈密顿图是一个连通图，即图中的每两个顶点之间都存在通路。
2. 图中每个顶点都是度数大于等于2的点，即每个顶点都至少连接着两条边。
二、欧拉图的定义与性质欧拉图是指一种可以通过图中每条边恰好一次的路径来穿越图的图。
具体来说，欧拉图是一个简单图，其中经过图中每条边且路径不重复的路径称为欧拉路径，而形成闭合回路的欧拉路径称为欧拉回路。
欧拉图具有以下的性质：1. 每个顶点的度数都是偶数，即每个顶点都连接着偶数条边。
2. 欧拉图中至少有两个连通分量，即图中有至少两个不同的部分可以从一部分通过路径到达另一部分。
三、哈密顿图与欧拉图的应用哈密顿图和欧拉图在实际生活中有广泛的应用，下面将分别介绍它们的应用领域。
1. 哈密顿图的应用：哈密顿图在旅行商问题中有着重要的应用。
旅行商问题是指一个旅行商要依次拜访若干个城市，然后返回起始城市，而要求找到一条最短的路径使得每个城市都被访问一次。
哈密顿图可以解决这个问题，通过寻找一条哈密顿路径来确定最短的路径。
2. 欧拉图的应用：欧拉图在电路设计和网络规划中发挥着重要的作用。
在电路设计中，欧拉图可以帮助我们确定如何安排电线的布线以最大程度地减少电线的长度和复杂度。
在网络规划中，欧拉图可以用于确定如何正确地连接不同的网络节点以实现高效的信息传输。
四、结论哈密顿图和欧拉图是图论中的两个重要概念。
哈密顿图是一种包含了图中所有顶点的路径的图，而欧拉图是一种可以通过图中每条边恰好一次的路径来穿越图的图。
