下载文档原格式
哈密尔顿图的充分必要条件摘要图论在现实生活中有着较为广泛的应用, 到目前为止,哈密尔顿图的非平凡充分必要条件尚不清楚,事实上,这是图论中还没解决的主要问题之一,但哈密尔顿图在实际问题中,应用又非常广泛,因此哈密尔顿图一直受到图论界以及运筹学学科研究人员的大力关注.关键词:哈密尔顿图;必要条件;充分条件;1 引言 (3)2 哈密尔顿图的背景 (3)3 哈密尔顿图的概念 (4)4 哈密顿图的定义 (5)4．1定义 (5)4．2定义 (5)4．3哈密顿路是遍历图的所有点。
(6)4 哈密尔顿图的充分条件和必要条件的讨论 (7)5 结论 (8)参考文献 (8)指导老师 (9)1 引言图论是一门既古老又年轻的学科,随着科学技术的蓬勃发展,它的应用已经渗透到自然科学以及社会科学的各个领域之中,利用它我们可以解决很多实际生活中的问题,给你一个图,你怎么知道它是否是哈密尔顿图呢?当然如果图的顶点不多,你可以用最古老的”尝试和错误”的方法试试找哈密尔顿回路就可以解决和判断.但是,数学家们并不满足这样的碰得焦头烂额后才找到的真理方法.是否存在一组必要和充分的条件,使得我们能够简单轻易地判断一个图是否是哈密尔顿图?有许多智者通过各种方式去尝试过了,遗憾的是至今尚未找到一个判别哈密尔顿回路和通路的充分必要条件.虽然有些充分非必要或必要非充分条件,但大部分还是采用尝试的办法,不过这些条件也是非常有用的.2 哈密尔顿图的背景美国图论数学家奥在1960年给出了一个图是哈密尔顿图的充分条件：对于顶点个数大于2的图，如果图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密尔顿图。
闭合的哈密顿路径称作哈密顿圈，含有图中所有顶的路径称作哈密顿路径.1857年，哈密尔顿发明了一个游戏(Icosian Game).它是由一个木制的正十二面体构成，在它的每个棱角处标有当时很有名的城市。
游戏目的是“环球旅行”。
为了容易记住被旅游过的城市，在每个棱角上放上一个钉子，再用一根线绕在那些旅游过的城市上(钉子),由此可以获得旅程的直观表示(如图1)。
哈密顿图十二面体中的哈密顿路径哈密顿图（英语：Hamiltonian path，或Traceable path）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。
在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶的路径称作哈密顿路径。
美国图论数学家奥勒在1960年给出了一个图是哈密尔顿图的充分条件：对于顶点个数大于2的图，如果图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密尔顿图。
哈密尔顿回路问题与欧拉回路类似。
它是1859年哈密尔顿首先提出的一个关于12面体的数学游戏：能否在图10.4.9中找到一个回路，使它含有图中所有结点一次且仅一次？若把每个结点看成一座城市，连接两个结点的边看成是交通线，那么这个问题就变成能否找到一条旅行路线，使得沿着该旅行路线经过每座城市恰好一次，再回到原来的出发地呢？为此，这个问题也被称作周游世界问题（10.4.9）对图10.4.9 ，图中粗线给出了这样的回路。
定义10.4.3 给定图G，若有一条路通过G中每个结点恰好一次，则这样的路称为哈密尔顿路；若有一个圈，通过G个每个结点恰好一次，这样的圈称为哈密尔顿回路（或哈密尔顿圈）。
具有哈密尔顿回路的图称为哈密尔顿图。
尽管哈密尔顿回路与欧拉回路问题在形式上极为相似，但是到目前为止还不知道一个图为哈密尔顿图的充要条件，寻找该充要条件仍是图论中尚未解决的主要问题之一。
下面先给出一个简单而有用的必要条件。
定理10.4.4 设图G＝〈V ,E〉是哈密尔顿图，则对于V的每个非空子集S，均有W（G－S）≤|S| 成立，其中W（G－S）是图G－S的连通分支数。
证明: 设α是G的哈密尔顿回路，S是V的任一非空子集。
在G－S中，α最多被分为|S|段，所以W（G－S）≤|S|利用本定理可判别某些图不为哈密尔顿图。
如在图10.4.10中，若取S＝｛v1，v4｝，则G－S有3 个连通分支，故该图不是哈密尔顿图。
摘要Hamilton回路判断的充分必要条件是至今尚未解决的一个难题，本文探讨了一些Hamilton图的充分条件，必要条件，并根据Hamilton图的相关性质给出了若干种判定Hamilton图的方法，同时，也给出了判定方法相应的实例。
关键词Hamilton图；充要条件；判定方法；回路；简图AbstractThe sufficient and necessary condition for judging Hamiltonian graph has been an unsettled problem for a long time. This paper mainly concerns some sufficient condition and some necessary conditions, and gives some methods for judging Hamiltonian graph based on the properties of Hamiltonian graph. Meanwhile , some examples are given.Key wordsHamiltonian graph; the sufficient and necessary condition; methods of judgement ; cycle；simple graph目录1．引言 (1)2．Hamilton图的相关概念 (2)3．Hamilton图的性质 (3)4．Hamilton图的若干判定方法 (5)5．相关的应用实例 (7)5.1 典型例子 (7)5.2 简单实例 (8)5.3 判断Hamilton图－1 (8)5.4 判断Hamilton图－2 (8)5.5 Petersen图是非Hamilton图的一个证明 (11)参考文献 (13)谢辞 (14)Hamilton图的若干判定条件Judgement of Hamiltonian Graph１.引言1859年，英国数学家哈密顿（Hamilton）爵士提出了下列周游世界的游戏：在正十二面体的二十个顶点上依次标记伦敦，巴黎，莫斯科，华盛顿，北京，东京等世界著名大城市;正十二面体的棱（边）表示连接这些城市的路线，问：能否在图中做一次旅行，从顶点到顶点，沿着边行走，经过每个城市恰好一次之后再回到出发点？这个问题被称为Hamilton问题。
必要条件充分条件其它方法应用特殊图哈密顿图周游世界问题1859年英国数学家威廉·哈密顿爵士发明了一个小玩具，这个小玩具是一个木刻的正十二面体，每面系正五角形，共有20个顶点，每个顶点标有世界上一个重要城市。
他提出一个问题：要求沿正十二面体的边寻找一条路通过20个城市，而每个城市只通过一次，最后返回原地。
哈密顿将此问题称为周游世界问题。
Definition设G是一个无向或有向图，若存在一条通路(回路)，经过图中每个结点一次且仅一次，则称此通路(回路)为该图的一条哈密顿通路(回路)。
具有哈密顿回路的图称为哈密顿图(Hamiltonian graph)。
注意规定：平凡图为哈密顿图；哈密顿通路是经过图中所有结点的通路中长度最短的通路；哈密顿回路是经过图中所有结点的回路中长度最短的回路。
Examplev1v2v3v4(a)哈密顿图(哈密顿回路)v1v2v3v4v5(b)存在哈密顿通路v1v2v3v4v5v6v7(c)无哈密顿通路v1v2v3v4(d)哈密顿图(哈密顿回路)v1v2v3v4(e)v1v2v3v4(f)引子定义必要条件充分条件其它方法应用哈密顿图的必要条件Theorem设无向图G=<V,E>是哈密顿图，V1是V的任意非空子集，则p(G−V1)⩽|V1|，其中p(G−V1)是从G中删除V1后所得到图的连通分支数。
Proof.设C是G中的一条哈密顿回路，V1是V的任意非空子集。
下面分两种情况讨论：（1）V1中结点在C中均相邻，删除C上V1中各结点及关联的边后，C−V1仍是连通的，但已非回路，因此p(C−V1)=1⩽|V1|。
（2）V1中结点在C上存在r(2⩽r⩽|V1|)个互不相邻，删除C上V1中各结点及关联的边后，将C分为互不相连的r段，即p(C−V1)=r⩽|V1|。
一般情况下，V1中的结点在C中即有相邻的，又有不相邻的，因此总有p(C−V1)⩽|V1|。
2算法的依据定理1图中任何不同的H回路至少有两个不同的边。
证明令H1是图G的一个H回路。
任取一个边(vi,vj),删去后,再加上任何其它一个边,必然使vi或vj的度数1。
此时,该回路不是H回路。
故,任何不同的H回路至少有两条不同的边。
定理2令Kn中所有哈密顿回路为HCn=(e1,e2,…,ek),回路数为k,Kn的结点为v1,v2,v3,…,vn,每个et(t=1,2,…,n)有n 条边。
某个ej与vn+1结点生成的H回路为:HCn+1(ej)=∑i,jej {(vn+1,vi),(vn+1,vj),(vi,vj)}={ej1,vj2,…,ejn}共n个,其中,i ≠j,i,j<=n,vi与vj相连。
则HCn+1(ej)是Kn+1的对应ej的H回路,共n个,所有的回路是不同的。
且,所有的HCn+1(e1,…,ek)的H回路也是不同的,故,HCn+1中的所有H回路为k n。
3证明1)由定理知,HC (e) ∑e {(v ,v),(v ,v),1 n+1 j = i,jj n+1 i n+1 j(vi,vj)}是Kn+1的一组对应ejH回路,共n个;ej是一个Kn的H回路,断其边(vi,vj),加入两个边(vn+1,vi),vn+1,vj),去掉(vi,vj),再加上ej的其余的边,得一个n+1个结点的回路,令为H1,边数为n+1,且每个结点的度数为2,则H1是图1Kn+1的哈密顿回路。
如图1所示(v1,v2,v3,v4)是K4的一个H回路,再加入一个点V5,删去边(v2,v3)加入边(v5,v2)和(v5,v3),组成{v5,v2,v1,v4,v3,v5}则是K5的一个回路。
2)HCn+1(ej)中的所有H回路是不同的。
因为由ej有n条边,HCn+1(ej)=i,jej{(vn+1,vi),(vn+1,vj),(vi,vj)}是断其每一条边生成的H回路,共有n个回路,每个回路都有在另一个H回路中被删去的边,故HCn+1(ej)中的所有H回路是不同的。
哈密尔顿图的充分必要条件摘要图论在现实生活中有着较为广泛的应用, 到目前为止,哈密尔顿图的非平凡充分必要条件尚不清楚,事实上,这是图论中还没解决的主要问题之一,但哈密尔顿图在实际问题中,应用又非常广泛,因此哈密尔顿图一直受到图论界以及运筹学学科研究人员的大力关注.关键词:哈密尔顿图;必要条件;充分条件;1 引言 (3)2 哈密尔顿图的背景 (3)3 哈密尔顿图的概念 (4)4 哈密顿图的定义 (5)4．1定义 (5)4．2定义 (5)4．3哈密顿路是遍历图的所有点。
(6)4 哈密尔顿图的充分条件和必要条件的讨论 (7)5 结论 (8)参考文献 (8)指导老师 (9)1 引言图论是一门既古老又年轻的学科,随着科学技术的蓬勃发展,它的应用已经渗透到自然科学以及社会科学的各个领域之中,利用它我们可以解决很多实际生活中的问题,给你一个图,你怎么知道它是否是哈密尔顿图呢?当然如果图的顶点不多,你可以用最古老的”尝试和错误”的方法试试找哈密尔顿回路就可以解决和判断.但是,数学家们并不满足这样的碰得焦头烂额后才找到的真理方法.是否存在一组必要和充分的条件,使得我们能够简单轻易地判断一个图是否是哈密尔顿图?有许多智者通过各种方式去尝试过了,遗憾的是至今尚未找到一个判别哈密尔顿回路和通路的充分必要条件.虽然有些充分非必要或必要非充分条件,但大部分还是采用尝试的办法,不过这些条件也是非常有用的.2 哈密尔顿图的背景美国图论数学家奥在1960年给出了一个图是哈密尔顿图的充分条件：对于顶点个数大于2的图，如果图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密尔顿图。
闭合的哈密顿路径称作哈密顿圈，含有图中所有顶的路径称作哈密顿路径.1857年，哈密尔顿发明了一个游戏(Icosian Game).它是由一个木制的正十二面体构成，在它的每个棱角处标有当时很有名的城市。
游戏目的是“环球旅行”。
为了容易记住被旅游过的城市，在每个棱角上放上一个钉子，再用一根线绕在那些旅游过的城市上(钉子),由此可以获得旅程的直观表示(如图1)。
Hamilton图的若⼲判定条件摘要Hamilton回路判断的充分必要条件是⾄今尚未解决的⼀个难题，本⽂探讨了⼀些Hamilton图的充分条件，必要条件，并根据Hamilton图的相关性质给出了若⼲种判定Hamilton图的⽅法，同时，也给出了判定⽅法相应的实例。
关键词Hamilton图；充要条件；判定⽅法；回路；简图AbstractThe sufficient and necessary condition for judging Hamiltonian graph has been an unsettled problem for a long time. This paper mainly concerns some sufficient condition and some necessary conditions, and gives some methods for judging Hamiltonian graph based on the properties of Hamiltonian graph. Meanwhile , some examples are given.Key wordsHamiltonian graph; the sufficient and necessary condition; methods of judgement ; cycle；simple graph⽬录1．引⾔ (1)2．Hamilton图的相关概念 (2)3．Hamilton图的性质 (3)4．Hamilton图的若⼲判定⽅法 (5)5．相关的应⽤实例 (7)5.1 典型例⼦ (7)5.2 简单实例 (8)5.3 判断Hamilton图－1 (8)5.4 判断Hamilton图－2 (8)5.5 Petersen图是⾮Hamilton图的⼀个证明 (11)参考⽂献 (13)谢辞 (14)Hamilton图的若⼲判定条件Judgement of Hamiltonian Graph１.引⾔1859年，英国数学家哈密顿（Hamilton）爵⼠提出了下列周游世界的游戏：在正⼗⼆⾯体的⼆⼗个顶点上依次标记伦敦，巴黎，莫斯科，华盛顿，北京，东京等世界著名⼤城市;正⼗⼆⾯体的棱（边）表⽰连接这些城市的路线，问：能否在图中做⼀次旅⾏，从顶点到顶点，沿着边⾏⾛，经过每个城市恰好⼀次之后再回到出发点？这个问题被称为Hamilton问题。
