哈密尔顿图的充分必要条件

哈密尔顿图的充分必要条件摘要图论在现实生活中有着较为广泛的应用, 到目前为止,哈密尔顿图的非平凡充分必要条件尚不清楚,事实上,这是图论中还没解决的主要问题之一,但哈密尔顿图在实际问题中,应用又非常广泛,因此哈密尔顿图一直受到图论界以及运筹学学科研究人员的大力关注.关键词:哈密尔顿图;必要条件;充分条件;1 引言42 哈密尔顿图的背景43 哈密尔顿图的概念54 哈密顿图的定义641定义642定义643哈密顿路是遍历图的所有点。74 哈密尔顿图的充分条件和必要条件的讨论85 结论9参考文献9指导老师101 引言图论是一门既古老又年轻的学科,随着科学技术的蓬勃发展,它的应用已经渗透到自然科学以及社会科学的各个领域之中,利用它我们可以解决很多实际生活中的问题,给你一个图,你怎么知道它是否是哈密尔顿图呢?当然如果图的顶点不多,你可以用最古老的”尝试和错误”的方法试试找哈密尔顿回路就可以解决和判断.但是,数学家们并不满足这样的碰得焦头烂额后才找到的真理方法.是否存在一组必要和充分的条件,使得我们能够简单轻易地判断一个图是否是哈密尔顿图?有许多智者通过各种方式去尝试过了,遗憾的是至今尚未找到一个判别哈密尔顿回路和通路的充分必要条件.虽然有些充分非必要或必要非充分条件,但大部分还是采用尝试的办法,不过这些条件也是非常有用的.2 哈密尔顿图的背景美国图论数学家奥在1960年给出了一个图是哈密尔顿图的充分条件：对于顶点个数大于2的图，如果图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密尔顿图。闭合的哈密顿路径称作哈密顿圈，含有图中所有顶的路径称作哈密顿路径.1857年， 哈密尔顿发明了一个游戏(Icosian Game).它是由一个木制的正十二面体构成，在它的每个棱角处标有当时很有名的城市。游戏目的是“环球旅行”。为了容易记住被旅游过的城市 ，在每个棱角上放上一个钉子，再用一根线绕在那些旅游过的城市上(钉子),由此可以获得旅程的直观表示(如图1)。图1 哈密尔顿(1805-1865),爱尔兰数学家。个人生活很不幸，但兴趣广泛：诗歌、光学、天文学和数学无所不能。他的主要贡献是在代数领域，发现了四元数(第一个非交换代数)，他认为数学是最美丽的花朵。 哈密尔顿把该游戏以25英镑的价格买给了J.Jacques and Sons公司 (该公司如今以制造国际象棋设备而著名) ，1859年获得专利权。但商业运作失败了.该游戏促使人们思考点线连接的图的结构特征。这就是图论历史上著名的哈密尔顿问题。3 哈密尔顿图的概念含有图中所有顶点的轨称作哈密尔顿轨，闭合的哈密尔顿轨称作哈密尔顿环，含有哈密尔顿环的图称作哈密尔顿图。著名的美国图论数学家奥勒在1960年给出了一个图是哈密尔顿图的充分条件：对于顶点个数大于2的图，如果图中任意两点度的和大于顶点总数，那这个图一定是哈密尔顿图。哈密尔顿轨也称作哈密尔顿链，指在一个图中沿边访问每个顶点恰好一次的路径。寻找这样的一个路径是一个典型的NP-完备(NP-complete)问题。包含图中每个顶点的路称为哈密尔顿路;通过图中每个顶点一次且仅一次的通路称为哈密尔顿通路;通过图中每个顶点一次的回路称为哈密尔顿回路;一个图若含有哈密尔顿回路,则称这个图是哈密尔顿图(如图2).图2 一个图的哈密尔顿回路与欧拉回路是很相似的,但差别在于哈密尔顿回路是环游图中的所有顶点,而欧拉回路是环游图中所有的边.对于一个图是否存在欧拉环游,存在一个非常简单的判别法.那么判别一个图是否存在哈密尔顿回路是否也存在这样一个非常简洁的判别法吗?遗憾的是直到目前为止,还没找到哈密尔顿图的充分必要条件,事实上,寻找哈密尔顿图的充分必要条件几乎是无望的.但是人们希望找到哈密尔顿图的简明有效的充分条件,这就是图论中的一个著名问题:哈密尔顿图的问题.”棋盘的骑士问题”实际上就是要判断它所对应的图是否是哈密尔顿图的问题.4 哈密顿图的定义41定义 设G=(P,L)是有向图，（ v1, vn）是G中一条路，如果G中没每点在此路中出现一次，则称此路为哈密顿路。如果G中每点除v1外，恰在此中出现一次，且v1 vn，则此路称为哈密顿回路。42定义 设G=(P,L)是有向图，如果G中有一条哈密顿回路，则称G为哈顿顿图。例1 下面的图为哈密顿图。HGFEDCBAG2在图中，路（ABCDHGFE）是哈密顿路。路（ABCDHGFEA）是哈密顿回路。43哈密顿路是遍历图的所有点。 对于哈密顿路与哈密顿回路，下面的一些性质是显然的。 哈密顿路是简单路。设G有n个点，这G的哈密顿路有n-1条边，G的哈密顿回路有n条边。 若G中某点度是0，这G既无哈密顿路，也无哈密顿回路。若G中某点的度是1，这G无哈密顿回路。 设v是G中的一个点， dG(v)=2若G有哈密顿回路，则以v为端点的两边必须都出现在哈密顿回路中。 哈密顿回路要求遍历诸点，如果图中某些必须在哈密顿回路中出现的边已经构成回路，而图中尚有不在该回路中出现的点，这该图一定没有哈密顿回路。 设v是图G的一个点，dG(v) 2，G有哈密顿回路，则哈密顿回路仅使用以v为端点的两条边4 哈密尔顿图的充分条件和必要条件的讨论对于哈密尔顿图条件的条件的讨论,我们先给出一个简单而有用的必要条件(7):定理1:设无向图G=(V,E)是哈密尔顿图, V1是V的任意的非空子集,则:P(G-V1)|V1|.其中,P(G-V1)为从G中删除V1(删除V1中各顶点及关联的边)后所得图的连通分支数.证明:设C为G中的一条哈密尔顿回路.(1) 若V1中的顶点在C上彼此相邻,则P(C-V1)=1|V1|(2) 设V1中的顶点在C上存在r(2r|V1|)个互不相邻,则 P(C-V1)=r|V1|一般说来,V1中的顶点在C上既有相邻的,又有不相邻的,因而总有 P(C-V1)|V1| 又因为C是G的生成子图,故P(G-V1)P(C-V1)|V1| 图3上图3中,虽然对任意的结点集合V1,都满足P(G-V1)|V1|,但它仍然不是哈密尔顿图.由此可见,定理1有时可以用来证明某一特定的图是非哈密尔顿图,可是,这个方法并不总是有效的.一般来说，V1中的顶点在C上既有相邻的，又有不相邻的，因而总有 又因为C是G的生成图，故 现在我们讨论哈密顿图的充分条件，当且仅当它的基础简单图是哈密尔顿图，所以我们只考虑简单图。最早的结果是英A 狄拉克在1952年给出一个充分条件使得一个图是哈密尔顿图。它的定理是只要检查每一顶点X，看它的上面有多少个弧通过，把这个数目D（X）来表示，只要每一个点D（X）是相当大的话，这个图就会是哈密顿尔图。5 结论定理1： 设无向图G=是哈密顿图，V1是V的任意的非空子集， p(G-V1)=3)阶无向简单图，如果G中任何一对不相邻的顶点度数之和都大于等于n,则G是哈密顿图。 推论： 设G是n(n=3)阶无向简单图，如果G中任何一对不相邻的顶点的度数之和都大于等于n，则G是哈密顿图。 定理3： 在n(n=2)阶有向图D=中，如果所有有向边均用无向边代替，所得无向图中含生成子图Kn，则有向图中存在哈密顿图。 推论： n(n=3)阶有向完全图为哈密顿图参考文献1J。A邦迪，默蒂等