下面工作被这里某大学正校长评价说海南琼大的“哈密顿图在国内图论界做得这么全面的是少有最简单的2页证明的含参数的邻域并泛圈海南琼大1991年已完成后世界各国仍再做约20才完全,那更复杂的如不含参数的邻域并泛圈我约200页证明…),如宋理事长说世界上在邻域并做得最好的是海南,并若解决基于它的问题“全世界科学家可放假7来庆祝”--刚更见给海南琼大来信的惊天大突破,并哈密顿图是最优试金石下面8节是几十年来最重要的邻域并为主的16领域分支并被哈密顿图世界第一的美籍赖大师说世界领先、美国前十大学主席说世界领导性海南也做哈密顿图全部次要领域),要知“各省先驱做“遍布全国、席卷全国”的它且仅有几篇论文;我做哈密顿图这样多是因这里首段说一入学导师已拿着我的一堆论文训我的师兄们、海南最伟大的极集论我仅用5分钟国家一等奖本原矩阵十几篇仅用3等等:

哈密顿图综述。引子1: 就因为艰巨使得在我们海南琼州大学之后全世界对哈密顿图(简称H)的研究已全都只好分为各类小的特殊图类去研究,即因它是已历经一千多年历史的世界最悠久特大难题,如此美国及欧洲大师们历经长期探索20世纪80年代初终于再进一步迈出世界上对一般图的哈密顿图的最后一轮探险步伐而酝酿出研究它的邻域并条件--之后以前研究它的各类条件也就逐渐已全都退居二线甚至退出历史的舞台而可预见将是最后的条件“邻域并条件”-其历史性也将无言而喻-并其除了研究哈密顿图的最基本的H圈之外的哈密顿图其它全部更难领域如哈密顿连通、泛圈(上面20年和200页都是泛圈的)、点泛圈、边泛圈、泛连通、最短路泛圈等等领域分支在世界上都是海南琼州大学最先突破(并如上面说次要领域即退居二线的条件研究它的各领域海南琼大也再一次全做到世界进一步的世界领先),这领域就如高度评价海南琼州大学的哈密顿图具有世界领先水平的香港数学会主席说它是“未来数学家的挑战”的最具代表性问题并且很多学科都起较大的推动作用(但也极其艰巨就如世界第3大师著作哈密顿图一章最后就搬出创造二战中拯救人类和世界的最伟大壮举的图论之父Tutte你们做不到欧拉大声说道。…而且越来越精彩,绽放在密歇耶鲁”(就如我1985年已被我后来的导师柳柏濂教授的报告会迷到会后我竟与一堆我们大学领导欢送他并只有我一人追随他到校主门外目送他的车消失在茫茫的夜幕中而3年后的1988年由广东教育出版社出版的他的一本书中仍重温“为了寻找图的哈密顿圈存在的充分条件,一百多年来,不知耗费了多少数学家的精力-很多人也以哈密顿的最著名工作为开端但其实应是一千多年来),即虽做不到但其精彩使佛普林耶鲁等美国每个大学都在乎都一代代不计其数的数学家为之赴汤蹈火; 丘成桐大师美国无人在乎陈景润哥德巴赫猜想。哈密顿图就如若解决全世界科学家将放假七天来庆祝“P vs NP问题3行字是Typical of the NP problems is that of 哈密顿路Problem,它也计算机科学的世界第一问题;最近邀请海南琼州大学去给他的包括已成航母统帅30个博士生及其它研究人员做报告的宁院长历经十年9500实证对哈密顿图问题…足见何等艰巨-20多年前我同时开创世界三大数学难题四色问题新纪元和下面进展就尝遍了鱼与熊掌之极端无奈

精彩也如Andrásfai的《图论导引》前言说图论的魅力不亚于当年的希腊文明--这书用五章阐述-第四章全部13都是哈密顿图-堪称希腊文明核心这里也见它在数理化生计医等学科都有非常重要的作用,如在计算机方面-以前曾来信表达非常愿意推荐海南琼州大学加入某世界科学组织的这页倒数第2段的美国工程院院士Cook的世界名著迷茫的旅行商:一个无处不在的计算机算法问题说“年复一年,许多无畏的数学家提出了哈密顿圈的充分条件,可是他们的猜想最后都被推翻了。Applegate教授在研究这问题时就将‘不屈不挠、前进到底’做为战斗口号”。注:旅行商问题就是最小哈密顿圈问题,下面各节就是分别对一般图的哈密顿圈, 哈密顿连通, 泛圈, 点泛圈, 边泛圈, 泛连通等等的综述其艰巨就如评价海南居国际先进的刘振宏大师说“一般哈密顿图非常不容易”,可参考图论若干领域以及若干相关专题

摘要:2005哈密顿圈及圈覆盖理论获得国家三大奖中最难获得的国家自然科学奖.下面综述以中科院权威大师刘振宏老师等在1991首届全国哈密顿图大会的综述文章的所有领域即哈密顿图六个领域:哈密顿, H连通, 泛圈, 点泛圈, 边泛圈, 泛连( H图是有H,如此H图主要是这6个主领域-16分支领域)为基础-并有所扩展. 这些领域之众如这首届哈密顿图大会在当时就已是百人大会, 而数学缺会者更众/计算机等大多也涉足. 会上重述一般非常不容易, 国家奖范校长回国前除和刘振宏老师合作外其它合作都和国外权威但也做下面1哈密顿而至今仍没做H图的其它领域, 即还没见其做上面6个领域的后五个领域. 获国家奖是范校长H圈的卓绝贡献, 此外他涉足的其它一些领域-也甚为惊艳. 一直鞭策着海南琼大倾力而为才成为世界上最先突破邻域并H图性即上面后五个领域居世界领先, 著名数学家某大学柳校长在2001年已说海南琼州大学在一千多年的世界最悠久哈密顿全部16领域全都居世界领先并说中国图论界能搞这么全面的是少有, 宋理事长在90年代初更已说世界上在邻域并的复圈结构图十几个领域做得最好的是海南’, GL世界第3的大师说H图做出重要贡献, 美国大师说献身科学, 宝理事长说成就很辉煌,如此1991年的华师大全校大会上唯一得到校长和几千研究生等多次起立鼓掌)

