第11章-参考资料：无向哈密顿图的一个充分条件的证明

哈密尔顿图的充分必要条件摘要图论在现实生活中有着较为广泛的应用, 到目前为止,哈密尔顿图的非平凡充分必要条件尚不清楚,事实上,这是图论中还没解决的主要问题之一,但哈密尔顿图在实际问题中,应用又非常广泛,因此哈密尔顿图一直受到图论界以及运筹学学科研究人员的大力关注.关键词:哈密尔顿图;必要条件;充分条件;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)。

哈密顿回路。
.
欧拉图与哈密顿图 1.2 哈密顿图及哈密顿通路
➢ 定义8.21
图G称为可2-着色（2-chromatic），
如果可用两种颜色给G的所有顶点着色， 使每个顶点着一种颜色，而同一边的两端点 必须着不同颜色。
.
欧拉图与哈密顿图 1.2 哈密顿图及哈密顿通路
✓ 定理8.16
设图G是可2-着色的。如果G是哈密顿 图，那么着两种颜色的顶点数目相等；如 果G有哈密顿通路，那么着两种颜色的顶点 数目之差至多为一。
✓定理8.14
设图G为具有n个顶点的简单无向图，如果G的 每一对顶点的度数之和都不小于n – 1 ，那么G中有 一条哈密顿通路；如果G的每一对顶点的度数之和 不小于n，且n≥3，那么G为一哈密顿图。
.
欧拉图与哈密顿图 1.2 哈密顿图及哈密顿通路
✓ 定理8.15
当n为不小于3的奇数时，
Kn上恰有 n 1 条互相均无任何公共边的 2
离散数学导论
.
欧拉图与哈密顿图 1.1欧拉图与欧拉路径
➢ 定义8.19
图G称为欧拉图（Euler graph），
如果图G上有一条经过G的所有顶点、所有
边的闭路径。图G称为欧拉路径（Euler
walk），如果图G上有一条经过G 所有顶点、所有边的路径。
.
欧拉图与哈密顿图 1.1欧拉图与欧拉路径
✓ 定理8.11
.
欧拉图与哈密顿图 1.2 哈密顿图及哈密顿通路
➢ 定义8.20
无向图G称为哈密顿图（Hamilton graph），
如果G上有一条经过所有顶点的回路
（也称这一回路为哈密顿回路）。称无向图有哈密顿 通路(非哈密顿图)，如果G上有一条经过所有顶点的

哈密顿图十二面体中的哈密顿路径哈密顿图（英语：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|。

例4 设 G 为 n（n3）阶无向简单图， 2，证明G 中存在 长度 +1 的圈.
证明：设 = v0v1…vl 是由初始路径 0 用扩大路径法的得到 的极大路径，则 l .
因为v0 不与 外的顶点相邻，又 d(v0) ，因而在 上除 v1 外，至少还存在 1个顶点与 v0 相邻. 设 vx 是离 v0 最远的顶点，于是 v0v1…vxv0 为 G 中长度 +1 的圈.
扩大路径法
设G = <V, E>为 n 阶无向图，E . 设 l 为G中一条路径. 若此路径的始点或终点与通路外的顶点相邻，就将它们扩到 通路中，继续这一过程，直到最后得到的通路的两个端 点不与通路外的顶点相邻为止. 设最后得到的路径为l+k（长度为 l 的路径扩大成了长度为 l+k 的路径），称l+k为“极大路径”. 称使用此种方法证明问题的方法为“扩大路径法”. 有向图中类似讨论，只需注意，在每步扩大中保证有向边方 向的一致性. 1
6
广东工业大学计算机学院
证明详解2
(3) 由于G是连通的，可得比 更长的路径。 如图(2) 所示，由 l < n可知，存在vl+1V(G) - V(C)与C上某一 点vt相邻。当t < ir – 1时，删除(vt-1, vt)，得到路径 ‘= vt1…v1vir…vlvir-1…vtvl+1比 的长度大1. 对于t > ir – 1和t = ir 的情况也可以构造类似的 ‘
广东工业大学计算机学院
实例
(1) (2)
(3)
(4)
由某条路径扩大出的极大路径不惟一，极大路径不一定是 图中最长的路径
上图中，(1)中实线边所示的长为2的初始路径，(2), (3), (4) 中实线边所示的都是由(1)扩展成的极大路径.

