下面的工作在这里被评价为“中国图论界(象海南琼州大学)做得这么全面的是少有-要知它的“研究者遍布全国--似席卷全国,这因它是世界人类史上最悠久的悬而未决难题--艰难和伟大更如Cook院士说年复一年,许多无畏的数学家提出了哈密顿圈…最后都被推翻了…”、人类史上十大天才说若解决相关问题“全世界科学家将放假7天来庆祝(下面8节每节主要有度条件和邻域并方向共16领域方向并多年来国家基金唯一说的邻域并8个领域只有海南突破8个欧美最先突破但海南再做到最好-其难见16个方向中的1方向:

哈密顿图综述。引子1: 哈密顿图简称H, 是已有1千多年的世界最悠久特大难题(其艰巨重要就如只排在Erdös之下世界第3大师著作哈密顿图一章就搬出图论之父Tutte:,你们做不到欧拉大声说道,…而且越来越精彩,绽放在密歇根耶鲁即虽做不到但其精彩使佛普林耶鲁等美国每个大学都在乎; 丘成桐大师美国无人在乎陈景润哥德巴赫猜想-说在乎是媒体误导的。而哈密顿图就如若解决全世界科学家将放假七天来庆祝“P vs NP问题3行字是Typical of the NP problems is that of 哈密顿路Problem,它也计算机世界第一问题--最近邀请海南琼州大学去给他30个博士生及其它研究人员做报告的宁院长历经十年9500实证对哈密顿图问题…足见何等艰巨-20多年前我同时开创世界三大数学难题四色问题新纪元和下面进展就尝遍了鱼与熊掌之极端无奈

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

摘要:2005哈密顿圈及圈覆盖理论获得国家三大奖中最难获得的国家自然科学奖(如海南至今仍没有得到此奖且如2000年只有15国家自然科学奖-数学又只给香港).下面综述以中科院权威大师刘振宏老师等在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节后各定理都用约十页才证完--而如获得上面国家自然科学奖的不到半页就证完也非常艰难,也如这里最后段和总理同载入史册的专家一生的论文全都做下面第4点泛圈图中的偶图的一个小问题但也只能做到一点点,其难就象丘成桐说最痛苦的两周-这里见丘成桐的这痛苦工作和博士论文

1哈密顿圈 (问题是最好的老师,如卡拉比猜想造就丘成桐,庞加莱猜想使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舅舅威格纳-Wigner也获得物理诺贝尔奖。再附一点人们通常已知道这哈密顿图大师Dirac在英国、瑞典、法国、美国的大学都任教过,其实还有其它如他和Erdös合作的这篇论文上写Dirac其时是我国第一个数学诺贝尔奖获得者陈省身大师读博士生的汉堡大学的教授):

定理1.1(狄拉克,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或图Ж或图Ю或图Я

赵克文和美国西弗吉尼亚大学研究生院赖院长等在美国SCI杂志《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哈密顿图博士学位论文仅有短短的39pp.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大学教授协会主席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是哈密顿图。

赵克文教授、教授和周教授等合作在Ars Combin.考虑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连通线图是哈密顿图,已证明后两个猜想等价。

2节、哈密顿连通性

(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是哈密顿连通图或几类例外图

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

3节、泛圈图  (这领域海南琼州大学1991年已彻底解决NC结合d课题但世界各地仍其后再做20,这泛圈图之麻烦也如1991年获伊大香槟分校博士的John Clay George教授Abdollah Khodkar教授以及1968年毕业的这里和海南琼州大学同任编委的W. D. Wallis大师等最近撰写《Pancyclic and Bipancyclic Graphs泛圈与偶泛圈图》一书就

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

关于下面各相关领域的几句序言:各类高哈密顿图领域(主要是泛圈图、点泛圈图、边泛圈图、泛连通图、最短路泛圈图等)在二个最重要条件之一邻域并条件的工作在国内最先都是我做出最关键突破的、并是由我最先完成的,从下面综述或说简述各类高哈密顿图的进展领域可见不仅国内、就是全世界也同样只有我最先突破和完成(可看这节或进入这里见海南大学要在1994年发表的泛连通图结果和1995年要发表的泛圈图结果和下节我1995年在《澳大利亚组合数学杂志》发表的点泛圈图猜想。关于这猜想,从下面第4节见1991年的南京大学的大会上它已做为这领域的最关键问题被列为哈密顿图6个猜想之一被在这大会提出呼吁去解决,然而在1998年以前世界各国都没有任何一类高哈密顿图的进展工作。本来我1992年左右已解决)(只有其中的泛圈图的不含最小度情况是由Faudree校长Gould主席等最先研究,但他们的工作离突破还远,虽应感谢他们,但也害得我陷在这艰难的领域付出太多),特别是,对我们中国唯一贫困市的深山区的状况实在是非常无奈和非常遗憾…否则,我在1995年以前本来已可以在泛圈图、点泛圈图、边泛圈图、泛连通图、最短路泛圈图等各个领域都把参数型与非参数型论文全部发表完,这样至少有约二十篇这些领域的将是经典性的、里程碑性的世界开创性论文发表--要是当时有经费及时发表各类高哈密顿图的每个领域的开创性论文必将产生国际重大影响。另外,邻域并不仅是推广以前的各种经典重要条件,它的各种巧妙的变型条件常有意料之外出奇的惊人效果,则也将从而促使各领域各学科进一步向纵深发展)。

上段已说各类哈密顿图的二个最重要条件之一邻域并条件;其实,从下面也看到各类哈密顿图的二个最重要条件之另一条件-度型条件,虽因已有很悠久的历史,当然早就已被开创,但从下面这条件的各领域工作见我也进一步推进到最高峰:

再多说几句我于1995年在《澳大利亚组合数学杂志》发表的点泛圈图猜想。它是邻域并在各类高哈密顿图领域奠基唯一基础工作(主要是1998年以后的各国发表的相关领域方面论文,几乎都是借用我这些方法才取得进展,特别是含参数d的方向更是绝对的唯一途径、必须经过的途径)。这猜想最先是由六个美国权威企图解决:即由这世界最权威中心Faudree校长Schelp大师、Cecil主席还加入其它美国大学的Gould主席、Jacobson院长和八十年代起已任图论杂志编委Lesniak教授试图去解决(Lesniak指导的博士论文是the Theory of Hamiltonian Graphs学生1987年已在这大学获任正教授)(这六个权威八十年代起就一起合作,并常和论文数量居世界前三位的ErdösHararyChartrand大师合作,他们也还有一些著名博士生也偶尔合作),但这六个世界权威解决不了这猜想,其后他们合作在杂志上提出这猜想 |Þ® 因此其后,我国此领域最权威的宋理事长以及他的中国最权威中心也解决不了,才再在1991年的南京大学的全国大会上和在《南京大学学报》上提出来,最终我1995发表上面解决的工作(我也是世界上第一个最先解决这猜想的),可见最先的解决总是要经历长期艰苦的探索的,是不容易的:

关于含参数d的情况:

1991年赵克文已给《中国科学》等投过|N(x)N(y)|≥n-δ的距离是2的泛圈性论文,回海南后海南大学学报》定在1994年第4期发表此结果

定理[12] (赵克文等)2连通n≥6阶图G的任一互不相邻的三点中有距离是2的两点x,y使|N(x)N(y)|+δ≥n,则图是泛圈图或Kn/2,n/2

赵克文1991就已完成最顶峰的这上面定理[12],但世界各国1992年以后仍在前赴后继做到2006年才达到我1991年完成的高度,即单单为了这个定理[12]世界各国许多大学机构花费二十年时间其实,这个问题美国和法国等在更早的1985已开始研究,可见找不到门道再拼搏也很不容易

关于不含参数d的常数型方向:

1991FaudreeGould 等在文[16]得到泛圈图的条件NC≥(2n+5)/3

定理3.3(FaudreeGould 1989[16]2连通n≥19阶图G的不相邻的任两点x,y均有|N(x)N(y)|≥(2n+5)/3,则图是泛圈图

1992年申请人赵克文的硕士学位论文中的泛圈图的条件大约是n≥16|N(x)N(y)|≥2n/3,它在北京召开的中-美图论会议上报告和被论文集收录(Combinatorics, graph theory, algorithms and applications (Beijing, 1993), 233--240, World Sci. Publ., River Edge, NJ, 1994),得到此领域创立者Faudree RJ教授在美国《数学评论》评论它 (96b:05093)

定理[13]  (赵克文等)n≥16|N(x)N(y)|≥2n/3,则G是泛圈图

这里说世界哈密顿图大师的博士、美国著名博士导师卫兵教授等在他们的论文中的22个地方分别仅推进到31312825313131192522312522311931311616313131。可见要把阶n31仅改进到30都需要在上面22个地方中的其中12个地方再做出突破。

定理3.4(卫兵 1998[18])解决2连通n≥31阶图G的泛圈性

在泛圈图的不含参数d的常数型方向,赵克文经过多年研究得到下面大大改进上面世界领导性数学家、美国Faudree校长等人的结果,并也解决3n9的情况(这结果已被颁发诺贝尔奖的瑞典皇家科学院1903年创刊的leading journal世界领导性杂志Arkiv Mate录用)

定理[14] (赵克文等)2连通n≥10阶图G的不相邻的任两点x,y均有|N(x)N(y)|≥(2n-3)/3,则图是泛圈图

定理[14]虽然难度大得多,需要非常多不同的方法等,因此搞的只能是掌握得更多的专精的,但世界各地也历经二十多年攀登定理[14]如此,美国乔治亚州立大学数学与统计系系主任冠涛教授说“献身科学”;我也把这篇论文给世界第9教授审  如此世界各地多长多艰巨的论文都见过的中科院等公认为“数学大师”的教授专门推荐它说“泛圈性作出高水平的工作

(B). 度型条件方向:

1971年哈密顿图权威大师、将其称为图论教父Bondy得到下面里程碑性的泛圈性结果(Bondy介绍中介绍这1研究论文,它就是下面泛圈图定理,也就是这篇,这里见我们琼州大学发展Bondy的这定理)。哈密顿图世界大师Bondy现聘到数学排名世界第一巴黎第六大学

定理3.1(Bondy, 1971[4])2连通n阶图G的不相邻的任意两点x,y均有d(x)+d(y)≥n,则图是泛圈图或Kn/2,n/2

国际组合数学及其应用学会会刊组合数学与计算杂志主编Aldred教授、新西兰数学会主席Holton院士世界第25张克民教授得到:

定理3.2(Aldred,1994[4])2连通n阶图G不相邻的任意两点x,y均有d(x)+d(y)≥n-1,则图是泛圈图或KC(n+1)/2G(n-1)/2 Kn/2,n/2C5

上面结果是哈密顿图权威Aldred主编的所有论文结果中唯一Gould主席2003年出版的世界公认权威的哈密顿图综述文章引用的

如此,赵克文得到改进和包含上面Bondy定理3.1Aldred