关键词: 上千年的世界最悠久特大难题重灾区的中国唯一贫困市

引子2:哈密顿图有很多极其重要的作用,不仅对集成电路等一些高科技领域,而且一些颠覆世界名震天下的重大问题如这里的NP=P问题也基于哈密顿图,之重大就如Charles Stross获得科幻诺贝尔奖名著说NP=P被证明之后AI会变得强大无比(当然也有象计算机巨头比尔×盖茨认为AI毁灭人类。总之,许多诺贝尔奖得主等大师都说若如此世界将天翻地覆本来2002年做此网站前已证我下面16问题等都NP完全的,其意义就如克雷所发布千禧年七大难题之“P vs NP”3行字全为Typical of the NP problems is that of 哈密顿路Problem也如诺奖得主Hopcroft这名著NP部分就说为了感受NP的能力,本章将考虑旅行商问题:图是否具有总权至多为W哈密顿圈宁院长等也从哈密顿路去处理NP=P?

这领域之意义也可见冠绝所有首相的英国首相Wilson的任牛津大学教授的亲儿子的图论网第4书和他的哈密顿图综述文章(中科大只选二篇哈密顿问题综述文章-分别是这Wilson编辑的和Gould主席). 下面综述看到海南琼州大学在全部领域都做到顶峰-不少似历经华山一条路,特别是下面2节后各定理都用约十页才证完一些用了约200--其难就象丘成桐说最痛苦的两周-这里见丘成桐的这痛苦工作和博士论文

下面琼大的50个主要方向的50个定理的大多数中的每个都要用约十页才能证完-并下面综述的分类就依照刘振宏大师Hamilton问题的研究概况论文的摘要说“综述了Hamilton圈、泛圈性、Hamilton连通性一样的分类其中彻底突破22个瓶颈的泛圈图定理的这篇用约200页证明,并除了一般图的哈密顿图工作,海南琼大还完成很多各类特殊限制图如象这类无爪图中的哈密顿图论文但为节省篇幅就不在下面不列出,另外海南琼大也完成一些最长圈论文但因不是哈密顿图也不列出:

1哈密顿圈(Hamilton)问题是最好的老师-是普遍共识,还如Paul Halmos说“问题是数学的心脏”等等-足见问题之关键,如卡拉比猜想造就丘成桐,庞加莱猜想使FreedmanSmale瑟斯顿佩雷尔曼等都获诺贝尔奖,庞加莱猜想仅有百年«哈密顿图问题则已千年-其难度等也将。再看歌猜-丘成桐说美国无人在乎陈景润歌德巴赫猜想,而这里见不要说美国大量的普通大学-就是一直居美国前3哈佛,普林斯顿, 耶鲁都有诺贝尔奖得主做哈密顿图,就如引子说哈密顿圈很多盖世作用,所以不仅要多问问题、更要多做不断深入地做好问题。

(A). 度型:

1952英国数学家Dirac(狄拉克)开创哈密顿图划时代的下面定理1.1凭这定理1.1就足够光耀千秋彪柄史册( 也见这定理的纪录1纪录2,或见1990已在国际数学家大会做45分钟报告的数学大师Thomassen院士撰写的诺贝尔物理奖得主的儿子Dirac-就是他,即他的老爸Dirac杨振宁心中的第2巨人、自传中列为1偶像--这里倒数3,中国物理学之父也说和一位一代泰斗的物理学家相处三个月的经验,是很难得的必将引起人们长久的津津乐道。这Dirac父亲和其学生Sciama共同指导出物理博士霍金大师, 独立指导出印度近代2个最伟大数学家之一的Chandra这里倒数第2. Dirac为何不做他父亲的物理或印度也做的数学?而坚定地做有一千年悠久历史哈密顿图还有Dirac的母亲的弟弟即Dirac的亲舅舅威格纳Eugene Wigner也获得物理诺贝尔奖Eugene Wigner曾在海南州大学的导师柳柏濂教授去合作研究几年的美国威斯康辛大学任教[这里说Eugene Wigner在美国只在威斯康辛大学和普林斯顿任教并虽在威斯康辛大学仅几年但该校认识他的女学生并结婚等说到该校的篇幅很多Eugene Wigner的博士中的物理学界中唯一获得2次诺贝尔奖John Bardeen的本科硕士都在海南州大学的导师柳柏濂教授去合作研究几年的美国威斯康辛大学学习]。再附一点人们通常已知道这哈密顿图大师Dirac在英国、瑞典、法国、美国的大学都任教过,其实还有其它如他和史上十大天才Erdös合作的这篇论文上写Dirac其时是我国第一个数学诺贝尔奖获得者陈省身大师读博士生的汉堡大学的教授):

定理1.1(Dirac(狄拉克),1952[9]):n阶图G的每点xd(x)≥n/2,则G是哈密顿图。

1960美国耶鲁大学Ore(奥勒)凭下面定理1.2流芳千古:(也见纪录1纪录2。更非常令人迷惑的是,Ore院士的许多博士门徒都已成了计算机大师,如他既有“现代计算机之父”,又有“计算机之母,如此我们海南琼州大学的很多论文是从多方面发展这结果到各方面都居于世界领先)

定理1.2(奥勒,1960[25]): 对于顶点个数大于2的图,如果图中任意两点度的和大于或等于顶点总数,那这个图一定是哈密顿图

曾在普林斯顿大学爱因斯坦长期共事并共用同一个助手的历史上十大数学天才大数学家Paul Erdös和斯坦福大学权威Chvátal1972年得到:

定理1.3(Erdös, Chvátal,1972[8]) :若连通图G的独立数a连通度k,则G是哈密顿图。

哈密顿图大师、牛津大学著名博士Bondy华东理工大学施劲松教授将其称为图论教父)和斯坦福大学Chvátal大师在1976年建立闭包理论Bondy教授也在1976出版世界名著-《图论及其应用》-它其后一直被世界各国奉为首选教材;第一节是Bondy写的标题为Young Genius的这篇就是写哈密顿图权威Chvátal-其时他在世界第2斯坦福大学指导的博士D. Avis已和他同任DAM编委):