W(C1)=10 W(C2)=11 W(C3)=9
最短
17
11.3 二部图与匹配
定义11.3 设 G=<V,E>为一个无向图, 若能将 V分成 V1和V2 (V1V2=V, V1V2=), 使得 G 中的每条边的两个端点都是一 个属于V1, 另一个属于V2, 则称 G 为二部图 ( 或称二分图, 偶 图), 称V1和V2为互补顶点子集, 常将二部图G记为<V1,V2,E>. 又若G是简单二部图, V1中每个顶点均与V2中所有的顶点相邻， 则称G为完全二部图, 记为 Kr,s, 其中r=|V1|, s=|V2|.
邻的顶点vi,vj, 均有
d(vi)+d(vj) n 则G中存在哈密顿回路.
（）
14
判断是否为哈密顿图
判断是否为(半)哈密顿图至今还是一个难题. (1) 观察出一条哈密顿回路或哈密顿通路. (2) 证明满足充分条件. (3) 证明不满足必要条件.
例4 证明右图(周游世界问题)是哈密顿图 证 abcdefghijklmnopqrsta 是一条哈密顿回路. 注意，此图不满足定理11.3推论的条件.
与已知条件矛盾. 得证V1中任意两顶点不相邻. 由对称性, V2 中也不存在相邻的顶点, 得证G为二部图．
21
最大匹配
定义11.4 设G=<V1,V2,E>为二部图, ME, 如果M中的任意两 条边都不相邻, 则称M是G的一个匹配. G中边数最多的匹配 称作最大匹配. 又设|V1||V2|, 如果M是G的一个匹配且 |M|=|V1|, 则称M是V1到V2的完备匹配. 当|V2|=|V1|时, 完备匹 配又称作完美匹配．
图论方法描述如下: 设G=<V,E,W>为一个n阶完全带权图Kn, 各边的权非负, 且可能为. 求G中的一条最短的哈密顿回路.

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问题。

A F
B
A
C
F
B C
E
D
E
D
竞赛图
底图为K4的竞赛图： A
B
C
以上每个图可以看作4个选手参加的循环赛的一种结果
竞赛图与有向哈密尔顿通路
底图是完全图的有向图称为竞赛图。 利用归纳法可以证明竞赛图含有向哈密尔顿通路。
循环赛该如何排名次
A F
E
B
按照在一条有向Hamilton通路 (一定存在)上的顺序排名：
Ore定理的证明
Ore定理（1960） 设G是无向简单图，|G|=n3，若
对G中任意不相邻的顶点u和v, d(u)+d(v)n （*）
则G有哈密尔顿回图。
证明.反证法, 若存在满足（*）的图G，但是G没有Hamilton回 路. 不妨假设G是边极大的非Hamilton图，且满足（*）。若G不是 边极大的非Hamilton图，则可以不断地向G增加若干条边,把G 变成边极大的非Hamilton图G’，G’依然满足（*），因为对 vV(G), dG(v)dG’(v)。
设G是无向简单图, |G|=n2, 若G中任意不相邻的顶点对
u,v均满足：d(u)+d(v)n-1，则G是连通图。
假设G不连通，则至少含2个连通分支，设为G1, G2。取xVG1, yVG2, 则：d(x)+d(y)(n1-1)+(n2-1)n-2 (其中ni是Gi的顶பைடு நூலகம்个数)， 矛盾。
有限图G是Hamilton图充分必要其闭合图C(G)是 Hamilton图.
闭合图(举例)
a
b
f
c e
d
判定定理的盲区
从“常识”出发个案处理

