下面的工作在这里被某校长评价为“哈密顿图…在国内图论界做得这么全面的是少有的”、宋理事长说“世界上在邻域并做得最好的是海南”等,要知它的“研究者遍布全国--似席卷全国”(下面只列出刘大师说“非常不容易的一般图”的约50个领域/方向的50篇主干论文-而各类特殊图类如无爪图等我也做很多)。这领域是世界人类史上最重大悠久的悬而未决难题--其艰难和伟大更如Cook院士说“年复一年,许多无畏的数学家提出了哈密顿圈…最后都被推翻了…”、人类史上十大天才说若解决相关问题“全世界科学家将放假7天来庆祝”(下面8节每节主要有度条件和邻域并方向共16个领域方向并多年来国家基金唯一说的邻域并8个领域只有海南突破另8个欧美最先突破但海南再做到最好-其难见16个方向中的1方向。也如下面定理[3]见曾在和哈佛/普林斯顿都同是22分的世界前4名大学攻读了5年多的博士论文仅有20多页-可能绝无仅有,在第3节泛圈图看到海南完成后世界各国仍再做20年…,下面也看到海南琼州大学在9节(9个领域)都居于世界领先):
哈密顿图综述。引子1: 哈密顿图简称H图, 是已有一千多年的世界最悠久的特大难题(其艰巨重要就如只排在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教授在研究这问题时就将‘不屈不挠、前进到底’做为战斗口号”。注:旅行商问题就是最小哈密顿圈问题,下面各节就是分别对一般图的哈密顿圈, 哈密顿连通, 泛圈, 点泛圈, 边泛圈, 泛连通等等的综述,这里附若干相关学科专题)
摘要: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节“点泛圈图”中的偶图的一个小问题但也只能做到一点点,其难就象丘成桐说最痛苦的两周-这里见丘成桐的这痛苦工作和博士论文
下面本人50个定理的大多数中的每个都用约十页证明--如其中彻底突破22个瓶颈的泛圈图定理的这篇用约200页证明-并下面仅列出一般图的哈密顿图工作而本人还完成很多各类特殊限制图如象这类无爪图中的哈密顿图论文:
第1节、哈密顿圈 (“问题是最好的老师”,如卡拉比猜想造就丘成桐,庞加莱猜想使Freedman、Smale、瑟斯顿和佩雷尔曼等都获诺贝尔奖,而庞加莱猜想仅有百年«哈密顿图问题则已千年-其难度等等也将…。再看歌猜-丘成桐说美国无人在乎陈景润的‘歌德巴赫猜想’,而这里见不要说美国大量其它大学-就是一直居美国前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的每点x的d(x)≥n/2,则G是哈密顿图
1960年美国耶鲁大学Ore(奥勒)也只凭下面定理1.2就流芳千古:(也见纪录1、纪录2。更非常令人迷惑的是,Ore院士的许多博士门徒都已成了计算机大师,如他既有“现代计算机之父”,又有“计算机之母”,如此我们海南琼州大学的很多论文是从多方面发展这结果到各方面都居于世界领先)
定理1.2(奥勒,1960[25]): 对于顶点个数大于2的图,如果图中任意两点度的和大于或等于顶点总数,那这个图一定是哈密顿图。
曾在普林斯顿大学和爱因斯坦长期共事并共用同一个助手的历史上十大数学天才、大数学家Paul Erdös和斯坦福大学权威Chvátal在1972年得到:
定理1.3(Erdös, Chvátal,1972[8]) :若连通图G的独立数a≤连通度k,则G是哈密顿图。
哈密顿图大师、牛津大学著名博士Bondy(华东理工大学
定理1.4(Bondy,Chvátal,1976[4]):若n阶图G的不相邻两点x,y有d(x)+d(y)≥n,则G和G+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,则G有c圈或图Ж或图Ю或图Я
赵克文和美国西弗吉尼亚大学研究生院赖院长等在美国SCI杂志《Appl.Math.Lett.》非常极致的推广H图型范定理:
定理[2] (赵克文等):k连通n阶图G的任一含满足1≤|N(x)∩N(y)|≤α-1的两点x,y的k个独立点组成的点集S,若有max{d(v):v∈S}≥n/2,则G是哈密顿图。
关于定理[2],它也发展某些国家一些专家的著名工作。下面列出它发展的其中3个定理,即下面定理1.6 、定理1.7、定理1.8
。详细附注如下:1987年Wojda院士和欧洲最古老的著名大学之一的法国奥大的运筹学科创建奠基人Benhocine教授2人合作仅局部推广上面范定理-即得到下面定理1.6 (在全球最著名的“维基”网见波兰历史上200个数学家中就有Wojda院士,在他前面的是1230年出生的世界著名数学家Witelon;“维基”网见中国仅有66个数学家且古代及华侨不少-自然列入的还是较国际化的。Wojda院士的学硕博士都在哥白尼母校-雅盖沃大学攻读,他的导师就是雅盖沃大学最正宗哈密顿图大师Skupień。刚见1971年Wojda院士已和这导师合作发表哈密顿图论文但至今的会议和杂志论文一共才43篇,足见哈密顿图非常不容易;又如这法国 Benhocine教授1977年发表在法国科学院学报的哈密顿图论文就一直有国际影响, 但他至今仅有25篇数学论文且18篇是哈密顿图的--再也可说明难。这两人都是哈密顿图大师,Wojda教授也在巴黎大学和波兰科学院等培养多个博士-当然此网常没有记录很多博士生)(波兰有许多非常利害的数学家--如泛函分析主要开创者Banach-巴拿赫就是最著名的代表之一。曾来信称赞我的工作的哈密顿图大师Béla Bollobás的博士Gowers的博士论文就是用组合方法处理巴拿赫空间问题的并解决巴拿赫的某些重要猜想而引起组合数学界的极大兴趣-即他的“主要成就在于运用组合数学的方法解决了巴拿赫空间理论中的一系列问题”其后获得数学诺贝尔奖-Fields奖,如此以前虽忙但我也算读完整本巴拿赫的世界名著《线性算子理论》-它就是讲Gowers研究的巴拿赫空间及F空间的算子理论--此于书成于20世纪30年代初,其后,Banach空间理论又有很多发展,特别是看本人的这个不动点理论专题网见自1965年Kirk证明了具有正规结构自反的Banach空间具有不动点性质和1966年Opial得到了具有Opial性质的Banach空间具有弱不动点性质后,利用Banach空间几何性研究非扩张类映射的不动点性质的理论得到了迅速发展)
定理1.6
(Wojda等):对a(G)£n/2的n阶图G, 若距离是2的任意两点x,y均有max{d(x),d(y)}≥
(n-1)/2,则G有H圈或例外图
1998年我国清华大学著名专家俞教授等也在某些方面改进上面范定理如下:
定理1.7 (俞教授等): 对a(G)£n/2的n阶图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的任两点x、y均有max
{d(x),d(y)}≥n/2,则G是哈密顿图。
显然,上面各国的工作也全都分别被上面赵克文等的定理[1]、定理[2]所包含-即赵克文的这2个定理也都比他们的好!另外,赵克文等也还从几个方面给出范定理的简单证明等
关于改进发展上面定理1.2(奥勒定理)的方向,七十年代在剑桥大学期间写了几本图论书并提出解决最小哈密顿圈的当时世界最重要最有效算法的Christofides和法国专家Ainouche得到下面定理1.9(关于Christofides,如这里为数学教师列出的参考资料中第3章“图论”的前5本书中的第4本书是Christofides在1975年撰写而至今仍为主要参考的用书,第1本是上面英国首相儿子合写的,第2、3本都是这里接受我和他合作的图论世界第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)/2∨G(n-1)/2
其后,琼州大学赵克文1991年已完成的、美国南卡罗来纳大学数学系唯一的正教授Rao Li在2006年在《信息处理快报》、山西省数学会理事长
定理[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}.
其中山西省数学会理事长
附注1:再多说点涉及定理[3]的事。哈密顿图世界权威-美国南卡大Li教授只是做2连通图而1连通相当于几乎不做,李理事长等也用全篇论文只解决2连通图,而琼大赵克文把2连通图和1连通图全部解决(《心灵捕手》影片的主角原型兼顾问Kleitman院士的博士-《离散数学》执行主编Goddard教授对这篇编号为“DM 17668”的琼州大学的上面定理[3]论文的原话是“the proof is indeed short”),足见以前哈密顿图非常不容易而显珍贵
附注2:哈密顿图之艰难也如2011-2012荷兰排名的世界大学100强中居世界第4名的Rice大学(这里也见它居世界第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教授还曾是哈佛大学助理教授
赵克文再突破上面定理[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)/2∪K2), G(n-2)/2ÚK-(n+2)/2, G2Ú3K2, G2Ú (2K2∪K1) }.
下面略解上面定理[4]之难的上下界全部方面理由:①除了上面法英权威的定理1.9--日本这篇6页解决的也是:不相邻2点的d(x)+d(y)≥n-1 且还引用美国Ore、英国Dirac和匈牙利Pósa(1966年国际数学奥林匹克竟赛最高分者)这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院士的最正宗的哈密顿图博士(这里第2个Wolf奖部分见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是哈密顿图。
赵克文、
定理[6] (赵克文等): k连通n阶图G的任一含满足1≤|N(x)∩N(y)|≤α-1的两点x,y的k个独立点组成的点集S,若有max{d(v):vÎS}≥n/2+s,则G是s-哈密顿图。
(B). 邻域并型:
欧洲大学之母的巴黎大学的Pierre Fraisse教授在1986年得到条件|N(S)|≥k(n-1)/(k+1)(关于在巴黎大学理学院基础上重建的这巴黎第11大学的著名的图与优化组合理论中心的哈密顿图权威专家现在还有李皓、Odile
Favaron和Evelyne
Flandrin等,这中心是Jean-Claude Bermond创立的,他现是法国国立计算机及自动化研究院的通讯的算法、模拟、组合优化研究所所长并担任过几乎所有图论、组合数学杂志的编委(我也对Bermond的写进图论教材的著名定理给出简单证明),近5届的Fields奖得主中这巴黎11大就有3人-和普林斯顿大学并列全世界第一(这数学世界第一的大学也只有一个定理被取入图论书)。Fraisse的论文虽在1986年发表,但正文第4行说是推广下面1989年发表的邻域并条件。参考文献中注明是参考美国Emory大学数学系1985年已有的预印本,可见Gould主席才是邻域并的主要创立者)
1989年Gould主席等得到邻域并条件:
定理1.10:2连通n阶图G的不相邻的任两点x,y均有|N(x)∪N(y)|≥(2n-1)/3,则G是哈密顿图
1989年Lindquester考虑距离是2的情况,得到:
定理1.11:2连通n阶图G的距离是2的任两点x,y均有|N(x)∪N(y)|≥(2n-1)/3,则G是哈密顿图
1991年Bauer、范更华校长和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的两点x、y的|N(x)∪N(y)|≥(2n-4)/3的哈密顿图性。我的目的不只为推广深化上面Bauer和范更华理事长等人的定理1.12,也为解决Bauer等人的这篇论文9页的无爪图猜想:无爪图不相邻两点x、y的|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(Faudree等1991[12]):若2连通n阶图G的不相邻的任意两点x,y均有|N(x)∪N(y)| ≥n-δ,则G是哈密顿图。
定理1.14:宋增民,张克民,1994[31] ):G是独立数为α的k连通n≥3阶图,对图G的任一恰有k+1的点的独立点集S,若存在u,vÎS,使d(u)+d(v)≥n或|N(u)∩N(v)|≥a或对S中任意两点u,v,均有|N(u)∪N(v)|≥n-△(S),则G是哈密顿图
赵克文和Gould主席合作的下面结果改进上面所有邻域并型条件方向的全部结果:
定理[6] (赵克文等):G是独立数为a的k连通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年仍悬而未决--它还更是源于这里第2个Wolf奖部分的一百多年前的1884年Tait提出的错误的哈密顿图猜想--且Tait提出的62年后才能找到这猜想错误的例证--涉及此猜想者有美国数学协会主席、捷克斯洛伐克科学院院长和太空探索的诺贝尔奖获得者等-足见这问题重要);凯莱图: 美Gallian、加Witte (此权威的妻子Morris是年轻的“凯莱图”博士)、加Alspach、美Locke教授、孟教授等(对任一aÎ群G,a的关联边为(a, ab) for bÎ生成集S,如此若S是对称的则凯莱图是|S|正则图,但能自成一统如此单列它。显然凯莱图的任两点都存在相应的自同构,如此凯莱图是下面点可迁图。已知超立方体网络、双环网络、星图等互连网络图不仅是凯莱图也是正则图,但这领域已成一个热门专题队伍也庞大就也单列为--互连网络图: 美Harary教授、台徐力行教授、徐俊明教授、台陈健辉教授、台謝孫源教授等);随机图: 美Frieze、澳加Wormald、以Alon、美Sudakov、英Cooper等。这肯定非常不好列举,因每个课题都可列出20个甚至50个做出有世界影响工作的专家,如1983年在东京大学指导出著名哈密顿图博士Saito的Enomoto为代表的日本至少应有20人可列入,特别是日本80、90年代等毕业的一批博士经常合作大有长江后浪推前浪很值得尊敬,则此没有列入日本实为遗憾,可能是他们横跨课题多或属于另外课题如Saito教授等多做其它禁子图或收缩边嵌入特殊点的哈密顿圈等。又如随机图师徒匈牙利Erdös大师和英Bollobás院士是最先两代开拓者-因此他们的文章是必看的而我又感到这些年轻人也做得不错就为了也给年轻人机会吧,此外象Thomassen院士和Broersma等是多面手不只属于一个领域,此排名也与成就大小无关如Alon院士虽比前两者年轻但名气稍大于前者而不排前也许是前两者成就也大且又较专,又澳李才恒教授和上面Morris的博士标题虽一样,但Morris多和他丈夫合作哈密顿图但论文少而硕果累累的李是做其它方向,如此各列出几个已是如覆薄冰勉为其难了…(哈佛大学丘成桐院士说在美国无人在乎‘歌德巴赫猜想’。但从这段的哈佛大学Whitney的平面图、耶鲁大学Ore院士的一般图和Lovász主席的点可迁图猜想和普林斯顿Seymour主编的kth-power猜想--前一个猜想仍悬而未决进展甚微,后一个猜想被匈牙利院士Komlós和美国科学院院士Szemerédi等3人得n充分大是真,如此应可说在美国处处在乎‘哈密顿图’)
最后,记录几类图的著名结果和猜想:在1931年Whitney的“4连通三角形平面是哈密顿图”,和1956年Tutte的“4连通平面是哈密顿图”的基础上,1971年Nash-Williams提出至今仍悬而未决的猜想“4连通torus map是哈密顿图”。1984年Matthews和Sumner提出也尚未解决的猜想“4连通无爪图是哈密顿图”,1986年 Thomassen提出又猜想“4连通线图是哈密顿图”,已证明后两个猜想等价。
一些极拟哈密顿图如Julius
Peter Christian Petersen图也有很重要作用(注:Petersen不仅是著名数学家而且是一位出色的名师,当他讲课遇到推理困难时总是说“这是显而易见的”,并让学生自己查阅他的著作.他还是一名有经验的作家.
1891年,彼得森发表了一篇奠定他图论历史地位的长达28页的论文。…1898年,彼得森又发表了一篇只有3页的论文,在这篇文章中,为举反例构造了著名的彼得森图)
第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∨(K2∪K2∪K2),
G(n-1)/2∨(K-(n-3)/2∪K2), G(n-1)/2∨K-(n+1)/2,Gn/2∨K-n/2, (Gn/2∨K-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(Faudree,Gould 等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ös、Harary和Chartrand大师合作,他们也还有一些著名博士生也偶尔合作),但这六个世界权威解决不了这猜想,其后他们合作在杂志上提出这猜想 |Þ® 因此其后,我国此领域最权威的宋理事长以及他的中国最权威中心也解决不了,才再在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的常数型方向:
1991年Faudree,Gould 等在文[16]得到泛圈图的条件NC≥(2n+5)/3。
定理3.3(Faudree,Gould 等1989[16]:2连通n≥19阶图G的不相邻的任两点x,y均有|N(x)∪N(y)|≥(2n+5)/3,则图是泛圈图
1992年申请人赵克文的硕士学位论文中的泛圈图的条件大约是“n≥16和|N(x)∪N(y)|≥2n/
定理[13] (赵克文等):“n≥16和|N(x)∪N(y)|≥2n/3,则G是泛圈图”
这里说世界哈密顿图大师的博士、美国著名博士导师卫兵教授等在他们的论文中的22个地方分别仅推进到:31,31,28,25,31,31,31,19,25,22,31,25,22,31,19,31,31,16,16,31,31,31。可见要把阶n从31仅改进到30都需要在上面22个地方中的其中12个地方再做出突破。(这篇论文被2000年的国际图论研讨会录用)。
定理3.4(卫兵 等1998[18])解决2连通n≥31阶图G的泛圈性。
在泛圈图的不含参数d的常数型方向,赵克文经过多年研究得到下面大大改进上面世界领导性数学家、美国Faudree校长等人的结果,并也解决3≤n≤9的情况(这结果已被颁发诺贝尔奖的瑞典皇家科学院1903年创刊的leading journal即世界领导性杂志Arkiv Mate