定理1.4(Bondy,Chvátal,1976[4]):n阶图G的不相邻两点x,yd(x)+d(y)≥n,则GG+xy同哈密顿性。

1984年时在连续10排名加拿大第一大学Tutte当时在这大学)的范更华教授得到下面名垂青史范定理

定理1.5(范定理,1984[10]) :2连通n阶图G的距离是2的任意两点x,y均有max{d(x),d(y)}≥c/2,则G是有c圈,当c=n时是哈密顿图。

上面已说哈密顿图之难居世界三大难题之首!它的重要性更如它的货郎担问题”(即最小哈密顿圈问题)每一次小进展都能震惊数学界--国首批博士导师管梅谷校长评介的苏联的一项发明震惊了数学界的工作就是货郎担问题”—见这里注解这震惊数学界

其后,海南省琼州大学赵克文等从下面多个最重要方向、许多关键层次促进和深化哈密顿圈的发展:

琼州大学和从美国第一大学(它经常居美国前4博士毕业后在日本东京大学工作几年并已很著名的北京大学宋教授合作得到

定理[1] (赵克文等):n阶图G的距离是2的任意两点x,y均有max{d(x),d(y)}≥(c-1)/2,则Gc或图Ж或图Ю或图Я

赵克文和美国西弗吉尼亚大学研究生院赖院长等将在美国Appl.Math.Lett.非常极致的推广H图型范定理

定理[2] (赵克文等):k连通n阶图G的任一含满足1≤|N(x)N(y)|≤α-1的两点x,yk个独立点组成的点集S,若有max{d(v):vS}≥n/2,G是哈密顿图。

 关于定理[2],它也发展某些国家一些专家的著名工作。下面列出它发展的其中3个定理,即下面定理1.6 定理1.7定理1.8 。详细附注如下:1987Wojda院士和欧洲最古老的著名大学之一的法国奥大运筹学科创建奠基人Benhocine教授2人合作仅局部推广上面范定理-即得到下面定理1.6 (全球最著名 Amer. Math. os Renyi维基网见波兰历史上200数学家中就有Wojda院士,在前面的是1230年出生的世界著名数学家Witelon维基网见中国仅有66数学家且古代及华侨不少-自然列入的还是国际化的。Wojda院士的学硕博士都在哥白尼母校-雅盖沃大学攻读,他的导师就是雅盖沃大学最正宗哈密顿图大师Skupień。刚见1971Wojda院士已和这导师合作发表哈密顿图论文但至今的会议和杂志论文一共才43,足见哈密顿图非常不容易;又如这法国 Benhocine教授1977年发表在法国科学院学报的哈密顿图论文就一直有国际影响, 但他至今仅有25篇数学论文且18篇是哈密顿图--再也可说明难。这两人都是哈密顿图大师,Wojda教授也在巴黎大学和波兰科学院等培养多个博士-当然此网常没有记录很多博士生)(波兰有许多非常利害的数学家--如泛函分析主要开创者Banach-巴拿赫就是最著名的代表之一。曾来信称赞我的工作的哈密顿图大师Béla Bollobás的博士Gowers的博士论文就是用组合方法处理巴拿赫空间问题的并解决巴拿赫的某些重要猜想而引起组合数学界的极大兴趣-即他的“主要成就在于运用组合数学的方法解决了巴拿赫空间理论中的一系列问题”其后获得数学诺贝尔奖-Fields,如此以前虽忙但我也算读完整本巴拿赫的世界名著线性算子理论-它就是讲Gowers研究的巴拿赫空间及F空间的算子理论--此于书成于20世纪30年代初,其后,Banach空间理论又有很多发展,特别是看本人的这个不动点理论专题网见自1965Kirk证明了具有正规结构自反的Banach空间具有不动点性质和1966Opial得到了具有Opial性质的Banach空间具有弱不动点性质后,利用Banach空间几何性研究非扩张类映射的不动点性质的理论得到了迅速发展

定理1.6 (Wojda):a(G)£n/2n阶图G, 距离是2的任意两点x,y均有max{d(x),d(y)}≥ (n-1)/2,则GH圈或例外图   

1998年我国清华大学著名专家俞教授也在某些方面改进上面范定理如下:

定理1.7  (俞教授): a(G)£n/2n阶图G, 距离是2的任意两点x,y均有max{d(u),d(v)}≥(n-1)/2|N(u)N(v)|≥n,则G是哈密顿图或1或图2

从我们下面的证明中可知道当把界改进到(n-1)/2最艰难的部分其实就是他们都放弃避开的a(G)=(n+1)/2。因此定理1.6定理1.7都并没有改进范定理

上面是世界各地沿着度型-Fan条件改进式的进展;下面是世界各地沿着度型-Fan型条件推广的工作: 

1993年美国乔治亚州立大学数学与统计系系主任Chen教授得到

定理1.8: 2连通n阶图G的满足1≤|N(x)∩N(y)|≤α-1的任两点xy均有max {d(x),d(y)}≥n/2,G是哈密顿图

显然,上面各国的工作也全都分别被上面赵克文等的定理[1]定理[2]所包含-赵克文的这2个定理也都比他们的好!另外,赵克文等也还从几个方面给出范定理的简单证明等

关于改进发展上面定理1.2(奥勒定理)的方向,七十年代剑桥大学期间写了几本图论书并提出决最小哈密顿圈的当时世界最重要最有效算法Christofides和法国专家Ainouche得到下面定理1.9关于Christofides,如这里为数学教师列出的参考资料中3章“图论”5本书中的4本书Christofides1975年撰写而至今仍为主要参考的用书,第1本是上面英国首相儿子合写的,23都是这里接受我和他合作的图论世界第3大师Chartrand,第5篇是历史上四大数学家之一欧拉-Leonhard Euler的。而1981年获得牛津大学和伦敦大学博士学位的Ahmed Ainouche可能是的哈密顿图专家了如看他的网页见每一篇论文都是哈密顿图的如此他1981年至今才有20多篇论文--Ainouche还是这非洲面积最大国家的数学会杂志编委--因这国家近一百余年一直是法国殖民地如此编委有一半是法国人--足见20多篇论文就有代表性就非常不容易)

定理1.9(Christofides-Ainouche,1985):n阶图G的不相邻的任意两点x,y均有d(x)+d(y)≥n-1,则G是哈密顿图或K*(n+1)/2G(n-1)/2

其后,琼州大学赵克文1991年已完成的、美国南卡罗来纳大学数学系唯一的正教授Rao Li2006年在《信息处理快报》、山西省数学会理事长教授等2007年在《离散应用数学》分别均得到下面结果(李理事长还位居2002年出版的《山西大学百年校史》数学学院4个入选者的第2--西省科协主席侯晋川居他之前-而在他之后的另2个燕居让和毕业于北大的梁展东是该校研究生院原院长都大李理事长十几岁。关于南卡罗来纳大学-它一分校曾提出无爪图领域闪耀世界的著名猜想。关于Rao Li教授,其一直在哈密顿图前沿奋斗-取得很多重要结果,如他和三个大师1987年完成这个非常著名的哈密顿图结果,在这2007年前他的论文全部是哈密顿图的且在美国《数学评论》也见他2007年前刚好发表30篇论文。邻州的北卡罗莱纳大学著名的计算机诺贝尔奖获得者Brooks-也曾对图论有贡献):

定理[3] (赵、李、Li)n阶图G的距离是2的任两点x,y均有d(x)+d(y)≥n-1,则G是哈密顿图或GÎ{G(n-1)/2ÚK-(n+1)/2, Kh:w:Gt}.

其中山西省数学会理事长教授的论文最后说:Jongen教授给予这论文很多详细的评注和建议。一查看知Jongen是大名鼎鼎的理工科很多方面一直名列德国第一的亚琛工业大学大师,这也许缘由这论文是李理事长和这亚琛工业大学2个博士合作的。关于理事长、美国南卡大和我分别得到的上面定理[3],虽然是比剑桥大学Christofides教授和牛津大学伦敦博士Ainouche合作的定理1.9好,但探索的技术已发展到如此丰富了却在人之后20年才发表,还是有点不是滋味。如此我们琼州大学和美国第一大学博士北京大学宋教授合作得到更好得多的上面定理[1]:“n阶图G的距离是2的任意两点x,y均有max{d(x),d(y)}≥(n-1)/2,则G是哈密顿图或图Ж”(这是非常必要的!不是因为定理[3],而是因为上面定理1.6见在巴黎大学培养多个博士的Wojda院士和法国奥大运筹学科创建奠基人Benhocine教授合作在1987年仅非常艰难地解决到a(G)£n/2,又再过10年的1998年的上面定理1.7清华大学2个权威教授、陆所长和江苏省数学会理事长教授3个人合作也仍还是仅解决到a(G)£n/2,可这a(G)算不得名份-却拦截着路-实在很难受。其实,a(G)稍比n/2小点都容易解决,即这个问题的珠穆朗玛峰最高峰是(n+1)/2左右,而只要差一点,难度就有天壤之别!而我们彻底攀上珠穆朗玛峰最高峰。也算结束这么多年来爱好这问题的专家们的尴尬历史吧)

附注1:再多说点涉及定理[3]的事。哈密顿图世界权威-美国南卡大Li教授只是做2连通图而1连通相当于几乎不做,李理事长等也用全篇论文只解决2连通图,而琼大赵克文把2连通图和1连通图全部解决心灵捕手》影片的主角原型兼顾问Kleitman院士的博士-《离散数学》执行主编Goddard教授对这篇编号为“DM 17668”的琼州大学的上面定理[3]论文的原话是the proof is indeed short足见以前哈密顿图非常不容易而显珍贵

附注2哈密顿图之艰难也如2011-2012荷兰排名的世界大学100中居世界第4Rice大学(这里也见它居世界第4大学-即它和哈佛大学普林斯顿大学都同是22分多-而第4名以后都少于22--是有点意外-吃惊-且当时该大学3个最好的研究生专业有数学)的Jennings哈密顿图博士学位论文包括参考文献仅有短短的39-从全文见除去参考文献等更仅有30写成中文也就20多页可否考证是否历史上最短?2003年也在这大学本科毕业,其后因突出而博士论文上也说得到2个国家基金资助他-可他还要再读5年多博士生,象哈佛丘成桐院士半年就获博士,足见哈密顿图非常之难--特别是5年多仅写20多页应是世界绝无仅有的吧)-这论文得到若σ³A(G)-1则有哈密顿路(σ 的定义见第3页,A(G)的定义见第21,第2页说这结果是这论文的主要结果。这个结果的证明在第23页,前面都是为它准备的引理,也就是世界第4大学的这篇39页博士论文仅有一个结果,其也如在美国《数学评论》见他至今仅有一篇论文。关于哈密顿图之也如台湾的从2000-2007年全身心读了7年多博士-若包括之前的2年硕士生则连续攻读9的哈密顿图博士学位论文也才69)。这世界第4大学博士论文的第一导师是八十年代在哈佛大学做博士时已和神一般Erdös宗师合作也独立发表一些哈密顿图论文Richard Stong教授 --Stong教授还曾是哈佛大学助理教授和访问教授--哈密顿图之艰难也如Stong教授至今也仅有30篇研究论文。这Jennings博士论文源于Fajtlowicz院士和学生DeLaVina 2006年的一个猜想,关于的一些猜想见下面再附(顺注:上面南卡大Li教授的博士导师就是哈密顿图大师Schelp教授。这Schelp教授最近就和刚获得阿贝尔奖的大师Endre Szemerédi以及Sárközy教授及国际数学联盟主席Lovász的唯一师弟Lehel教授等考虑图和超图的一些变型哈密顿圈问题(见Cycles in hypergraphsOn the Regularity Method)。阿贝尔奖被公认是数学界的“诺贝尔奖”--至今才有11获得这奖--足见在国际数学界的地位。上面定理[2]简介的诺贝尔奖得主Gowers也介绍Endre Szemerédi工作并在第1页末说“perhaps the  single most important in combinatorics, is the graph—即可能是组合数学中唯一最重要的”。这阿贝尔奖获得者Endre Szemerédi指导的博士生中仅有一人的博士学位论文不是做图论的但此人发表的论文也全是图论的,其中的Yi Zhao博士现在冠涛主任的数学系任副教授,Szemerédi和他的博士Sárközy教授也合作发表多篇正宗哈密顿图问题论文1论文2论文3等,Endre Szemerédi还和János Komlós院士合作发表多篇正宗哈密顿图论文1论文2论文3,他还发表二十多篇与哈密顿图密切的圈及路问题,特别是他们九十年代发表系列解决1994年在国际数学家大会1小时报告的Seymour教授提出的k-th power哈密顿圈问题论文1论文2等。即将举办庆贺Szemerédi院士70岁生日的数学会议就有国际数学联盟主席Lovász陶哲轩GowersFurstenbergAvi等一批获得各类有诺贝尔奖称号大师出席做报告)。在此附一些与上面世界第4大学39哈密顿路图博士论文相关的问题很多专家也已关注之,如DM主编West教授参与合作的这方面论文并认为其中条件为κ(G)≥ t(G)-2的哈密顿路猜想等几个问题值得做