个结点正负度相等可以断定从G的任一结点 v0出发一定存在G的一条简单回路C。若 C=E(G)，则得证。否则在G中删去C的各 边，找到新的简单回路C1，并添加至C中。 重复该步骤直至C成为欧拉回路为止。
2014-11-25
IntroductionToCS--Xiaofeng Gao
12
欧拉道路(欧拉迹)
IntroductionToCS--Xiaofeng Gao
15
编码盘范例
【例】一个编码盘分成16个相等的扇面，
每个扇面分别由绝缘体和导体组成，可以 表示0和1两种状态，其中a,b,c,d四个位置的 扇面组成一组二进制输出。 试问这16个二进制数的 序列应如何排列，编码 盘才恰好能组成0000到 1111的16组四位二进制 输出，同时旋转一周后 又返回到0000状态？
【例】 判断下图是否可以一笔画成：
a
b
a
b
e
d
c G
e
d H
c
2014-11-25
IntroductionToCS--Xiaofeng Gao
21
哈密顿圈
Hamilton Circuit
2014-11-25
IntroductionToCS--Xiaofeng Gao
22
哈密顿回路与道路
【定义】无向图G的一条经过全部结点的初
【证明】易知k是偶数。在这个k个结点间
添加k/2条边，使得每个结点都与其中一条 边关联，得到G’，易知G’中各结点的度都 为偶数，故G’中有欧拉回路C，这k/2条边 都在C上且不相邻接。故删去这些边，可以 得到k/2条简单道路，它们包含了G的所有 边，即E(G)划分成了k/2条简单道路。
2014-11-25

哈密顿图十二面体中地哈密顿路径哈密顿图（英语：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 个连通分支, 故该图不是哈密尔顿图.判断哈密尔顿图地充分条件很多, 我们仅介绍其中一个.定理10.4.5 设G＝〈V ,E〉是有n个结点地简单图,1）如果任两结点u, v∈V, 均有deg(u)＋deg(v)≥n－1,则在G中存在一条哈密尔顿路；2）如果对任两结点u, v∈V, 均有deg(u)＋deg(v)≥n,则G是哈密尔顿图. 证明略.【例10.4.3】某地有５个风景点.若每个景点均有两条道路与其他景点相通,问是否可经过每个景点恰好一次而游完这５处？解将景点作为结点,道路作为边,则得到一个有５个结点地无向图.由题意,对每个结点vi,有deg(vi)＝2（i∈Ｎ5）.则对任两点vi, vj（i, j∈Ｎ5）均有deg(vi)＋deg(vj)＝2＋2＝4＝5－1 可知此图一定有一条哈密尔顿路,本题有解.我们再通过一个例子,介绍一个判别哈密尔顿路不存在地标号法.【例10.4.4】证明图10.4.11所示地图没有哈密尔顿路.证明: 任取一结点如v1,用A标记,所有与它相邻地结点标B.继续不断地用A标记所有邻接于B 地结点,用B标记所有邻接于A地结点,直到图中所有结点全部标记完毕.如果图中有一条哈密尔顿路,则必交替通过结点A和B.因此或者结点A和B数目一样,或者两者相差１个.（10.4.11）而本题有３个结点标记A,５个结点标记B,它们相差２个,所以该图不存在哈密尔顿路.作为哈密尔顿回路地自然推广是著名地货郎担问题.问题是这样叙述地：设有一个货郎,从他所在地城镇出发去n－１个城镇.要求经过每个城镇恰好一次,然后返回原地,问他地旅行路线怎样安排才最经济？从图论地观点来看,该问题就是：在一个有权完全图中找一条权最小地哈密尔顿回路.研究这个问题是十分有趣且有实用价值地.但很可惜,至今没有找到一个很有效地算法.当然我们可以用枚举法来解,但是当完全图地结点较多时,枚举法地运算量在计算机上也很难实现.下面介绍地“最邻近方法”给出了问题地近似解.最邻近方法地步骤如下：1) 由任意选择地结点开始, 找与该点最靠近（即权最小）地点, 形成有一条边地初始路径.2) 设ｘ表示最新加到这条路上地结点, 从不在路上地所有结点中选一个与ｘ最靠近地结点, 把连接ｘ与这一结点地边加到这条路上. 重复这一步, 直到G中所有结点包含在路上.3) 将连接起始点与最后加入地结点之间地边加到这条路上, 就得到一个圈, 即为问题地近似解.【例10.4.5】某流动售货员居住在ａ城,为推销货物他要访问ｂ,ｃ,d城后返回ａ城.若该４城间地距离如图10.4.12所示,试用最邻近方法找出完成该旅行地最短路线？解按最邻近方法一共有４步,见图10.4.13. 得到地总距离为46.（10.4.12）寻找哈密顿路径是一个典型地NP-完全问题.后来人们也证明了,找一条哈密顿路地近似比为常数地近似算法也是NP-完全地.寻找哈密顿路地确定算法虽然很难有多项式时间地,但是这并不意味着只能进行时间复杂度为O(n!*n)暴力搜索.利用状态压缩动态规划,我们可以将时间复杂度降低到O(2^n*n^3),具体算法是建立方程f[i][S][j],表示经过了i个节点,节点都是集合S地,到达节点j时地最短路径.每次我们都按照点j所连地节点进行转移.哈密顿路图论在许多领域,诸如物理、化学、运筹学、计算机科学、信息论、控制论、网络理论、社会科学以及经济管理等各方面都有广泛地应用,它已经广泛地应用于实际生活、生产和科学研究中.所以作为二十一世纪地应用型,我们应该好好学习图论,把图论应用到现实生活中,帮我们解决一些实际生活中地问题,让所学地知识更好地服务于我们.。

