1、 本科毕业论文 （ 20 届） 哈密顿图的判定与应用 所在学院 专业班级 信息与计算科学 学生姓名 学号 指导教师 职称 完成日期 年 月 I 摘 要 哈密顿图理论是图论的一个重要组成部分 , 它是从 1859 年英国数学家哈密顿爵士提出周游世界的游戏 每个面都是正五边形的正十二面体的 顶点都通过一遍而回到起点的数学游戏中体现出来的 , 并且在此产生的 . 后人为了纪念这位数学家 , 将经过图中每个顶点一次且仅一次的回路称为哈密顿回路 . 由于运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题 , 从而引起广泛的注意和研究 . 为了理论上的突破 , 加强它们在实践中的应用 , 本文通
2、过阐述哈密顿图的定义和性质 , 以及哈密顿图判定的条件来向读者揭示哈密顿图的原理及应用 . 关键词 : 哈密顿图 ; 判定 ; 应用 ; 座位安排 II Abstract Hamiltonian graph theory is an important part of graph theory, in 1859, it is proposed by Sir Hamilton who was a British mathematician, he designed a game named around the world: how to pass over every vertices of
3、the dodecahedron which each face was a regular pentagon, then back to the starting point of the dodecahedron. To commemorate the Hamiltonian, the figure which has a circuit to go through each vertex once and only once is called Hamiltonian circuit. Because computer coding theory in science and a lot
4、 of problems can be reduced to Hamiltonian problems, it attracted wide attention and research. To theoretical breakthrough, and to strengthen it application in practice, the thesis discusses the theory and application of Hamiltonian through describes the definition, nature and determined conditions
5、of the Hamiltonian. Keywords: Hamiltonian graph; Determination; Applications; Seating arrangementsIII 目 录 摘 要 .I Abstract . II 1 前言 . 1 2 哈密顿图的定义与性质 . 6 2.1 哈密顿图的定义 . 6 2.2 哈密顿图的性质 . 7 3 哈密顿图的判定 . 10 3.1 哈密顿图判定的必要条件 . 10 3.2 哈密顿图判定的充分条件 . 11 4 哈密顿图的应用 . 14 4.1 座位安排问题 . 14 4.2 旅行售货员问题 . 14 5 小结 . 16
6、参考文献 . 17 致谢 .错误 !未定义书签。 1 1 前言 图论 (graphic theory)是一门既古老又年轻的学科 . 它诞生于 18世纪上半叶 . 到 19世纪下半叶这个领域才发展成为数学的一个系统的分支 , 直到 20 世纪上半叶 , 这门学科才有自己的著作出现 . 自 20世纪下半叶开始 , 随着计算机科学与技术的发展 , 图的理论研究和应用研究才得到迅速广泛的重视 , 图论作为一个数学的分支 , 才真正确立了自己的地位 . 哈密顿 (爱尔兰科学家 )在 1859 年提出一个名叫 “周游世界 ”游戏问题是 : 能否遍历正 12面体的每个顶点一次且一次后回到原地 . 由此引申出
7、哈密顿图的定义 : 如果图 G 上有一条经过图 G 所用顶点一次且仅一次的回路 , 则称此回路为哈密顿回路 , 具有哈密顿回路的图称为哈密顿图 . 哈密顿图具有六个领域 : 哈密顿圈 , H 连通 , 泛圈 , 点泛圈 , 边泛圈 , 泛连通 . 哈密顿图是有哈密顿圈的图 . 至今没有一个像欧拉图的充要条件那样的 “非平凡的 ”(不是定义的同义反复 )关于哈密顿图、哈密顿通路的充分必要条件 , 但关于他们的充分性和必要性分别有一些研究成果 . 而哈密顿图不光在金字塔图、扇面蜂巢图及马图上有 体现它性质的研究 , 且在四正则连环图和彼得森中有它独特的应用 . 而且哈密顿图在哈密顿通路、哈密顿轨、
8、多哈密顿轨问题上也有很多细致的研究和应用 . 1984 年在连续 10 年 排名加拿大第一的大学的范更华教授得到 名垂青史 的“范定理 ”: 2 连 通 n 阶图 G 的距离是 2 的任意两点 ,xy均有 m a x ( ), ( ) / 2d x d y c, 则 G 是有 c 圈 , 当 cn 时是哈密顿图 . 当然 , 关于如 此著名的范定理 , 各国不少专家也对范定理企求做出改进发展 . 1987 年 Wojda 院士和欧洲最古老的著名大学之一的法国奥大的运筹学科创建奠基人 Benhocine教授 2人合作仅局部推广上面范定理 . 又如法国 Benhocine教授 1977年发表在法国
9、科学院学报的哈密顿图论文就一直有国际影响 , 但他至今仅有 25篇数学论文且 18篇是哈密顿图的 , 他是排名哈密顿图研究前 30 名大师之一 . 哈密顿图已经历了一个多世纪的跋涉 , 容易攀登的时代已经过去了 , 其进展已非常不容易 , 如此即使是世界级的大师泰斗 , 不论你多么聪明利害都好 , 面对的下一个问题猜想都永远是相关学科的全世界的专家经过多年仍不能解决的 , 就是想做点进展都非常不容易 , 每一篇论文都是超越最权威大师的成果 . 哈密顿图的难如两个权威说 “非常不容易 ”. 但它却具有重大历史意义以及广泛而重要的2 应用价值 . 现国际数学联盟主席是哈密顿图权威 , 并且 琼州大
10、学赵克文和美国权威等合作改进耶鲁大学 Ore 院士等大师权威的代表性结果在 “哈密顿图 ”领域已 居世界领先 . 在国内 , 宁宣熙和宁安琪提出了哈密顿圈自组织算法的实证研究结果和其在哈密顿图判定上的应用 , 介绍了 SOA 算法在大约 12000 个规模不同 ( 1 0 4 0 0 0 , 2 0 8 0 0 0nm )的一般任意图中构造哈密顿圈的实证研究结果 , 验证了 SOA 算法的可靠性和时间的多项式性 . 在此基础上论证了 SOA 算法用于判断一般任意图是否为哈密顿图的可行性 , 并用一些实例进行了实证研究 . 在阻塞流理论的研究中 , 利用网络最小阻塞流与哈密顿轨之间的关系建立了
11、哈密顿轨问题的无环最小支撑流模型 . 通过这个模型可以把一步内构造无环最小支撑流这一数学难题分解成分别在多项式时间内完成的两个阶段 , 从而为解决这一数学难题找到了新的思路 , 开发研制了在一般任意图中构造哈密顿圈的自组织算法 (或 SOA算法 ). 在文献 14 , 全面详细地介绍了作者经过 10 多年潜心研究这一算法的理论及进行 12000 余例实证研究的结果 . 到目前为止尚未遇到反例 . 由于不少学者根据 NPC 理论认定这是绝对不可能的 , 因此作者只好通过大量的实证研究来显示这一 多项式算法存在的可能性 . 况且 , 作者进行这项研究的目的并不是为了解决计算复杂性理论中 NP 是否
12、等于 P 的问题 , 而是为学术研究和工程应用提供一种在一般图中构造哈密顿圈的实用有效工具 . 即便有人能找到反例 , 说明 SOA算法只不过是像线性规划单纯形算法那样 , 是一个实用的好算法 , 应当说这也是一个很幸运的结果 . 因为有了它 , 不但可以在用相关定理 (如范定理或者其它更新的定理 )判定存在哈密顿圈的一般图中构造出至少一条具体的哈密顿圈 , 也可以对超出这些定理范围之外的一般图进行是否是哈密顿图的判定 , 这岂不也是一项有实 用价值的成果 . 如果这些研究结果还能对数学家们在解决哈密顿图判定的理论研究上有所启迪和帮助 , 那么这项研究就更有意义了 . 回溯法是一种按照深度优先
13、的策略从根结点开始搜索解空间树的算法 , 该算法可以用来求出问题的全部解 , 也可以在求出问题的一个解之后停止对问题的求解 , 即只求该问题是否有解 5 . 哈密顿通路就是判断图中是否存在一条通过所有顶点一次且仅一次的路径 . 宁夏大学数学计算机学院 的 刘向娇 博士在他的 用回溯法求哈密顿通路 论文中论述了 用回溯法来求解一个任 意的图中是否存在一条哈密顿通路的问题 , 并用具体的算法来3 实现它 . 算法搜索至解空间树的任一结点时 , 总是先判断该结点是否肯定不包含问题的解 . 如果肯定不包含 , 则跳过对以该结点为根的子树的系统搜索 , 逐层向其祖先结点回溯 . 否则 , 进入该子树 ,
14、 继续按深度优先的策略进行搜索 . 回溯法在用来求问题的所有解时 , 要回溯到根 , 且根结点的所有子树都已被搜索遍才结束 6 . 而回溯法在用来求问题的任一解时 , 只要搜索到问题的一个解就可以结束 . 这种以深度优先的方式系统 地搜索问题的解的算法称为回溯法 , 它适用于解一些组合数较大的问题 . 在求解一些问题 (如走迷宫、地图着色等问题 )时 , 题目的要求可能是求出原问题的一种或所有可能的解决方案 . 这类问题的解往往是由一个一个的步骤或状态所构成的 , 每一步骤又有若干种可能的决策方案 ; 由于没有固定、明确的数学解析方法 , 往往要采用搜索的做法 , 即从某一个初始状态出发 ,
15、不断地向前 (即下一个状态 )搜索 , 以期最终达到目标状态 , 从而得到原问题的一个解或所有的解 . 在搜索的过程中 , 由于问题本身及所采取的搜索方法的特点 (如在缺乏全局及 足够的前瞻信息的情况下进行搜索等 ) 7 , 会导致走到某一状态就走不下去的情况 , 这时 , 就必须回头 (即回到上一步 , 而不是回到最初的状态 ), 再尝试其他的可能性 , 换一个方向或方法再试试 . 这样 , 不断地向前探索、回溯 , 再向前、再回溯 , 直至最终得出问题的解 , 或者一路回溯到出发点 (出现这种情况即表示原问题无解 ) 8 . 注意 , 这种搜索过程并不是尝试搜索问题解空间中所有的可能状态和
16、路径 , 而是采用深度优先的 方式 , 沿着一条路径 , 尽可能深入地向前探索 . 用回溯法解哈密顿通路问题首先要画出问题的解空间树 , 该解空间树是一棵最大度是n 的树 (其中 n 为图中的顶点数 ), 树中只有第一个结点的度是 n , 其余结点的度都为1n (该结点不用与其自身相连 ). 在编写算法时可以通过判断该边在图的邻接矩阵中的值来剪枝 , 如果其值 不是 1 则说明该边不存在则剪枝不用搜索 . 由于在求图的哈密顿通路时走过的顶点不能再重复走 , 所以要对已经遍历过的顶点做一个标记 , 如果在搜索时找到的是一个带有标记的顶点 , 那么该路径也是不可行的 , 应剪去 . 宁安琪、宁宣熙
17、 9 在她们的另外一篇关于金字塔图的哈密顿图性质研究的论文中阐述了她们仿照埃及金字塔的形状 , 设计了一类金字塔图 , 它包括平面金字塔图和立体多面金字塔图 , 并用一般图中构造哈密顿轨 (圈 )的自组织算法 ( SO 算法 )研究了它们的哈密顿图性质 . 同时 , 也验证了 SO 算法的有效性 . 在一般图中构造哈密顿轨 (圈 )的算法研究中 , 设计各种不同的哈密顿图去进行算法的可行性及计算复杂性的研究是十分重要的环节 . 为此 , 4 她们已经设计过塔形图 , 套装图 , 四正则围城迷宫图 , 连环图等 , 它们都在验证一般图中构造哈密顿轨 (圈 )的自组织算法的有效性起了重要作用 .
18、她们仿照埃及金字塔的形状 , 设计了一类金字塔图 , 它包括平面金字塔图和立体多面金字塔图 , 并用 SO 算法研究了它们的哈密顿图性质 . 田媛和刘铎 10 在他们的金字塔图存在哈密顿回路的构造性证明论文首先给出了平面金字塔图中哈密顿回路的一个构造方法 ; 而后以此为基础 , 给出了立体多面金字塔图中哈密顿回路的构造方法 . 从而构造性地部分证明了宁安琪等学者提出的金字塔图都是哈密顿图的猜想 . 本文通过分析哈密顿图的性质 , 论述了哈密顿图的定义及若干判定方法和哈密顿图在实际生产生活中的应用 . 并对几个实际问题进行了具体的分析 , 从而进一步加深对哈密顿图的理解及应用 . 5 6 2 哈
19、密顿图的定义与性质 2.1 哈密顿图的定义 定义 2.111 图 (graph)G 由两个部分组成 (1)非空集合 V , 称为图 G 的顶点集 . (2)多重集合 E , 称为图 G 的边集 . 定义 2.2 图 G 的顶点 1v 到顶点 lv 的拟路径是指如下的序列 1 1 2 2 3 1 1, , , , , , , ,l l lv e v e v v e v. 其中 ( 1,2, , )iv i l 是 G 的顶点 , 1, 2, , 1je j l是 G 的边 . 当 1, 2, , 1je j l各不相同时 , 该拟路径称为路径 . 又当 1, 2, ,iv i l 各不相同时 (
20、除1v 和 lv 外 ), 则称此路径为通路 . 1 lvv 的路径称为闭路径 , 1 lvv 的通路称为回路 . 定义 2.3 哈密顿通路 : 经过图中所有顶点一次且仅一次的 通路 . 定义 2.4 哈密顿回路 : 经过图中所有顶点一次且仅一次的 回路 . 定义 2.5 哈密顿图 : 具有哈密顿回路的图 . 定义 2.6 半哈密顿图 : 具有哈密顿通路而无哈密顿回路的图 . 图 2.1 博物馆展室的示意图 图 2.1 给出了一个现代艺术博物馆的示意图 , 该博物馆被分成 15 个展室 . 在每天下班之前 , 一个安保人员从前门进入接待室 , 然后检查每一间展室看一切是否状况良好 . 如果工作人员能够浏览每个房间一次 , 然后返回到接待室 , 这将会是最有效 率的走法 . 这种走法可以实现吗 ?
