张成岗(CZ)的博客世界分享 http://blog.sciencenet.cn/u/zcgweb 脑损伤与脑保护;神经认知;生物信息;蛋白质组;辐射损伤与防护

博文

[转载]图论及其应用-哈密尔顿图(alpha)

已有 217 次阅读 2020-10-30 15:09 |系统分类:科研笔记|文章来源:转载

https://www.cnblogs.com/titer1/archive/2011/04/12/2014226.html 

图论及其应用-哈密尔顿图(alpha)

 

小结:2010-04。。todo 没有粘贴公式。

1重要的概念是 闭包。

注意 ppt定义4

2重点汇总与 闭包定理

3其他的2个定理对比:(第一阶级:是不是两个反面)

一个是

 存在 不相邻的点u , v, 围绕 du + dv >=n; G H图,那么G+uv也是H图(66:增边)

                      满足du + dv >=n 都有u,v相邻,那么G是闭包、

 

本次课主要内容

()、哈密尔顿图的概念

()、性质与判定

哈密尔顿图

     1、背景

()、哈密尔顿图的概念

    1857年, 哈密尔顿发明了一个游戏(Icosian Game).它是由一个木制的正十二面体构成,在它的每个棱角处标有当时很有名的城市。游戏目的是“环球旅行”。为了容易记住被旅游过的城市 ,在每个棱角上放上一个钉子,再用一根线绕在那些旅游过的城市上(钉子),由此可以获得旅程的直观表示。