31
小结
• 欧拉图 Easy – 充要条件 • 哈密顿图 Hard – 必要条件 – 充分条件
32
13
无向半哈密顿图的充分条件
• 定理8.7: 设G是n(2)阶无向简单图, 若对G中任意 不相邻顶点u与v有 d(u)+d(v)n-1 则G是半哈密顿图. • 证: 只需证明 (1) G连通 (2) 由极大路径可得圈 (3) 由圈可得更长路径
14
定理8.7证明(1)
• (1) G连通: uv( (u,v)E w((u,w)E(w,v)E )
18
无向哈密顿图的充分条件二
• 推论2: 设G是n(3)阶无向简单图,若对G中任意顶点 u有 d(u)n/2 则G是哈密顿图. #
• 定理8.8: 设u,v是无向n阶简单图G中两个不相 邻顶点,且d(u)+d(v)n, 则 G是哈密顿图 G(u,v)是哈密顿图. #
19
有向半哈密顿图的充分条件
vi-1
vi
定理8.10证明(2)
• 则 C’=v1v2…vi-1vvi…vkv1 是长度为k+1的圈.
vi-1 v vi v
vi-1 vi
24
定理8.10证明(2)
• 否则, 令 V1={vV(D-C) | uV(C), <u,v>E(D) } V2={vV(D-C) | uV(C), <v,u>E(D) } 则 V1,V2, V1V2 = .
7
无向哈密顿图的必要条件
• 定理8.6: 设G=<V,E>是无向哈密顿图, 则对V的任意 非空真子集V1有 p(G-V1) |V1|。 • 证明：设C是G中任意哈密顿回路, 当V1中顶点在C 中都不相邻时, p(C-V1)=|V1|最大; 否则, p(C-V1)<|V1|. C是G的生成子图, 所以p(G-V1)P(C-V1)|V1|. #

K3
K4
Kn(n3)有Hamilton回路
b
b
b
a
c
a
ca
c
e
d
e
d
e
d
一个基本的必要条件
如果图G=(V, E)是Hamilton图，则对V的任一非空子 集S，都有 P(G-S) |S|
其中， P(G-S)表示图G-S的连通分支数.
理由：设C是G中的Hamilton回路, P(G-S) P(C-S) |S| 向一个图中顶点之间加边不会增加连通分支。
必要条件的应用
举例
c
a
b
将图中点a, b, c的集合记为S, G-S有4个 连通分支,而|S|=3. G不是Hamilton图.
举例
Kh
Kh
Kn-2h
下图给出的是 C2,7的具体图 (h=2,n=7)
必要条件的局限性
必要条件只能判定一个图不是哈密尔顿图
Petersen图满足上述必要条件，但不是哈密尔顿图。
u,v均满足：d(u)+d(v)n-1，则G是连通图。
假设G不连通，则至少含2个连通分支，设为G1, G2。取xVG1, yVG2, 则：d(x)+d(y)(n1-1)+(n2-1)n-2 (其中ni是Gi的顶点个数)， 矛盾。
充分条件的讨论
“ (G) n/2”不能减弱为： (G) 举例，n=5， (G)=2 . G不是Hamilton图.
有限图G是Hamilton图充分必要其闭合图C(G)是 Hamilton图.
闭合图(举例)
a
b
f
c e
d
判定定理的盲区
从“常识”出发个案处理
一顶点关联的边中恰有两 条边在哈密尔顿回路中。

f(0)=0; f(x)的图像关于原点对称； 若f(x)有最值，则f(x)max+f(x)min=0,等等
即探求定义在R上的函数f(x)为奇函数的 必要条件.
2.已知 a // bb
α
c b c,b d,c dO Od
ba,ac,ad
a,c,d
寻找 b 的充分条件 …,直至已知
复习回顾
下列各题中，p是q的什么条件？
A.充分不必要；B.必要不充分；
C.充要；
D.既不充分也不必要.
1.p:函数f(x)的定义域关于原点对称，
q:函数f(x)是偶函数；
( B)
2.p:直线l与圆C相切，
q:圆心到直线的距离等于半径；( C )
3.p:空间两条直线平行，
q:两条直线与同一平面所成角相等；
； seo优化怎么做 https:///SEO/ seo优化怎么做
；
春日之白鹭掠过绿潭的世界，然而大部分时候像现在，是一口沾了年代的大鼎，熬着肉骨头，响起沉闷的沸泡。我读到一股腥香，这幅幻画是一页多脂肪的食谱。我仿佛听到白袍侍者正在长桌上摆设银刀叉，金属的碰触声使夏日有了主题。想必秘密的邀请卡都发了，盛夏筵席正等待华服宾客， 也等着萃取他们的热汗，调一桶咸咸的开胃酒。那么，我没有理由取缔那只挨饿的小虫了，她盗用我的名字，挤入人堆，搂抱自己的肉骨头渴望接近火，幻想鲜美的肉汁慢慢渗透舌根的滋味。她活着，跟众人一起活着。 我不忍心苛责什么，打算永远不告诉她真相。渐渐兴起同欢的兴致观赏画 中人物，我仍然坐着，被我抛弃的她正在百货大楼门口按电话。夏季五折消息的悬布刷下来，画了个泳装墨镜打扮得油脂少女，正好遮去她的上半身，衔接那件过于老气的裙子及双脚，仿佛她也是打折货，七折八扣拍卖着。她不知道自己正站在很可笑的位置变成拼装人被我偷窥，依旧严肃地按 电话键。有位慌张男子从她身旁蹿出，趁黄灯大跑步杀过马路，有些人见机尾随，却被困在路中央进退不得，那些六亲不认的，就算是站在斑马线上有他的亲爷爷，一样拉一蓬黑烟赏他。这就是活得真真的世界。她终于接通电话，捂耳朵大喊：“请大声点儿，我根本听不到，这里好吵……”服 饰店的音响如山崩海裂，“什么？再大声点……”他只听到话筒内像大卡车倒沙石，不知道谁接了电话？说了什么？也许那个人正是她要找的，也许不是……她愤愤地挂了，冲进服饰店想找人吼：“你们卖衣服还是治耳聋的？”与她擦身而过，从服饰店走出来一位很满足的胖妈妈牵着胖儿子的 手，胖儿子牵着胖嘟嘟的蛋卷冰淇淋，冰淇淋牵着儿童的舌头，舌头吧嗒吧嗒朝灌气球的小贩说好好玩，小贩将气球系在孩子的太阳帽上，现在气球把整栋大厦稳稳顶住了。胖妈妈侧身看一名刚到的女贩撑开脚架，掀开大木箱，斑斓的珠子项饰激迸锐光，那女贩用会施魔法的手拎出一串，圈牲 口般挂在胖妈妈的脖子上，两个女人正在鉴赏镜子里的幻象，她在服饰店等管音乐的人上完厕所，从衣列的空袭窥视那两个女人的嘴唇干戈。胖儿子抱着行人号志灯杆溜圈圈，气球也溜圈圈，胖儿子被绕住了，气球破了，鲜还缠着，喊妈妈。她偷笑：“把帽子拿下来嘛，真是的！”胖妈妈牵着 胖儿子过马路了，女贩朝她们露了轻蔑的冷脸，那张脸布着善谋的狂妄，仿佛她的床底下养了只害喜的大母贝，每天早晨呕吐一箩筐珠子后，就舒服多了。他熟谙那些阅读床第与繁殖课本的人对圈套的依赖，珠子项链也就生意不恶了。她终于使热门摇滚的兽声减低，目送胖母子安全抵达对街， 等待女贩谈妥下一笔交易，把那具电话空出来。她捏着一块钱币，认分地站着，开始幻想公共电话肚子里的钱币谈过什么？也许他们正在轮流放音；有的高声尖笑，有的结结巴巴如含了颗大石榴，有的钱币克药般嘟囔：“我爱你，永远爱你，无法自拔地爱你……”有的愤怒：“不必解释，我再 也不相信你说的话……”她非常气馁，刚才她的钱币只会说：“请大声点……根本听不到……什么？……”颓丧的情绪是她疲惫起来，炎夏的阳光滑过肌肤，汉汩汩地濡湿额头。她想放弃一块钱的对谈，让那位等着她去做感情谈判的男子去等，他若不相等就自然不会等，她忽然觉得无话可 说。 ?这就是活着吧，我想。空中不时响起预告欢宴的高音小喇叭，揉杂在鼎沸的街声里。我无法携带亲密的她一起回去潭深水绿的世界，看一群白鹭如会飞的雪。她属于华丽的市街，与众人一样怀着秘密请帖，共同使用街衢，赶路、错身而过、穿梭迷巷，趁天黑之前找到乐园的大门。每个人 都希望是第一个接受洒花的贵宾，挑选美味的炖肉，啜饮餐前酒，优雅地使用刀叉。或许落地玻璃框的缘故，我隐约看到这幅欢宴图浮凸着恶魔的背书，受邀者正走入一个被决定的主题里，有一口大鼎等待烹调那批新鲜的肉骨，当他们在黑胡椒的诱拐下饱啖他人之肉，自己的肉也将在别人的瓷 盘上消瘦。我不知道谁是这场筵席里最开敞的娇客？但既然隶属市街，我再无能力阻止她去奔赴神奇的邀约。虽然，此刻的她沮丧地坐在路边的白椅上，一块钱币浸泡在手掌的汗液里。 所以，当你——陌生的街头女人出现在我的眼眶内，攲睡在那颗槭树的薄荫下，我几乎认错你躺卧在我的深 潭堤岸，是年轻时代熟悉的女鬼。 ? 你当然不是鬼，隔一段距离，仍然看得到蓬乱的发式与污秽的花裳。或许一切曾经鲜丽，被灰尘纺织之后，就变成人人躲避的异乡客。你是流动画面上唯一的静止，这使我的眼光逡巡的再远终会回到槭树与你。我们随同在时光中静止，确信在你午憩的残梦里， 与你隔岸对看的人不是我，你不会发觉我正在观看你、推敲你，甚至欣赏你与青槭形成的凄美布局；仿佛在你之前有人于树下坐出一团灰渍，在你之后也会有人依影续坐。不知道明日谁将坐在我的位置观看树下的谁？甚至不敢说，被我遗弃于街道的她，有一天会不会也成为别人眼中的树下鬼？ 但，我与你既然目遇，你的心飘向何处非我能及，我的心却通过你的睡躯飘向另一个时空，田边坝头，那从闹鬼的麻竹林，有人一直摇晃竹桠。 我还小，常常走哪条唯一的土路到镇上。水坝在路的中段，对岸竹树高茂，蔓藤乱荡，分不清树种，好像亘古纠缠就是他们的名字。风大的季节，整 排竹树往这岸折腰，仿佛地狱内千万个冤死鬼，伸出绿手臂抓替身。如果风更猛，则是一亿条舌头朝路人脸上吐绿口水了。树躯内，蝉叫得凶恶，千军万马喊杀也不过如此。忽然，风停，树静，蝉噤，听得见阳光的小碎步，喧哗的河水从掣水闸奔泻而下，打着漩涡，不断浮升白泡沫，又被阳光 的碎步一个个踩破，偶尔落闸的布袋莲，晕头转向地，像被弃的紫尸。坝路四周尽是稻原菜圃，看不见屋舍。除了早晨、黄昏上学的孩童，漫长的白昼嗅不到人味。我每次经过，总感到心脏的鼓动，有一股冰冷的绿雾经年笼罩着竹树、水坝、堤路，愈靠近它愈冷。我甚至陷入臆想，看到自己走 入绿雾，一寸寸被溶解，散出白烟，身下绑辫子的红蝴蝶结、洋装及两只木屐落在地上，一只绿茸茸的野犬扑来，捧着木屐啃啮，舔食我那温湿的脚泽…… “你们不知道自己的小孩已经死了，还喝酒！”我躺在眠床上漫思，坝头那团绿雾仿佛破窗而来，举起我、晃动我。隔壁饭桌飘来菜香， 人世的肉肴十分呛鼻，却也不难闻。抡拳闹酒的汉子们嫌酒淡了，开始叙述鬼魅的乡野传奇，好像不说点刀光血影的见识，这辈子就软了。有人在鬼月的银光下，撞见她蹲在坝头不远的田沟洗衣，以为是哪家媳妇、女儿？朝她喊：“喂——谁人女儿？三更半夜洗什么衫？快回去睡！”她没应， 兀自蹲着；那人架住脚踏车，想过岸说话，忽然不见人影，黑黝黝的原野只有一钩冷月，他会意她的来头，狂奔回家，一张茭白笋脸从此红不回来，隔日起害病十多天，鬼门收关哪天才能下床找拖鞋……“鬼不会老，他若不跳水，跟我阿祖同辈分，几十年后看起来，还是未出阁的姑娘样！” ? 他们说起她被人遗弃的故事，话语传入蚊帐内，我字字句句仔细听着，替她听，仿佛我是她的内贼、她的耳朵。“你们不知道自己的小孩已经死了，还喝酒！”她要我这样说，声音在我嘴里蠕动着，只有自己听见。我抱怨：狗咬坏木屐，你会赔我么？她说：鬼不走路，遇见风，跟风走；遇见水， 跟水流。我说：“花心。”被踩了会痛么？她说：很痛。我说：那么夏天淹大水，谁忽然退了，你来不及跟，是不是像一块布搭在鸡寮顶下不来？她说：得回去洗衣了，夜里露水重，总晒不��

condition to ensure a graph being hamil -回复如何确保一个图是哈密顿图？哈密顿图是图论中的一个重要概念，指的是一个图中存在一个哈密顿回路，即可以从图中的任意一点出发经过每个点一次且仅一次后回到出发点。

在许多应用领域，如电路设计、旅行商问题等，哈密顿图都具有重要的意义。

那么，如何确保一个图是哈密顿图呢？下面将一步一步回答这个问题。

第一步：理解概念和要求在进一步讨论如何确保一个图是哈密顿图之前，首先我们需要理解哈密顿图的概念和要求。

哈密顿图是指一个图中存在一个哈密顿回路，即可以从任意一点开始，经过每个顶点一次且仅一次后回到起始点。

所以，要确保一个图是哈密顿图，需要满足以下条件：1. 图中的每个顶点都必须与其他顶点相连。

2. 图中不能有孤立顶点，即每个顶点都必须至少与一个其他顶点相连。

3. 图中不能有割顶，即移除该顶点后，图不再连通或不再是哈密顿图。

第二步：检查图中的割顶为了确保一个图是哈密顿图，我们需要检查图中是否存在割顶。

割顶是指移除该顶点后，图不再连通或不再是哈密顿图。

为了检查一个图中是否存在割顶，可以使用割顶判定算法，如DFS（深度优先搜索）算法或Tarjan 算法。

在DFS算法中，通过对图进行深度优先搜索，我们可以检查每个顶点的连通性，并标记已访问的顶点。

如果在搜索过程中，存在一个顶点v，移除该顶点后，图不再连通或不再是哈密顿图，那么v就是一个割顶。

Tarjan算法是一种基于DFS的割顶判定算法，通过对每个顶点进行深度优先搜索，可以找出所有的割顶。

通过调用Tarjan算法，我们可以检查图中是否存在割顶，并且移除割顶后，图仍然是连通的。

如果存在割顶，则该图不是哈密顿图。

第三步：检查图中的连通性除了检查图中是否存在割顶外，我们还需要检查图的连通性，以确保图中的每个顶点都可以互相到达。

可以通过广度优先搜索（BFS）或深度优先搜索（DFS）等算法来检查图的连通性。