赵克文再突破上面定理[3]到下面深刻进展(关于是的理由见下面②。这挑战的艰难性当然必几乎处处都要挑战极限突破极限才行,而且每走一步都似乎感到无路可走下去--也确实是无路可走,以前的方法技术似乎远远达不到推动它前进一点的作用,也肯定新的方法技术必须是超越突破以前的方法技术的,即如此极限问题的新路的每开一步都只有开在坚硬的大石、在悬崖绝壁边--别再梦想有无捷径,所以其难可能不是几倍于以前的进展。对如此问题如此极限-以前的方法能起的指导程度非常有限-而且就是较空泛的模糊的宏观性的方法论也较缺乏--则就是在坚硬大石上把路开通了也可能不起作用是白白浪费时间去开通(下面所有领域的几十个定理的绝对多数问题都是如此艰巨的,绝对多数我都坚持做到特别极限的进展程度,它们也都是在如此一步一步的极其艰难中一点一点向前推进的):

定理[4] (赵克文等)n阶图G的距离是2的任两点x,y均有d(x)+d(y)≥n-2,则是哈密顿图或GÎ{(G(n-1)/2ÚK-(n+1)/2)-e, G(n-1)/2ÚK-(n+1)/2, G(n-2)/2Ú (K-(n-2)/2K2), G(n-2)/2ÚK-(n+2)/2, G2Ú3K2, G2Ú (2K2K1) }.

下面略解上面定理[4]之难的上下界全部方面理由:①除了上面法英权威的定理1.9--日本这篇6页解决的也是:不相邻2点的d(x)+d(y)≥n-1 且还引用美国Ore、英国Dirac和匈牙利Pósa1966年国际数学奥林匹克竟赛最高分者)这3个大师的三个定理(特别是后二个定理就是在做得专深广博的基础上思索几年也未必开掘搭建到利用它们的道路--日本这篇论文的思想也部分基于这作者和当时正指导诺贝尔奖获得者Bollobás院士合作的这篇论文。而看我们的定理[4]的每一方面对以前方法技术的艰难创新突破程度则它可能又不只比这日本的难上十几倍,确实日本以及上面英法等的方法已几乎不起任何作用);