clip_image001

     哈密尔顿(1805---1865),爱尔兰数学家。个人生活很不幸,但兴趣广泛:诗歌、光学、天文学和数学无所不能。他的主要贡献是在代数领域,发现了四元数(第一个非交换代数),他认为数学是最美丽的花朵。

    哈密尔顿把该游戏以25英镑的价格买给了J.Jacques and Sons公司 (该公司如今以制造国际象棋设备而著名1859年获得专利权。但商业运作失败了。

    该游戏促使人们思考点线连接的图的结构特征。这就是图论历史上著名的哈密尔顿问题。

     2、哈密尔顿图与哈密尔顿路

     定义如果经过图G的每个顶点恰好一次后能够回到出发点,称这样的图为哈密尔顿图,简称H图。所经过的闭途径是G的一个生成圈,称为G的哈密尔顿圈。

    1、正十二面体是H图。

clip_image002

     下图G是非H图。

     证明:因为在G中,边uv是割边,所以它不在G的任意圈上,于是uv不能在G的同一个圈上。故G不存在包括所有顶点的圈,即G是非H图。

clip_image003

     定义如果存在经过G的每个顶点恰好一次的路,称该路为G的哈密尔顿路,简称H路。

clip_image004

()、性质与判定

     1、性质

     定理1 (必要条件GH图,则对V(G)的任一非空顶点子集S,有:

 

     证明:GH图,设CGH圈。则对V(G)的任意非空子集S, 容易知道:

 

     所以,有:

 

     注:不等式为GH图的必要条件,即不等式不满足时,可断定对应图是非H图。

     求证下图是非H图。

     证明:取S=2, 7, 6,则有:

clip_image005

 

     所以由定理1知,G为非H图。

clip_image007clip_image008

      注意:满足定理1不等式的图不一定是H图。

      例如:著名的彼德森图是非H图,但它满足定理1的不等式。

clip_image009

     彼得森(1839----1910),丹麦哥本哈根大学数学教授。家境贫寒,因此而辍过学。但19岁就出版了关于对数的专著。他作过中学教师,32岁获哥本哈根大学数学博士学位,然后一直在该大学作数学教授。

     彼得森是一位出色的名教师。他讲课遇到推理困难时,总是说:“这是显而易见的”,并让学生自己查阅他的著作。同时,他是一位有经验的作家,论述问题很形象,讲究形式的优雅。

     1891年,彼得森发表了一篇奠定他图论历史地位的长达28页的论文。这篇文章被公认是第一篇包含图论基本结论的文章。同时也是第一次在文章中使用“图”术语。

     1898年,彼得森又发表了一篇只有3页的论文,在这篇文章中,为举反例构造了著名的彼得森图。

clip_image010

     2、判定

      图的H性判定是NP-困难问题。到目前为止,有关的定理有300多个,但没有一个是理想的。拓展H图的实用特征仍然被图论领域认为是重大而没有解决的问题。

     图的哈密尔顿问题和四色问题被谓为挑战图论领域150年智力极限的总和。三位数学“诺奖”获得者ErdÖsWhitney  Lovász 以及DiracOre等在哈密尔顿问题上有过杰出贡献。

     下面,介绍几个著名的定理。

     定理2 (充分条件对于n3的单图G,如果G中有:

 

     那么GH图。

     证明若不然,设G是一个满足定理条件的极大非H简单图。显然G不能是完全图,否则,GH图。

     于是,可以在G中任意取两个不相邻顶点uv。考虑图G + u v,由G的极大性,G+ u vH图。且G+ u v的每一个H圈必然包含边u v

     所以,在G中存在起点为u而终点为vHP

     不失一般性,设起点为u而终点为vHP为:

 

clip_image011

     令:

 

 

     对于ST, 显然,

     另一方面:可以证明:

 

 

     所以:

 

     否则,设                     

 

     那么,由

 

     

 

clip_image012

     这样在G中有H圈,与假设矛盾!

     于是:

     这与已知                     矛盾!

 

     注:该定理是数学家 Dirac1952年得到的。该定理被认为是H问题的划时代奠基性成果。

 

     Dirac曾经是丹麦奥尔胡斯大学知名教授,杰出的数学研究者。其父亲(继父)是在量子力学中做出卓越贡献的物理学家狄拉克,1933年获诺贝尔物理学奖。Dirac发表关于H问题论文39篇。他1952年的定理将永载史册!

 

     1960年,美国耶鲁大学数学家奥勒(Ore)院士考察不相邻两点度和情况,弱化了Dirac条件 ,得到一个光耀千秋的结果。

       Ore发表关于H问题论文59篇。

     定理3 (充分条件对于n3的单图G,如果G中的任意两个不相邻顶点uv,有:

 

       那么,GH图。

       : (1) 该定理证明和定理2可以完全一致!

       (2) 该定理的条件是紧的。例如:设G是由Kk+1的一个顶点和另一个Kk+1的一个顶点重合得到的图,那么对于G

 的任意两个不相邻顶点uv,有:

 

     G是非H图。

clip_image014clip_image015

      1976年,牛津大学的图论大师Bondy(帮迪)等在Ore定理基础上,得到图G和它的闭包间的同哈密尔顿性。

     注:帮迪的书《图论及其应用》是一本经典必读教材。有中译本和习题解答。吴望祖译 

     引理对于单图G,如果G中有两个不相邻顶点uv,满足:

 

     那么GH图当且仅当G + u vH图。

     证明:“必要性” 显然。

    “充分性”

     若不然,设G是非H图,那么G+uv的每个H圈必然经过边uv, 于是G含有一条哈密尔顿(u ,v)路。

clip_image011

     与定理2的证明相同,可推出:

     定义n阶单图中,若对d (u) + d (v) 的任意一对顶点uv,均有u a dj v , 则称G是闭图。

     引理G1G2是同一个点集V的两个闭图,则G=G1G2是闭图。

 

     这与条件矛盾!

     证明:任取u, vV(G1  G2),如果有:

 

   易知:

 

     G1G2都是闭图,所以uvG1G2中都邻接,所以,在G中也邻接。故G是闭图。

     注:G1G2都是闭图,它们的并不一定是闭图。

     例如:

clip_image017clip_image018

clip_image019

clip_image021

     尽管G1G2是闭图,但其并不是闭图!

     定义4        是图G的闭包,如果它是包含G的极小闭图。

 

     注:如果G本身是闭图,则其闭包是它本身;如果G不是闭图,则由定义可以通过在度和大于等于n的不相邻顶点对间加边来构造G的闭图。例如:

clip_image023clip_image025

     引理3  G的闭包是唯一的。

     证明:设               是图G的两个闭包,则:

 

 

 

 

     所以,有:

 

     又由引理2知,                 是闭图,且

 

 

     有:

 

     同理:

 

     所以,

 

     定理4(帮迪——闭包定理GH图当且仅当它的闭包是H图。

     证明:“必要性”显然。

  “充分性” :假设G的闭包是H图,我们证明GH图。

   假设G的闭包和G相同,结论显然。

   若不然,设ei (1ik)是为构造G的闭包而添加的所有边,由引理1GH图当且仅当G+e1H图,G+e1H图当且仅当G+e1+e2H,反复应用引理1,可以得到定理结论。

     由于完全图一定是H图,所以由闭包定理有:

     推论1:设Gn3的单图,若G的闭包是完全图,则GH图。

     由闭包定理也可以推出DiracOre定理:

     推论1:设Gn3的单图。

     (1) 若δ(G)n/2,GH(Dirac定理);

     (2) 若对于G中任意不相邻顶点uv,都有d(u)+d(v)n,GH.(Ore定理)

     在闭包定理的基础上,Chvátal和帮迪进一步得到图的H性的度序列判定法。

      定理5(Chvátal——度序列判定法设简单图G的度序列是(d1,d2,,dn), 这里,d1d2≦…≦dn,并且n3.若对任意的m<n/2,或有 dm>m,或有dn-m  n-m,GH图。

     萨瓦达定理的证明方法:证G的闭包是完全图。

     证明:如果G的闭包是Kn,则GH图。

     否则,设uvG的闭包中不相邻接的且度和最大的两点,又假设:

 

     由于     是闭图,u是其中不邻接顶点,所以:

 

 

     于是,若取                      ,则

 

 

     对于这个m, 由于:

 

     所以在G的闭包中至少有m个点与v不邻接。

     uv的取法知:与v不邻接的m个点中,u的度数最大。这就意味着:G中至少有m个点的度数不大于m,即:

 

     另一方面,由m的选取,G的闭包中有n-1-m个点与u不相邻接。而这些点中,v的度最大。这意味着:在G的闭包中有n-1-m个与u不邻接的点的度数小于等于v的度数。

     但是,由:

 

     以及u的度数不超过v的度数假设,G的闭包中至少有n-m个点的度不超过n-m,从而在G中至少有n-m个点的度数严格小于n-m,即:

 

     4  求证下图是H图。

     证明:在G中有:

clip_image044

 

 

 

 

   n=9,所以,m=1,2,3,4

 

     所以,由度序列判定法,GH图。

     :哈密尔顿图研究简介

     哈密尔顿问题的研究一直是图论热点。研究历史大致情况如下:

     (1) 1952Dirac定理是研究的奠基性结果;

     (2) 1962Ore定理是Dirac定理的重要推进;

     (3) 1976年帮迪的闭包定理是Ore定理的重要推进;

     (4) 1985年时任剑桥大学兼伦敦大学教授的Nicos在弱化Ore定理条件基础上推进了Ore定理;

    (5) 1996GSU计算机系五个特聘教授之一的ChenSCI

杂志《图论杂志》编委EgawaSCI杂志《图论与组合》主编

Saito等再进一步推进Ore定理。

     (6)  2007赖虹建教授统一上面全部结果(见美国Appl.Math.Lett.),似已是珠峰之极.

     值得一提的是,福州大学的 范更华教授对H问题的研究也取得重要成就,他得出“范定理”:

    范定理:若图中每对距离为2的点中有一点的度数至少是

图的点数的一半,则该图存在哈密尔顿圈。

     该成果获得中国2005年度国家自然科学二等奖。

 作业

  P97---99    习题 10,  12

Thank      You !




http://wap.sciencenet.cn/blog-40692-1256364.html

上一篇:[转载]应游戏而生的数学图论,多栖发展的数学家哈密顿,传奇人生
下一篇:医学突破必将来自于生命起源与进化生物学的研究突破

0

该博文允许注册用户评论 请点击登录 评论 (1 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-11-28 11:11

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部