哈密尔顿图的判定及在.docVIP

哈密尔顿图的判定及在“旅行货郎问题”上的应用 摘要： 伴随着数学和计算机科学的发展，图论的应用已经渗透到了各个领域；利用图的直观性和漂亮的表现特性可以使人们对现实的系统有更清晰的了解. 在现实的世界当中许多问题的数学抽象形式都可以用图来描述，例如互联网、通讯网、交通网、分子结构、集成电路等.图论已经成为了人们研究自然科学和社会科学的重要工具，其中哈密尔顿图在其相关的领域的应用已经越来越广泛.大部分的图论书上都给出了哈密尔顿图的判别方法和相关的应用， 本文在查阅大量相关的资料的基础上总结和概括哈密尔顿图的起源、判别方法及相关的应用. 关键词： 数学；图论；哈密尔顿图；判别方法；应用 1 哈密尔顿图的起源 哈密尔顿（Hamilton）是一位出生在爱尔兰的天文学家和数学家. 他的一生是很丰富多彩的，自从他发现“四元数”后，他又发现了另一种称之为“Thee Icosiane Calculus”的代数系统，这个系统包含有乘法和加法的运算算子，但是乘法并不满足交换律. 他发现的这个代数系统是和正则12 面体有关的. 于是在1859 年他提出了所谓的“周游世界游戏”：将一个正十二面体当中的20 个顶点分别表示全世界的20 个城市（如图1-1），一个人要从其中的某一个城市出发， 经过每一个城市刚好一次，然后再回到出发点， 问这样的旅行路线是否真的存在？ 这个游戏曾经风靡一时.可以应用拓扑的思想，将这正十二面体“拉平”将会得到一个和它同构的平面图（如图1-2），这样进行就可以将这个游戏转化为：要求必须沿着正十二面体的棱，怎样才能走完正则十二面体上的所有顶点，而且最后又回到起点的问题. 从此以后，由于这游戏的缘故，人们就把这一类图称为哈密尔顿图. 2 哈密尔顿图的相关概念 设G 是一个图， 包含图G 中的每个顶点的路就称为哈密尔顿路.通过图G 中每个顶点有且仅有一次的通路就称为哈密尔顿通路.通过图G 中的每个顶点有且仅有一次的回路就称为哈尔顿回路.一个图假如含有哈密尔顿回路，则这个图就是哈密尔顿图. 定理1 若图G=V,E具有汉密尔顿回路，则对于结点集V的每个非空子集S均有 W(G-S)≤|S|成立。其中W(G-S)是G-S中连通分支数。 　　定理2 设G具有n个结点的简单图，如果G中每一对结点度数之和大于等于n-1，则在G中存在一条汉密尔顿路。 　　定理3 设G是具有n个结点的简单图。如果G中每一对结点度数之和大于等于n,则在G中存在一条汉密尔顿回路。 　　定义2 给定图G=V,E有n个结点，若将图G中度数之和至少是n的非邻接结点连接起来得图G’，对图G’重复上述步骤，直到不再有这样的结点对存在为止，所得到的图，称为是原图G的闭包，记作C(G)。 　　定理4 当且仅当一个简单图的闭包是汉密尔顿图时，这个简单图是汉密尔顿图。3 哈密尔顿图的判定 任意给定一个图，怎样才能知道它是不是哈密尔顿图呢？ 当然如果这个图的顶点不多，你可以直接用最为古老的“尝试和错误”的蛮力方法找出哈密尔顿回路就可以判断了.但是数学家们并不满意这种碰得焦头烂额后才能找到真理的办法.那么是否存在一个充分必要条件，能使我们简单地判断任意给的图是否为哈密尔顿图呢？很多科学家做过大量研究，但遗憾的是到目前为止还没能得到一个判别哈密尔顿图的充要条件，这也是图论的一大难题.虽然存在一些充分不必要，或者必要不充分的条件，但是在大部分的情况下，还是采用最古老的尝试的办法，不过这些判别方法在某些场合也是十分有用的. 下面将介绍几个判别哈密尔顿图的方法：因为对任意一个图来说如果它是哈密尔顿图，当且仅当它的基础简单图是哈密尔顿图，所以我们只要考虑简单图. 我们首先给出判别哈密尔顿图的四个充分条件：最早的提出哈密尔顿图的充分条件的是英国的狄拉克.他的定理只要求检查图上的每个顶点x看每个顶点x 上有多少个弧通过，将通过顶点x 的弧个条数记为D(x),当图中的每个顶点的D(x)相当大时，这个图就是哈密尔顿图. . . 定理1(狄拉克定理). 任意给定一个图，如果这个图的顶点数n≥3，而且D(x)≥n/2,那么这个图一定是哈密尔顿图. . . 根据狄拉克定理我们可以判断下面的两个图G1 和G2（图2-1）都是哈密尔顿图. . . 因为在图G1 当中，每一个顶点x 都有D(x)=3，而n=4，显然D(x)=3≥4/2=2.而在图G2 当中，每一个顶点x 都有D(x)=4，而n=6，显然D(x)=4≥6/2=2.所以图G1 和图G2 都是哈密尔顿图. . . 在狄拉克提出上述充分条件的八年后，美国的著名图论学家奥斯坦·奥勒将狄拉克的工作进行了推广，得到了以下的十分重要的结论. . . 定理2(奥勒定理). 任意给定一个图，如果这个图的顶点数n≥3，而且对于任意的两个顶点x，