Köhler只能研究不相邻2点的d(x)+d(y)≥n-3的某些更强结构的非常少的特殊图而稍一般就无能为力无从研究,Jung大师对不相邻2点的d(x)+d(y)≥n-4更是只研究坚韧图,所以定理[4]对全部图都解决可能是最后的好进展最好的刻划-即再向前可能非常难且其进展的例外图也多而杂乱并多少意义。

所以要研究“不相邻2点” d(x)+d(y)≥n-2都已非常困难,而上面定理[4]更研究包含“不相邻2点的”的更非常艰难的“距离是2的任两点”!

如此美国大学教授协会中南区主席、也是有5万学生的全美特大型大学Texas A&M大学(现是全美第6大公立高校-美国私校都很小)的教授协会主席Arthur Hobbs教授看了定理[4]后评价说“I have looked through the paper you went me, and it does look very interesting”。Hobbs授的导师就是上面第一段说到的完成了第二次世界大战情报界最伟大的壮举的图论奠基人William Tutte院士的最正宗的哈密顿图博士(这里2Wolf部分见Tutte院士的哈密顿图结果也名垂青史),Hobbs授和二十世纪伟大数学家Erdös合作的5篇论文也全是哈密顿图的,同时也因Jung大师的上面论文中的10篇参考文献中就有2篇是Hobbs主席如此我才请最权威的Hobbs教授评审

这是非常难得的高评价了,如中国数学最高殿堂-中科院数学院2007年以来的30多个科研进展报告中的其中之一09.04.25发布的评价是“are interesting ,这应是较普通的评价。而我下面定理[11]收到爱因斯坦长期任主编的杂志评价为“quite interesting”。上一段Hobbs主席更说定理[4]very interesting

赵克文Gould主席考虑一个新的极限条件[18],将发表在SCI核心杂志Arkiv Mate(见Gould主席的个人主页)

定理[5] (赵克文等): 2连通n阶图G的两两距离为2的点对均有{|N(x)N(y)|+d(u), |N(w)N(z)|+d(v)}≥n , G是哈密顿图。

赵克文、颜教授、赖教授和周教授等合作考虑max{d(v):vÎS}≥n/2+ss-Hamiltonian graphs

定理[6] (赵克文等): k连通n阶图G的任一含满足1≤|N(x)N(y)|≤α-1的两点x,yk个独立点组成的点集S,若有max{d(v):vÎS}≥n/2+s,Gs-哈密顿图。

 (B).  邻域并型:

欧洲大学之母巴黎大学Pierre Fraisse教授在1986年得到条件|N(S)|≥k(n-1)/(k+1)(关于在巴黎大学理学院基础上重建的这巴黎第11大学的著名的图与优化组合理论中心的哈密顿图权威专家现在还有李皓、Odile FavaronEvelyne Flandrin等,这中心是Jean-Claude Bermond创立的,他现是法国国立计算机及自动化研究院通讯的算法、模拟、组合优化研究所所长并担任过几乎所有图论、组合数学杂志的编委(我也对Bermond的写进图论教材的著名定理给出简单证明),近5届的Fields奖得主中这巴黎11大就有3-普林斯顿大学并列全世界第一(这数学世界第一的大学也只有一个定理被取入图论书)Fraisse的论文虽在1986年发表,但正文第4行说是推广下面1989年发表的邻域并条件。参考文献中注明是参考美国Emory大学数学系1985年已有的预印本,可见Gould主席才是邻域并的主要创立者)

1989Gould主席等得到邻域并条件:

定理1.10:2连通n阶图G的不相邻的任两点x,y均有|N(x)N(y)|≥(2n-1)/3,则G是哈密顿图

1989Lindquester考虑距离是2的情况,得到:

定理1.11:2连通n阶图G的距离是2的任两点x,y均有|N(x)N(y)|≥(2n-1)/3,则G是哈密顿图

1991Bauer范更华校长Veldman等三个国际著名权威把上面的界改进到|N(x)N(y)|≥(2n-2)/3

定理1.12(Bauer范更华,1991[1])2连通n阶图G的不相邻两点x,y均有|N(x)N(y)|≥(2n-2)/3,则G是哈密顿图。

1991赵克文进一步解决:一般图距离2的两点xy|N(x)N(y)|≥(2n-4)/3的哈密顿图性。我的目的不只为推广深化上面Bauer范更华理事长等人的定理1.12,也为解决Bauer等人的这篇论文9无爪图猜想:无爪图不相邻两点xy|N(x)ÈN(y)|≥(2n-4)/3则是哈密顿图。即我们这都解决到同样界≥(2n-4)/3的距离是2一般图了,那无爪图就显得意义小了。此外,我们知道图论的瓶颈段常是阶约9≤n≤99,如此,若不考查整体条件的意义,这瓶颈(2n-4)/3比分母是2时的瓶颈的难度大、其方法的突破就更得新方法--而突破了瓶颈其它部分就算是仍无限多也能常常可推而广之即它们已不是问题了(其实,关于这猜想,我也解决更深刻的无爪图的满足1≤|N(x)N(y)|≤α-1的两点均有 |N(x)N(y)|≥(2n-6)/3的更深远的情况。Bauer等人的这篇论文共提出4个猜想,最著名的猜想是进入这里见我用近一页证明的第1个猜想。这些结果见1993年的首届海南省青年学术年会论文集)

1991《图论杂志》三个编委Faudree校长Lesniak院长和Schelp教授考虑含参数δ的邻域并条件:

定理1.13(Faudree1991[12])2连通n阶图G的不相邻的任意两点x,y均有|N(x)N(y)| ≥n-δ,则G是哈密顿图。

1994宋增民张克民教授改进上面条件:

定理1.14:宋增民,张克民,1994[31] )G是独立数为αk连通n≥3阶图,对图G的任一恰有k+1的点的独立点集S,若存在u,vÎS,使d(u)+d(v)≥n|N(u)N(v)|≥aS中任意两点u,v,均有|N(u)N(v)|≥n-(S),则G是哈密顿图

赵克文Gould主席合作的下面结果改进上面所有邻域并型条件方向的全部结果:

定理[6] (赵克文等):G是独立数为ak连通n≥3阶图,对图G的任一含距离是2的两点的恰有k+1的点的独立点集S,若满足下列条件之一,则G是哈密顿图

(i)存在u,vÎS,使d(u)+d(v)≥n|N(u)N(v)|≥a;

(ii)S中任意两点u,v,均有|N(u)N(v)|≥n-(S) (发表在Colloq. Math。或Gould主席的个人主页)

赵克文和美籍专家赖院长合作的这方向的更深刻结果将被北美SCI杂志Ars Combin.发表(见赖教授的网页

定理[7] (赵克文等):k连通n阶图G的任一含满足1≤|N(x)N(y)|≤α-1的两点x,y均有|N(u)N(v)|≥n-δ-1, G是哈密顿图或几类非哈密顿图。

除了一般图,各类特殊限制图的哈密顿圈性也是国际性的热门课题,下面仅为偶记,因从事这些领域的专家层出不穷数不胜数、其国际最前沿也不断演化博大精深,决非个人能力所及述之。主要有线图-无爪图: 见美赖教授、法Li-Favaron-Flandrin、捷Ryjáček教授、李明楚教授、熊教授等;坚韧图: 田丰教授、Chvátal教授、德Jung、美Bauer主席、美Schmeichel等;正则图: 朱教授、荷英Broersma、美Hobbs、英Jackson、奥Fleischner等;平面图: 哈佛大学Whitney、加Tutte、新澳Holton、丹Thomassen院士、美郁教授二分图也是重要课题但一般二分图的各型充分条件结果能够从一般图推导,还有一类情况是与正则、平面结合在一起但方法较掺杂没有太独立或突出自已如此就不另外举-如平面3正则二分图猜想已走过30年仍悬而未决--它还更是源于这里第2Wolf部分的一百多年前的1884Tait出的错误的哈密顿图猜想--Tait出的62年后才能找到这猜想错误的例证--涉及此猜想者有美国数学协会主席捷克斯洛伐克科学院院长和太空探索的诺贝尔奖获得者-足见这问题重要);凯莱图: Gallian、加Witte (此权威的妻子Morris是年轻的凯莱图博士)、加Alspach、美Locke教授、孟教授等(对任一aÎGa的关联边为(a, ab) for bÎ生成集S,如此若S是对称的则凯莱图|S|正则图,但能自成一统如此单列它。显然凯莱图的任两点都存在相应的自同构,如此凯莱图是下面点可迁图。已知超立方体网络、双环网络、星图等互连网络图不仅是凯莱图也是正则图,但这领域已成一个热门专题队伍也庞大就也单列为--互连网络图: Harary教授、台徐力行教授、徐俊明教授、台陈健辉教授、台謝孫源教授等);随机图: Frieze、澳加Wormald、以Alon、美Sudakov、英Cooper等。这肯定非常不好列举,因每个课题都可列出20个甚至50个做出有世界影响工作的专家,如1983年在东京大学指导出著名哈密顿图博士SaitoEnomoto为代表的日本至少应有20人可列入,特别是日本8090年代等毕业的一批博士经常合作大有长江后浪推前浪很值得尊敬,则此没有列入日本实为遗憾,可能是他们横跨课题多或属于另外课题如Saito教授等多做其它禁子图收缩嵌入特殊点的哈密顿圈等。又如随机图师徒匈牙利Erdös大师和英Bollobás院士是最先两代开拓者-因此他们的文章是必看的而我又感到这些年轻人也做得不错就为了也给年轻人机会吧,此外象Thomassen院士和Broersma等是多面手不只属于一个领域,此排名也与成就大小无关如Alon院士虽比前两者年轻但名气稍大于前者而不排前也许是前两者成就也大且又较专,又澳李才恒教授和上面Morris的博士标题虽一样,但Morris多和他丈夫合作哈密顿图但论文少而硕果累累的是做其它方向,如此各列出几个已是如覆薄冰勉为其难了(哈佛大学丘成桐院士说在美国无人在乎歌德巴赫猜想。但从这段的哈佛大学Whitney的平面图、耶鲁大学Ore院士的一般图和Lovász主席的点可迁图猜想和普林斯顿Seymour主编的kth-power猜想--前一个猜想仍悬而未决进展甚微,后一个猜想被匈牙利院士Komlós和美国科学院院士Szemerédi3人得n充分大是真,如此应可说在美国处处在乎哈密顿图

最后,记录几类图的著名结果和猜想:在1931Whitney的“4连通三角形平面是哈密顿图”,和1956Tutte的“4连通平面是哈密顿图”的基础上1971Nash-Williams提出至今仍悬而未决的猜想4连通torus map是哈密顿图”。1984MatthewsSumner提出也尚未解决的猜想4连通无爪图是哈密顿图1986 Thomassen提出又猜想4连通线图是哈密顿图,已证明后两个猜想等价。

一些极拟哈密顿图如Julius Peter Christian Petersen图也有很重要作用(:Petersen不仅是著名数学家而且是一位出色的名师,当他讲课遇到推理困难时总是说这是显而易见的”,并让学生自己查阅他的著作.他还是一名有经验的作家. 1891年,彼得森发表了一篇奠定他图论历史地位的长达28页的论文。…1898年,彼得森又发表了一篇只有3页的论文,在这篇文章中,为举反例构造了著名的彼得森图)

2节、哈密顿连通性Hamilton连通性):正如1969年获得牛津大学图论博士的J. A. Bondy大师所说的世界闻名的Meta的猜想:即Hamilton图的充分条件都可导出它是泛圈的。而显然,这对许多哈密顿连通性也是适合的,因此,哈密顿连通性是优先要攻克的课题

(A). 度型条件方向:

1963耶鲁大学Ore院士得到:

定理2.1:n阶图G的不相邻的任两点x,y均有d(x)+d(y)≥n+1,则是哈密顿连通图

赵克文下面得到包含和改进Ore院士等大师的距离是2且界是n-1的情况,它还比第1节的多数定理都好: 

定理[8] (赵克文等)n阶图G的距离是2的任两点x,y均有d(x)+d(y)≥n-1,则G是哈密顿连通图或GÎ{Y6, G3(K2K2K2), G(n-1)/2(K-(n-3)/2K2), G(n-1)/2K-(n+1)/2,Gn/2K-n/2, (Gn/2K-n/2)-e}

关于上面这结果,和上面39哈密顿图博士学位论文同从美国Rice大学获得博士的-中国十大杰出青年之扶磊教授的介绍中的第一个杂志-美国著名数学杂志Proceedings of the American Mathematical Society其责任主编就经过送审我的上面结果后给我来信说Your work is clearly worth publishing并经过扩展方向修改其后接受发表(扶磊教授获得十杰时只有12篇论文,就象这里的很不容易

德国首都的最具国际化色彩的柏林工业大学Wei博士哈密顿图权威Jung教授1993年解决d(u)+d(v)+d(w)-|N(u)N(v)N(w)|n+1的哈密顿连通性。

历史上23卓越图论学家之一的美国Faudree校长等在1989年得到

定理2.2(FaudreeGould 1989[12])2连通n阶图G的不相邻的任意两点x,y均有|N(x)N(y)|≥(2n+1)/3,则G是哈密顿连通图。

赵克文J. Sci. Tech.把上面定理2.2的界(2n+1)/3改进到(2n+1)/3,还把它的不相邻的两点推进到距离是2和更深入的1≤|N(x)N(y)|≤α-1的两点:

定理[9] (赵克文等)2连通n阶图G的任一含满足1≤|N(x)N(y)|≤α-1的两点x,y均有|N(x)N(y)|≥(2n-2)/3,则G是哈密顿连通图或几类例外图。

(B).  邻域并条件方向:

最近,赵克文和美国西弗吉尼亚大学研究生院赖院长等在美国顶级一区杂志Computers. Math. Appl.得到更深刻的整数形式:

定理[10] (赵克文等)2连通n阶图G均有{|N(x)N(y)|+d(w): xyÏE(G),d(w,x)=2}≥n,则G是哈密顿连通图或几类例外图。

D. Bauer, H.J Broersma, H.J Veldman, Li Rao李饶考虑任意3独立点度和与连通度的关系情况并最近的1989年得到

定理2.32连通n阶图G均有{d(x)+d(y)+d(w): xyÏE(G),d(w,x)=2}≥n+k,则G是哈密顿图。

赵克文接着考虑任意3独立点度和与连通度的关系的哈密顿连通性情况,得到:

定理[11] (赵克文等)2连通n阶图G均有{d(x)+d(y)+d(w): xyÏE(G),d(w,x)=2}≥n+k,则G是哈密顿连通图或例外图。

数学终身荣誉奖-沃尔夫奖获得者Eilenberg曾说“代数拓扑学的成就往往不是通过往前进、利用已有的方法于新的问题取得的,而常常是回过来,提炼新的、更细致的方法,这些方法对取得进一步结果是不可少的”。我认为这句话对数学以及很多科学都是正确的,上面、特别是下面就是践行他的真言

3节、泛圈性这领域以及下面各领域全都是紧迫的课题是基于Meta猜想(参考宋理事长1991年《南京大学学报》图论专辑最后的“研究问题”说“J. A. Bondy给出Meta的猜想:即Hamilton图的充分条件都可导出它是泛圈的”。这领域海南琼州大学1991年已彻底解决NC结合d课题但世界各地仍其后再做20,这泛圈图之麻烦也如1991年获伊大香槟分校博士的John Clay George教授Abdollah Khodkar教授以及1968年毕业的这里和海南琼州大学同任编委的W. D. Wallis大师等最近撰写《Pancyclic and Bipancyclic Graphs泛圈与偶泛圈图》一书就