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

哈密顿图综述。引子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英国数学家Gabriel A. Dirac (狄拉克)开创哈密顿图划时代的下面定理1.1凭这定理1.1就足够光耀千秋彪柄史册( 也见这定理的纪录1纪录2,或见1990已在国际数学家大会做45分钟报告的数学大师Thomassen院士撰写的诺贝尔物理奖得主Paul A. M. Dirac的儿子Gabriel A. Dirac-就是他,即现代哈密顿图之父Gabriel A. Dirac的老爸Paul A. M. 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(Gabriel A. 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泛圈与偶泛圈图》一书就

(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,则图是泛圈图

赵克文的研究生毕业论文的工作之一泛圈图的条件大约是n≥16|N(x)N(y)|≥2n/3,它中美图论会议上报告和被论文集收录,得到此领域创立者Faudree RJ教授在美国《数学评论》评论它 (96b:05093)

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

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

定理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+]2连通n(n10)阶图的δ≥(n+k)/3NC2(2n-3-k)/3,则G是泛圈图

定理[14]定理[14+]虽然难度极大,需要非常多不同的方法等,因此搞的只能是掌握得更多的专精的,但世界各地也历经十年如一日攀登定理[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等的定理3.2且已是最好进展的结果如下

定理[15]  (赵克文等)2连通n阶图G的距离是2的任意两点x,y均有d(x)+d(y)≥n-1,则图是泛圈图或KC(n+1)/2G(n-1)/2 Kn/2,n/2Kn/2,n/2-eC5

         除了一般图,这节也有许多较受重视的相关的特殊图课题,最受关注的有:无含爪(爪是K1,3)及一些特殊子图的图的泛圈性,它们一直受到国内外一些专家重视,如美国Gould主席的几个博士的学位论文就做此。这主要基于1986Thomassen院士4连通无爪图是哈密顿图的著名猜想,因此猜想实在苦恼人如此1993Plummer提出更特殊的猜想:4连通4正则无爪图是哈密顿图,以及1971Bondy教父哈密顿图的充分条件都蕴含图几乎是泛圈图猜测(即至多有某些例外图--2000Brandt Favaron, Ryjacek确实证明每k≥2连通无爪图都存在非泛圈图,然而也有很多专家证明哈密顿性蕴含泛圈性,如1997Faudree校长和Gould主席证明1991Bedrossian的哈密顿性条件“2连通无爪、无P6也具有泛圈性;又如1997GouldPfenderŁuczak证明“3连通无爪、无P7图是泛圈的”-也应是哈密顿图的)。如此,也一般都研究34连通的无含某些特殊子图的图的泛圈性。如1991Shepherd证明3连通{K1,3, N}-free图是泛圈图(NNet即三角形每点恰再连一边)1997Gould和他的博士PfenderŁuczak得到:3连通无爪、无P7图是泛圈图;最近Gould主席的另2个博士FerraraWagnerMorris进一步证明得到:4连通无爪、无P10图是泛圈图或Petersen图的线图,而且若P10换为P9就没有例外图;他的博士Ferrara等人最近也证明:4连通{K1,3, N(i,j,k)}-free图是泛圈图(i+j+k=6而且都非零)Gould主席和他的4个博士最近也证明4连通{K1,3, B(i,j)}-free图是泛圈图(i+j=6而且都非零,N(i,j,0)=B(i,j)。他们2004年证明i+j=43连通时也是泛圈)。陈教授和他等最近考虑的一类限制也值得注意。在此顺便说最近Kaiser Vrána证明:最小度至少是65连通无爪图是哈密顿图,这是一个可喜的进步。West主编的问题网上就收入Gould主席为提出者的这方面的问题

4节、点泛圈性

(A).  度型条件方向:

中科院院长的母校-“欧洲的麻省理工”德国亚琛工业大学Volkmann教授(V郭余宝导师和该校Schiermeyer教授及Randerath教授等得到:

定理4.1(VolkmannSchiermeyer,2002)2连通n阶图G的不相邻的任意两点x,y均有d(x)+d(y)≥n,则图是4-点泛圈图或Kn/2,n/2

赵克文进一步解决到n-1的情况,一并改进泛圈、点泛圈等的所有结果,是这方向世界顶峰的进展:

定理[16] (赵克文等)2连通n≥7阶图G不相邻的任意两点x,y均有d(x)+d(y)≥n-1,则图是4-点泛圈图或H(n-1)/2KC(n+1)/2, Kn/2,n/2, H2:(K1ÈKn-3)之一。

4-cycles是极限或说瓶颈所在而且做到34-cycles才有意义和有深刻认识。因这极部分的cycles问题解决,一般情况就好认识

(我曾把定理[16] 投给科学巨人爱因斯坦长期任主编的下面杂志,得到全世界第一个的数学会-伦敦数学会主席英国皇家学会副会长、牛津大学Hitchin院士给我送来审稿人认为“quite interesting”希望我参考要求修改的来信如下:Dear Dr Zhao,

You sent a few weeks ago a paper to be submitted to Mathematische Annalen(爱因斯坦做了此杂志多年主编).  Although we rarely publish papers in graph theory. The referee has now reported back, he finds the contents of the paper quite interesting

N J Hitchin   

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

1991年在南京大学举办的首届哈密顿图专题讨论会的论文集(即《南京大学学报》27卷图论专辑)的最后一篇是“研究问题”,它是由田丰、张克民教授和宋增民理事长等总结世界各国认为最有兴趣和难度极大的六个猜想和一些问题,这六个猜想中的其中一个猜想被赵克文1991当年中山大学计算机系系主任娄定俊教授几次上来我们五楼的中国第一个组合研究室完全彻底解决,其后发表在澳大利亚的Australas. J. Combin. 12 (1995), 81-91(在2000年以前可见全世界只有我这篇论文是证明这猜想的,它的意义非常重大,因为其后邻域并的所有各类哈密顿图的突破和发展都基于它的证明方法)。赵克文证明的这个泛圈图猜想也是世界领导性数学家Faudree校长提出的:

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

而国内外最早完整发表含参数δ的高哈密顿图的论文是东南大学数学系博士导师林文松1997年发表在《东南大学学报英文版》的论文A generalized neighborhood union condition for pancyclicity. J. Southeast Univ. (English Ed.) 13 (1997), no. 1, 108--112.”的结果“2连通n≥6阶图G的任一互不相邻的三点中有两点x,y使|N(x)ÈN(y)|≥n-δ+1,则图是泛圈图”。

其实,我1991年已解决到界是n-δ的情况:见海南大学学报要发表的结果G的任两点x,y使|N(x)ÈN(y)|≥n-δ,则图是泛圈图或Kn/2,n/2

其后,西安交通大学博士导师王建中院长等只做d=4的情况(见:泛圈图的一个充分条件安徽师大学报-1993:16(1)-14-18);

王校长等又仅做d=5的情况(见:邻域并和点泛圈图,太原机械学院学报-1994:15(4)-286-291);

2000年武汉理工大学理学院院长肖新平在我们发表了5年后也才再证明这猜想(见:Faudree猜想与Hamilton性,武汉理工大学学报-2000:24(2)-138-141)。

赵克文1995年也解决n-δ的点泛圈图(见:吉林大学自然科学学报-

定理[18] (赵克文等)2连通n≥6阶图G的距离是2的任意两点x,y均有|N(x)N(y)|≥n-δ,则图是[5n]点泛圈图

5节、泛连通性

度型条件方向:

1974FaudreeSchelp研究d(x)+d(y)≥n+1的泛连通性,

定理5.1(FaudreeSchelp,1974[13]):n阶图G的不相邻的任意两点x,y均有d(x)+d(y)≥n+1,则G[5n]泛连通图。

1977Williamson得到d(x)+d(y)≥(3n-2)/2的泛连通性,1984年美国North Dakota大学博士蔡小涛在《中国科学》得到:

定理 5.2. nn≥5)阶的不相邻的任意两点u,v均有d(u)+d(v)n,则G[5n]泛连通图或GÎ{{Kn/2,n/2, Hn/2Kcn/2, Hm-2H2Kn-m.}

(关于蔡小涛教授,这里1982年的第三届的该大学学报14个编委中就有这美国North Dakota大学博士蔡小涛教授,第5段最后说该校图论方面的研究在国内处于领先,蔡小涛其后定居美国。这里倒数第3段见叶校长只说Faudree、蔡小涛工作)

其后,琼州大学赵克文得到改进超越蔡小涛教授的最重要的工作并已是做到最好的进展(如蔡小涛教授的上面论文用了十页只解决部分且他不能解决的部分他用这里第5-哈拉里的《图论》九页解决的结果,而赵克文发表在组合图论大师南大校长陈永川院士的南开大学学报的只用1页半就一并解决蔡小涛和哈拉里要共20才解决的问题,而且我这1页半还不引用任何结果

定理[19] (赵克文)n(≥5)阶的距离是2的任意两点u,v均有d(u)+d(v)n,则G[5n]泛连通图或GÎ{Hn/2KCn/2, H2--(Kn-mHm-2)}

  邻域并条件方向:

1998年,美国密西西比大学卫兵教授和开拓我国图论并陈景润的报道同获一等奖的朱永津大师这两代新老领军权威代表人物合作发表:

定理5.3(卫兵,朱永津1998[34])3连通n阶图G不相邻任意两点x,y均有|N(x)ÈN(y)|≥n-δ+1,则G[7n]泛连通图。

卫兵和朱永津教授在这论文中评论“RemarkThe lower bound 7 in Theorems 1 and 2 might be reduced to 6”即“评论:定理1和定理2中的下界7也许能简少降低为6(也就是卫兵和朱永津教授在这论文已解决7至相应的任意长n的路-却长是6的路反而无能为力奇怪吗?而这页所有各节都应如此是小阶是反而困难但全部各节海南琼州大学都在1993年前已彻底解决彻底做到最好

海南琼州大学就在1998年投到解决上面卫兵和朱永津大师问题的论文去我国最权威的《中国科学》杂志(海南文理工农医等任何学科领域在199812月前还没有论文投去《中国科学》,其实在下面见我在1994年以前已投多篇论文去《中国科学》只不过解决的都是外国人提出的问题)这论文已彻底解决这评论遗留的问题并本已通过了《中国科学》的前2次审稿-即前2次审稿人提的一点非实质问题我已回答-否则也不会有第3次送给审稿人征求他的意见-可就是《中国科学》这第3次送给审稿人-编辑部给我来信说审稿人已出国联系不到-卫兵和朱永津老师的这篇论文证明很长而参考文献仅2篇是他的-如此编辑部也难找到合适的替代审稿人(因朱永津大师80年代初就彻底失明这是我国图论界的极大损-卫兵80年代初也是朱永津老师的研究生其后80年代中期去德国攻读博士--因此这第1、第2审者应该是卫兵教授-因别人不太紧密接触进展-主要指世界各国有任何进展等的一般都只会接触卫兵-他真特别很忙而由别人审但这是《中国科学》那为防止对进展出现误判也会告知卫兵教授--并看到卫兵教授已发表大量顶级论文)。其实我1993年前已得到如下彻底性的更好结果:不仅证明卫兵和朱永津老师的猜想而且还更把他俩的不相邻进一步做到距离是2、以及把3连通做到2连通情况如下:

定理[20] (赵克文) 3连通n阶图G不相邻任意两点x,y均有|N(x)ÈN(y)|≥n-δ+1,则G[6n]泛连通图。(《中国科学》1和第2审都已基本没有大问题,但第3审编辑部说审稿人已在国外无法联系【这里第28海南首个我国最权威的《中国科学》杂志的特邀审稿专家-这有些怪似是《中国科学》为补偿-若有任何问题就不亏欠-就不会给我审这以前中国唯一最顶级杂志的稿,多年来很多媒体都报道我是它的海南第一个评审人】其实,我1993年前已做到比这2个定理都更好的下面定理[20]*定理[20]**定理[20]***)。

海南琼州大学彻底解决到距离是2以及[4n]泛连通性等最好进展结果:

定理[20]* (赵克文) 3连通n阶图G距离是2的任意两点x,y均有|N(x)ÈN(y)|≥n-δ+1,则G[6n]泛连通图。(上面2篇卫兵和朱永津老师的,以及海南琼大的条件都是“不相邻任意两点”即距离³2;而现在只考虑其中的距离=2的两点,而若也有同样的效力,显然是惊人的,当然更是比上面2篇论文都更好,就如看到这条件仍保证[6n]泛连通图。当然,其它一些情况下就难如愿)

定理[20] **(赵克文)3 连通n 阶图G 距离是2 的任意两点x,y均有|N(x)ÈN(y)|≥n-δ+1,则G[4n]泛连通图或几类例外图。

定理[20] ***(赵克文)2 连通n 阶图G 距离是2 的任意两点x,y均有|N(x)ÈN(y)|≥n-δ+1,则G[4n]泛连通图或稍多些的例外图。

    当然,我在1994年前已投很多论文到这《中国科学》杂志这里下面论文右上角登记的投稿日期是1994年5月13投到《中国科学》的论文上写出的3个结果确实比上面这篇更有意义得多(右上角只能看清“中”字-还见注明“数”,总之这确实是《中国科学》登记的我投去的数学稿件)

附注:关于这论文作者之一的朱永津大师,见中国科技大学数学科学学院徐俊明主任在这里5页的§2.1的第一段说“1979年召开第一届全国图论大会,成立中国图论学会朱永津研究员任理事长田丰研究员任秘书长,国内大规模研究图论由此开始。朱永津等的主要研究方向是Hamilton问题,他们的研究方向主导并深刻影响着中国的图论研究…”。确实这理事长秘书长对我影响不小,特别是美国赖虹建院长还有当时国际数学教育大学委员会主席做哈密顿图的中山大学计算机系主任娄定俊等权威1990年底几次来我校组合研究室研讨和做报告,以及1990年我去南京市参加全国图论大会暨国际图论专题研讨会并亲身聆听了法国国家科研中心权威和美国权威大师等的哈密顿图报告等等,使我充分确认这不仅是国内主攻方向也是国际上主攀的珠穆朗玛峰需要全身心投入-如此我1985年听导师的报告后就已马上购买代数图论组合数学研究生教材攻读和已开拓的很多领域,我1990年就不得不放弃它们以及我导师的《组合矩阵论》和我们海南最重要学科“极值集合论”以及我1990年也已完全彻底放弃四色问题、图荫度、生成树等等。徐俊明主任所说之权威正如他只在胡森一人之下,而这胡森1989年就在普林斯顿大学获得John MatherWilliam Thurston2个美国科学院院士、诺贝尔奖得主的博士);卫兵教授也曾任中国运筹学会第六届理事会第一副秘书长-不过他也已在美国任教,比他年轻得多的第二副秘书长刘宝碇的博士生都已成了该领域国内顶级专家,秘书长方伟武研究员与华罗庚大师关系密切(并兼中国运筹学会数学规划分会第四届理事长-副理事长都是象李端也是香港城大协理副校长并副理事长戴彧虹刚当选中国运筹学会理事长)。卫兵担任副秘书长的这中国运筹学会第六届理事会的7个工作委员会主任中除了2青年工作委员会主任外的5个各方面主任当时都已是著名专家如张连生教授是上海市运筹学会第一届理事长、另2个主任张忠辅教授、王建方研究员90年代都曾给我们海南琼州大学来信(就是这2个青年主任宋考平和王雷震都在2008以及2013相继担任校长并宋考平最近2015年是中国工程院院士有效候选人);

除了一般图,这节的较受重视的相关的特殊图课题有,特殊限制图中的局部连通图:首先是1984KanetkarRao的局部2连通的结果:

定理 5.4. 如果G是连通、局部2连通无引导子图K1,3,则G是泛连通的当且仅当G3连通的

1987BroersmaVeldman的论文中有下面推广上面定理 5.4的猜想(没有找到上面论文全文,不清清楚是否已出现在上文):

定理 5.5 如果Gn≥4triangular图,G的线图L(G)是泛连通图当且仅当L(G)3连通的。

中科院田丰老师和密西西比大学卫兵教授等解决下面局部连通的泛连通图问题

定理5.6如果G是连通、局部连通无引导子图K1,3,则G是泛连通的当且仅当G3连通的。

   (要弄清楚证明要先弄清楚triangular图、trail, dominating trail(D-trail), spanning trail(S-trail), circuit, S-circuit就是spnning eulerian subgraph,含如此子图的图称为supereulerian超欧拉图

       可仿定理 5.5 考察图GRyjáčekclosure cl(G)等等的关系。

6节、边泛圈性

(A).  度型条件方向:

1993年起跟国际数学教育大学委员会主席D.A Holton等在S. J. Math.得到:

定理6.12连通n阶图G不相邻的任意两点x,y均有d(x)+d(y)≥n+1,则图是泛圈图或G1,G2,

赵克文得到已是世界最好进展的包含张教授等以前很多结果的定理如下:

定理[21-1] (赵克文等)nn≥5)阶的距离是2的任意两点u,v均有d(u)+d(v)n,则G5-边泛圈图或GÎ{{Kn/2,n/2, G=Kn/2,n/2-e, Hn/2Kcn/2, Hm-2H2Kn-m.}

挑战极限确实花时间精力多,有些专家不愿挑战方法的突破和超越,他们对进展总是见好就收或做不出停滞不前是换课题。那我们追求不仅是方法的突破和超越,它使哈密顿性的结构更清楚确定,进而才能够更好地做结构更复杂的各类哈密顿图-即泛圈、泛连通、最短泛圈等--

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

1998年林等在Neighbourhood Unions and Edge-Pancyclicity, Ars Combin.1998,48:81-86得到:

定理6.22连通n阶图G的不相邻的任两点x,y均有|N(x)N(y)|≥n-δ+2,则图是边泛圈图或几类非边泛圈图。

由第5泛连通图这一节的赵克文的定理[20]为主导,可以进一步得到比林教授的定理的两点关系和界等各方面都更好的结果“距离是2的任意两点x,y均有|N(x)ÈN(y)|≥n-δ+1的图是[4n]边泛圈图。只要再考虑没有最简单的[33]边泛圈的例外图类就完全解决这条件的情况。因“距离是2的任意两点x,y”比“不相邻的任意两点x,y”好,而且本条件的界|N(x)ÈN(y)|≥n-δ+1比林文松等的界|N(x)ÈN(y)|≥n-δ+2好。所以,我们得到:

定理[21-2] (赵克文等)2连通n阶图G的距离是2的任意两点x,y均有|N(x)N(y)|≥n-δ+1,则图是边泛圈图或几类非边泛圈图。

7节、最短路径泛圈性(看这里见这方向是台湾学者历经9年率先取得一些进展,因是对岸同胞,对他们9年非常不容易的付出就在这里再多做点介绍

(A).  度型条件方向:

即台湾教授和王有礼院长、张肇明院长洪西进院长合作得到下面定理

定理7.1(詹等 [2]). 若连通n≥4阶图G的最小度d(G)≥(n+2)/2, 则图是最短路泛圈图.

赵克文进一步改进上面定理7. 1

定理[22-1] 若连通n≥4阶图G的的不相邻的任两点x,y均有d(u)+d(v)≥n+2 , 则图是最短路泛圈图或G

台湾教授和王有礼院长、张肇明院长洪西进院长合作在《离散应用数学》也得到下面结果

定理7. 2(詹等[2]).若连通n≥4阶图G的的不相邻的任两点x,y均有d(u)+d(v)≥(3n-2)/2, 则图是最短路泛圈图.

      赵克文又再进一步研究更深入的d(u)≥(n+1)/2得到推广定理7.1的下面定理

定理[22-2].若连通n≥4阶图G的任一点u均有d(u)≥(n+1)/2, 则图G是最短路径泛圈图或Ю

我们也得到

定理[22-3] 若连通n≥4阶图G的的不相邻的任两点x,y均有 d(u)+d(v)≥(3n-3)/2 , 则图是最短路泛圈图.G=x5。其中x55阶图

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

邻域并的课题(即图G的不相邻的任意两点x,y均有|N(x)N(y)|≥n+1最短路泛圈性如何?)还等待研究。不过,从这度型条件的研究情况看,以及比上面各类高哈密顿图的度型推进更复杂看,邻域并课题将更加困难

极集的邻域并:在总结前人工作的基础上,琼州大学继而创立综合、推广度型条件(d(x)+d(y)³n 邻域并条件(|N(x)N(y)|+d³n的新的极型条件-简称 邻域并条件(|N(x)N(y)|+d(w) ³n:

8节、极集-邻域并

定理[23] (赵克文)2连通n≥6阶图G的满足d(x,y)=d(y,w)=2的任意三点都满足|N(x)N(y)|+d(w)n,则图G是泛圈图或Kn/2,n/2

琼州大学赵克文1991创立了极集-邻域并条件|N(x)N(y)|+d(w) ³n,并于1991年研究其泛圈性。后来也研究更深入的d(x,y)d(y,w)=2的泛圈性,再其后还完全解决d(x,y)=d(y,w)=2课题。要知道后2者花费多于前者十倍以上的时间--特别是最后者非常困难(2008林越分来我校的最先几个月我曾请他排版过很多论文-他应存底-其中这第8节用极集-邻域并研究齐次H路、H连通、泛圈、点泛圈、边泛圈、泛连通的有十几篇--好象曾福庚博士也帮我排版这第8节的好几篇。然而,刚见日本在2008年的下面工作仅是我1991年的工作。下面日本2010年的还不错,但我也在90年代已完成此工作,所以条件没有一分钱经费遗憾之至其实琼州大学1991年左右更已考察研究比下面日本的更深远的d(x,y)=2d(x, w)d(y, w)=2,在很多论文中都已提到过。2003我和吴炎院长在应用科学学报更试图解决d(x,y)=d(x, w)=d(y, w)=2的哈密顿性,并提出一个猜想--若这猜想成立-那是非常令人吃惊的-但或离开广州后就感到非常困难-或有反例。大胆提出这猜想是基于我们1991年完成的这篇论文极邻域并的哈密顿性至今也还没有解决,确实,研究上面条件的3个距离中仅一个距离是2的泛圈性情况就已经非常困难--虽然我们1991年已解决的,但日本到2008年仍在做全都没有一个距离是2的情况,显然,我们的这定理[23]也包含推广上面世界大师Bondy1971年得到的里程碑性的定理3.1以及推出上面海南大学要发表的定理[12]。当然我们这定理[23]也包含上面英国Dirac定理1.1美国Ore定理1.2以及包含上面Faudree校长等权威的定理1.10定理1.11定理1.12定理1.13定理1.14。我们创造这极集的条件|N(x)N(y)|+d(w)n的目的主要在用于更深入地探究高哈密顿图:特别是哈密顿连通、点泛圈、边泛圈、泛连通、路径泛圈等的结构和性质等。因迄今为止,刻划这几类高哈密顿图的条件几乎只有度型和邻域并,则研究赵克文条件|N(x)N(y)|+d(w) ³n也等于一并解决度型和邻域并

本来琼州大学在1991年就已可在世界科学史上烙下这一系列工作深深的印迹。但因没有一分钱经费非常遗憾的是:刚见日本东京工业大学博士和曾排名日本第一庆应义塾大学博士和当时排名日本第一早稻田大学博士这3个日本权威专家在最近的2008年合作在AJC2期得到下面定理8.1(要知道日本全世界最勤奋的民族--这也许与战争后遗症使然的危机感有关-如它一定时期内仍深感到亚洲人民讨债、苏联霸占其大幅领土、时时当美国的孙子等-你说这样的国家的民族意识会是怎样的?能躺着睡大觉吗?如此大多都象这个日本科学家一样,不成功便成仁-既有宁愿以死谢罪的骨气,还有什么做不成,怎能不领先世界再看看中国的学术界,其结果是正如北京大学校务委员会副主任饶毅所说“单个日本科学家的论文可以超我国同一领域全体中国科学家”,这样的被鞭策意识必发挥出比别国更大的能量,如此要重视这几个日本图论专家的眼光和选题。然而,这结果我早在1991年已独立完成--就是这里我们海南大学学报1994年要发表的结果而且海南大学学报要发表的还研究到距离是2的进一步的课题,因此实质上比这3个日本专家的定理8.1更深入更难--但因没有一分钱经费、月工资也仅几百元而非常。这东京工业大学Michio Sugeno1974年就创立后来被名为Sugeno模糊测度和模糊积分的著名博士学位论文-见下面第10节我们数学系俞峰的博士论文也做相关的研究。这Michio Sugeno(菅野道夫)1940 1965年起到2000年退休前一直在这大学工作,现是这大学退休教授也偶尔在西班牙工作,曾是日本模糊理论与系统学会和国际模糊系统联合会主席,他和模糊数学之父Zadeh共同获得首届IEEE模糊系统先锋奖-2000年,虽不能和后者比但也足见利害)

定理8.1 (日本3个专家,2008)2连通n≥6阶图G的不相邻的任意三点xyw都满足|N(x)N(y)|+d(w)≥n,则图G是泛圈图或GÎKn/2,n/2,

3个日本专家中第1作者博士毕业于东京工业大学现是诞生诺贝尔物理奖的芝浦工业大学教授,特别是第23作者八、九十年代多次和巴黎大学及美国等合作。

我也刚看到这3个日本专家最近的2010年又在AJC,47另一篇论文中得到下面定理8.2(比日本的这定理好的上面琼州大学的定理[20]已说《中国科学》1999年已三审我的论文-其实我在此之前几年已完成。而且,我的这定理[20]条件更好:研究到xy的距离是2,而这三个日本专家现在才仅做到xy不相邻;我的论文结论也更好:我研究到4-泛连通图,而这三个日本专家仅做到5-泛连通图。我条件或结论之一就更艰难得,一般专家是不敢做的。即可别想得简单,如这领域美国密西西比大学研究生部主席卫兵教授和世界级领军权威朱永津1998年合作仅做到6-泛连通图 如此他们提出猜想“G5-泛连通图?”。而我们都知道小圈和短路结构段是最艰难的瓶颈所在,即大圈或长路结构时常是较显然的,如此,他们的工作相比我1992年和1995年发表的工作,难说得上突破。而迄今为止除了琼州大学的工作外,全世界最好的论文确实只有密西西比大学研究生部主席卫兵教授这篇和日本的这2篇,其它的进展是非常艰难的如以我国的为例象教育部数学和力学委员会副主任的这篇泛圈图的、以及这里我国多个大学对这里一个简单问题都做了20的,就足见邻域并|N(x)N(y)|+d(w)多艰难?这是为什么这么多年进展如此之缓慢?!?

定理8.2 (日本3个专家,2010)2连通n≥6阶图G的不相邻的任意三点xyw都满足|N(x)N(y)|+d(w)n+1,则图G5-泛连通图或几类例外图

海南琼州大学还得到下面比包括日本3个专家的上面2个定理以及其他国家专家的更深刻的下面结果(众所周知,下面d(x,y)=2将有非常多地方是3个日本专家的无法触及的,其难度甚至是根本不可解):

定理[24] (赵克文)2连通n≥6阶图G的满足d(x,y)=2的任意三点都满足|N(x)N(y)|+d(w)n,则图G4-点泛圈图或GÎ{Kn/2,n/2, Gh: (K1Kn-h-1) for h=2,3}

定理[25] (赵克文)2连通n≥6阶图G的满足d(x,w)=2的任意三点都满足|N(x)N(y)|+d(w)n+1,则图G4-泛连通图或几类例外图

定理[26] (赵克文)2连通n≥6阶图G的满足d(y,w)=2的任意三点都满足|N(x)N(y)|+d(w)n+1,则图G5-边泛圈图或GÎ{v(i;d)i£(n+1)/2; 2£id£(n-1)/2:G(n-1)/2K-(n+1)/2-i,}

显然{v(i;d)i£(n+1)/2; 2£id£(n-1)/2:G(n-1)/2K-(n+1)/2-i,}和图1及图2的交为空.  其中G(n-1)/2表示(n-1)/2阶图, K-(n+1)/2-i表示(n+1)/2-i阶空图, G(n-1)/2K-(n+1)/2-i表示前部分图G(n-1)/2K-(n+1)/2-i的联图, v2£d£(n-1)/2:G(n-1)/2K-(n+1)/2-i表示不在G(n-1)/2K-(n+1)/2-i中的第i个点和G(n-1)/2d个点相邻, 而且这样的i个的邻域不交。

关于上面几个研究方向,它们在很多理论学科和工程技术领域都有重要应用,比如它们已成为当今计算机科学研究热点的网络可靠性和并行处理系统中的可容错技术方面的主要研究内容。并行处理系统中的可容错技术是指在互连网络中某些处理器发生故障的情形下仍能保证网络中无故障的处理器之间进行可靠的信息传送(可靠是指通信路径上的处理器或连接是无故障的,容错度指一个互连网络中能保证任意两个无故障处理器间进行可靠信息传送所容纳的最大故障处理器数)

设计和选择一个互连网络的拓扑结构时,高可靠性、高容错度是评估网络性能的重要概念。互连网络作为并行处理系统的主干,其容错性能的高低用容错度来衡量,容错度越高,容错性能越好。我们从网络的拓扑结构上考虑硬件故障对网络可靠性的影响,即在网络结点和或连线可能发生故障的情况下的数据传输的可靠性.在这种意义下,我们所说的网络容错性是指该网络能容忍多少组件和或连线同时发生故障,剩余的子网络中仍然含有某些特殊结构并仍能正常工作。因此高可靠性、高容错度的互连网络一直是网络设计者追求的重要目标之一,故考虑网络的容错性具有实际意义. 而专家们通常主要考虑的网络容错性是网络的容错哈密顿性、哈密顿连通性、泛圈性、点边泛圈性、泛连通性,最近也已有一些论文研究容错最短路径泛圈性。

从上面8节见这就是为什么我们的课题一直主要就放在这几类一般图的图结构,也因一般图涉及的是更广泛的课题,即因其方法理论等不只局限于互连网络图。当然除了上面8节我们也考虑相关的下面圈结构稍弱的更多图类

9节、国际数学联盟秘书长的Hypo-Hamiltonian、以及全美国最聪明的天才儿童在哈佛大学和麻省理工相继读硕博士期间提出的k-ordered哈密顿性、控制圈、齐次可迹、最长圈、G圈、S点集-可圈、k点数-可圈、cycle extendabilityS-pancyclableset-pancyclic subpancyclic3→c,还应有gn, gck-semipancyclick-path HamiltonianS-locally pancyclicpan-k-linked graphsk不交圈F-哈密顿图(F是独立边集) G×K2Prism 哈密顿性、无爪哈密顿图等(这些图类主要属于上面几节的各类主干经典图类的拓展变型的支干图类,里是这方面与哈密顿图有关的若干专题

1963年耶鲁大学Ore院士得到条件

定理9.1(Ore,1963[25]):n阶图G的不相邻的任意两点x,y均有d(x)+d(y)≥n-1,则G有哈密顿路。   可参考美国工程院院士Neil James Alexander Sloane1969年在J. Combinatorial Theory论文Hamiltonian cycles in a graph of degree 4

日本Yamashita“On degree sum conditions for long cycles and cycles through specified vertices”得到:

定理9.2(Yamashita [29]):n阶图G均有s2k(G)+1(G)≥n,则G有哈密顿圈。

Goddard2004年的“Minimum degree conditions for cycles including specified sets of vertices”得到(见PDF):

定理9.3: n阶图Gd≥(n+1)/2,则Gset-泛圈的。

Goddard在上面论文中说Hendry在这论文Extending cycles in graphs中证明下面定理(找不到Hendry的这篇论文全文):

定理9.4: n阶图G的不相邻的任意两点x,y均有d(x)+d(y)≥(3n-3)/2,则Gset-泛圈的(它是上面Goddard的论文的定理5

    Hendry定理9.4的界(定理5)和下面我的定理[31] 都同是(3n-3)/2(我不认为我的定理[31]有意义,但Hendry的这定理9.4有意义,那我的应该同等

我刚看到我读研究生时还没有出现过而近年由Gould主席、我师弟的博士导师Kostochka 教授和《图论》《siam.JDM》编委Ken教授和他们的部分博士生等研究的pan-k-linked 问题(用“linked graph”MR搜索仅见十几篇论文,此课题最早工作是Béla Bollobás院士等的这篇论文,其后这方面的论文几乎就是前面他们三人及和他们的博士生合作的,主要有论文1--PDF论文2--PDF论文3--PDF。此外也零星有其它人的一、二篇)

Polický 1995年在A sufficient condition for Hamiltonian graphs. Math. Slovaca  (1995), 45卷第2到:

定理9.5: n阶图G的不相邻的任意两点x,y均有d(x)+d(y)+max{w(x,y), w(y,x)}≥n,则G有哈密顿圈。

2005Mohammad Kaykobad院士和伦敦大学Mohammad Sohel Rahman博士得到

定理9.6(Kaykobad,2005[26]):n阶图G的不相邻的任意两点x,y均有d(x)+d(y)+d(x,y)≥n+1,则G有哈密顿路

赵克文1991年就得到比Kaykobad院士等的定理9.6远远的好得多的下面结果;

定理[27] (赵克文): n阶图G的不相邻的任意两点x,y均有d(x)+d(y)+d(x,y)≥n-1,则G有哈密顿路或Ж。

其实,从第一节中的我们的定理[4]还可类似得到比上面定理[27]好的定理:“n阶图G的距离是2的任意两点x,y均有d(x)+d(y)≥n-3,则G有哈密顿路或Ж”,这定理比Kaykobad院士等的定理6.2远远地好得多

最近这伦敦大学Mohammad Sohel Rahman博士和Kaykobad院士及Mohammad Saifur RahmanInternational Society for Computers and Their Applications国际计算机及其应用学会主办、美国路易斯安那州举办的20th International Conference on Computers and Their Applications20届计算机及其应用国际会议的论文A New Sufficient Condition of Hamiltonian Path又得到:

定理9.7(Rahman,2005[28]):n阶图G的不相邻的任意3u,v,w均有d(x)+d(y)+d(w)≥(3n-5)/2,则G有哈密顿路

看上面1节的定理[4]赵克文1991已解决G的距离是2的任两点x,y均有d(x)+d(y)≥n-2的哈密顿图,即我们不仅解决哈密顿路还解决包含哈密顿路的更重要的哈密顿圈,比这伦敦大学Rahman博士等的定理9.6深远得多(当d(x)+d(y)+d(w)≥(3n-5)/2时,也就至多有一、二对点可能例行这条件。若有例外,其它点密度就更大,这反而更充分。其实,他们的推广已是有些陈旧和滞后,当然提供的解决方法等还是有值得参考的地方。只有考虑它的哈密顿图或d(x,y)=d(w,x)=d(y,w)=2 变型其结果才算有些意义

1989Lindquester提出猜想:“NC2≥(n-1)/2则有哈密顿路 J. Graph Theory 13 (1989), no. 3, 335—352)。云南大学李建平院长和田丰老师合作的论文1996年证明此猜想(李建平教授1983年从中国科技大学毕业后跟中科院系统所蔡茂诚和田丰老师做“哈密顿图的与邻域并有关的两个猜想的证明”硕士学位工作,后获得巴黎大学哈密顿图博士学位。现负责云南大学数学学院已有的2个博士点建成国家数学一级学科博士授权点的申报工作)

赵克文在《应用科学学报》得到进一步的结果;

定理[28] (赵克文等)2连通n阶图G均有{|N(x)N(y)|+d(w): d(x,y)=d(y,w)=2}≥n-1,G有哈密顿路。

赵克文也考虑最短路泛圈图的邻域并课题,推广Chan的结果如下:

定理[29] (赵克文):n阶图G不相邻的任意两点x,y均有|N(x)N(y)|≥n-δ+1,则G最短路泛圈图或Y

我们也基于Linda Lesniak1973年发表在JCTb的著名哈密顿连通性论文等得到下面结果(因Lesniak教授一直是美国密苏里数学杂志12个编委之一如此我们这篇论文被它录用

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

1977年在二十世纪最伟大的数学家Erdös当时主编的Period. Math. Hungar.杂志发表下面结果,并说这最好的条件

定理9.5(1977[26]): n阶图G的不相邻的任意两点x,y均有d(x)+d(y)≥(3n-2)/2,则G是泛连通图

此君1973年以标题为On Hamilton-Connected Graphs(即哈密顿连通图)的著名博士论文获得前5名世界图论大师的博士

这结果并不大但论文却是被引用最多的图论论文之一,然而这么多年竟没有人发现这不是最好条件如此我给Period. Math. Hungar.杂志编委Lajos Soukup 教授投下面我改进这条件的定理[31] (我投稿是DAM执行主编Goddard肯定上面Hendry定理9.4(3n-3)/2有意义),他请专家花了15月审了我的这结果后说“The referee think the result of the present paper is worth to distribute by arxiv”,它说值得由arxiv distribute,那是说原断言错误吧,而我的是正确的。按说断言条件是最好仅举个更大界的例不成立就行!因此断言一般是百分之百不会断言错的!这论文这结果至今也无多大interests我不计较,我感兴趣的仅是为澄清这有趣的著名论文也应算得是著名历史遗案吧?如此我把上面定理的(3n-2)/2改进而得到下面定理的(3n-3)/2--才是最好的条件

定理[31] (赵克文): n阶图G的不相邻的任意两点x,y均有d(x)+d(y)≥(3n-3)/2,则G是泛连通图

在与这定理[31]相关的工作 赵克文还有很多精彩的论文      Tibor Szele1943年证明n阶完全竟赛图至少有n!/(2n-1)条哈密顿路

纽约州立大学宾汉姆顿大学Kronk教授1969年在PAMSJCT分别得到下面结果:

定理9.8 (Kronk, 1969): n2-连通G的不相邻的任意点x均有d(x)≥(n+k)/2,则Gk-path哈密顿图

定理9.9 (Kronk, 1969): n2-连通G的不相邻的任意两点x,y均有d(x)+d(y)≥n+k,则Gk-path哈密顿图

前人已做了一些不相邻”,我下面主要研究更为艰难的“距离为2。我的下面十余个结果主要是利用我读研究生时的八十年代末国际上诞生的最热门条件去推广上面两个定理等, 有些课题难度大极其艰难(如我们已成功用在推广k-哈密顿图的某些著名条件也用以推广k-path哈密顿图但似不太行

定理[32] (赵克文): n2-连通图G的距离为2的任意两点x,y均有d(x)+d(y)≥n+k-1,则Gk-path可迹的

定理[33] (赵克文): n2-连通图G的距离为2的任意两点x,y均有d(x)+d(y)≥n+k,则Gk-path哈密顿图

定理[34] (赵克文): n2-连通图G的距离为2的任意两点x,y均有d(x)+d(y)≥n+k+1,则Gk-path哈密顿连通的

k-path可迹只考察不相邻两点的情况,解决就较容易。但若考察处处要求距离是2”的两点的情况,大多数不相邻之处都不是距离是2”,而且因k-path结构的不确定性使判别不相邻是否也是距离是2”非常困难(就是k-path结构确定也非常不容易判断),如此这多数情况还必另开道路而且有时是非常艰难的路(进入这个网我以其中一个定理为例就可看到上何止百倍,即仅以篇幅衡量难度是不够的。当然距离是2”的难是与不相邻相对而言),其中不少是长年累月地钻到头痛昏沉也仍毫无半点进展(如1984Faudree校长等很容易就解决不相邻界是(n-1)/2可迹,其后在他们身边的Lindquerster企图解决距离是2 的同样界(n-1)/2下是否可迹?但不能解决而于1989提出猜想。再其后,哈密顿图世界权威专家Bauer1991在他们的这篇论文中也不能解决而再提出这距离是2”猜想!所以,距离是2”是对不相邻的推广但这推广在某些形式下的跨进并不象表面形式的推广那么单纯即其跨进是非常艰难的深刻的)

定理[35] (赵克文): n2-连通G的不相邻的任意两点x,y均有|N(x)N(y)|≥(n-1)/2+k,则Gk-path可迹的或例外图

定理[36] (赵克文): n2-连通图G的距离为2的任意两点x,y均有|N(x)N(y)|≥(n-1)/2+k,则Gk可迹的(k=0时就是解决前一段中的猜想

问题[37] (赵克文): n2-连通图G的距离为2的任意两点x,y均有2|N(x)N(y)|≥n-δ+k,则G的几类非k-path哈密顿图的结构如何?(这定理一定出乎世界各国每一个图论专家的意料我想每一个相关图论专家在20多年前创立此条件的哈密顿图结果起这二十多年来必定会认为全部图G都是k-path哈密顿图。然而,看这里最后一篇它的证明见不只存在一个k-path哈密顿图,而且还是有好几类!)。这也深入知道“邻域并”条件对“度和”条件的深入和拓展程度以及在哪些方面对图结构的决定性比度和条件关键和紧密

三个毕业于美国密歇根州立大学不久又得机会分到同一个大学的ChartrandKapoorLick1970年并提出研究n-Hamiltonian graphs

为此,我们下面填补这美国几个权威等遗留的空白课题领域-研究各型著名条件的k-可迹性、k-哈密顿图和k-哈密顿连通性等:

(我也刚看到南非最重要团队k-可迹图的相关问题:即Frick和他的已成为博士导师的学生Bullock教授以及上面第4郭余宝教授的师兄Dankelmann和曾任图论界SCI杂志Util Math实际主编Henning教授和著名博士导师Oellermann等六个世界哈密顿图权威在2011发表论文“Hamiltonicity of k-Traceable Graphs--k-可迹图一般不是哈密顿顿图如此它研究什么情况下是哈密顿的而H(k)和最长圈长又是多少?这问题也是启发于上面国际数学联盟秘书长的Hypo-traceable--也算是好课题,都是多年继承和发展的基础上的产物。有分量的问题还有:如它又在怎样情况下有进一步的泛圈性以及k-哈密顿图的泛圈性等也是同样分量和困难一些的问题。k-可迹图的定义也还可做一些调整使问题更一般化、适合性更强更普遍化。除了k-可迹图、k-哈密顿图等,类似问题有:在我做的k-path可迹图的基础上的这类提问也是同样分量的课题)

定理[38] (赵克文): n2-连通图G的不相邻的任意两点x,y均有|N(x)N(y)|≥n+k,则Gk-哈密顿图

定理[39] (赵克文): n2-连通图G的不相邻的任意两点x,y均有|N(x)N(y)|≥n+k-1,则Gk-可迹的

定理[40] (赵克文): n2-连通图G的不相邻的任意两点x,y均有|N(x)N(y)|≥(n-1)/2+k,则Gk-可迹的

定理[41] (赵克文): n2-连通图G的距离为2的任意两点x,y均有|N(x)N(y)|≥(n-1)/2+k,则Gk-可迹的或例外图(k=0时就是解决前一段中的猜想

问题[42] (赵克文): n2-连通图G的距离为2的任意两点x,y均有2|N(x)N(y)|+ d(x)+d(y)≥2n-1+k,则G的非k-哈密顿图的结构如何?(只构思论证轮廓和完成部分认为关键的主体结论的证明)

定理[43] (赵克文): n2-连通图G的不相邻的任意两点x,y均有|N(x)N(y)|≥n+k+1,则Gk-哈密顿连通的

猜想 (赵克文等) n阶图GNC+δ+kn,则GPrism 哈密顿的。

Gould主席1991年的综述文章说:欧洲大学之母法国巴黎第11大学的两个权威FlandrinHao Li (李皓)1988年在巴黎第11大学举办的406号报告得到d(x)+d(y)+d(z)≥4n/3+|N(x)N(y)N(z)|则其图是哈密顿图(近5届的数学诺贝尔奖-Fields奖得主中这巴黎第11大学就有3-名列全世界第一。巴黎第11大学也称巴黎南大学--是在原巴黎大学理学院的基础上发展的大学,今年在法国大学中排名第1);其后,1991在前两个权威基础上再加入德国首都的柏林工业大学权威Jung教授得到把界降低到d(x)+d(y)+d(z)≥n+|N(x)N(y)N(z)|则其图是哈密顿图;再其后,1996又在巴黎第11大学2个权威的基础上再加入Favaron南京信息工程大学党委书记刘一平、中科院田丰所长、东南大学数学系最高奖项1996教育部科技三等奖得主吴正声教授这六个权威共同合作这条件的下面定理[35] Scyclable;如此,也值得考察这条件的更更艰难k-path哈密顿路,至少是能考察k-哈密顿性以及+1k-哈密顿连通性的这也是对巴黎大学等工作的有意义气的推广(相当于考察网络的容错性)

博士论文是哈密顿图的前辈大师Walther的博士Harant和他一个和国际数学奥林匹克19871989满分同名的学生Frank Göring(见早六年获得博士的同胞Zuther只把他列入图论学家网或EJC上的组合学人)及另一学生Gerlach的论文“On cycles through specified vertices”得到:

定理9.10(GerlachGöring -Harant-Tkac): GSÍV(G)|S|=k(S)+2≥6,若S1-坚韧的,则S是独立集或Scyclable;若S2-坚韧的,则Scyclable

给我来信的剑桥大学Béla Bollobás院士英国权威Graham Brightwell教授在“Cycles through specified vertices”得到(日本东京大学博士并已是东京数学杂志编委的Katsuhiro Ota在论文“Cycles through prescribed vertices with large degree sum”也得到类似结果):

定理9.11(BollobásBrightwell,1993[29]): n≥3阶图Gd(x)+d(y)n/2 for 任意2个不相邻点x,yÎSÍV(G), |S|≥3, Scyclable

其后,有很多深化工作,如: a(S)≤k(G)(Fournier,1985) a(S)≤k(S), s3(S)≥n+min{k(S),d(S)} ( Broersma et al. 1997Ozeki, Yameshita, 2008) s4(S)≥n+2a(S)-2 s4(S)≥n+a(S)+ k(S)-1 s2k(S)+1(S)≥n无爪、正则和二分图等图类也有许多研究

如:法国三个专家Abderrezzak, Flandrin, Amar研究二分图并在论文“Cyclability and pancyclability in bipartite graphs”得到:

定理9.12(Abderrezzak, Flandrin, Amar): 若阶为2n≥62连通平衡二分图G=(XY, E)d(x)+d(y)≥n+1 for 任意2个不相邻点xÎSÍX, yÎY ,  Scyclable

其中,赵克文得到推广上面英国la BollobásGraham Brightwell(他俩是历史上26卓越图论家之二 )等的结果以及其它相关方向的进展如下:

定理[44] (赵克文): n≥3阶图GNC2(S)+dG(u)≥n for 任意2个不相邻点x,yÎSÍV(G), |S|≥3, Scyclable

   我们也得到此条件的更加艰难的S-locally pancyclic图性

定理[45] (赵克文): n≥3阶图GNC2(S)+dG(u)≥n for 任意2个不相邻点x,yÎSÍV(G), |S|≥3, GS-locally pancyclic or |S|=4, G[S]=k2,2 的一例外图

定理[46] (赵克文): n≥3阶图Gd(x)+d(y)≥ |N(x)N(y)N(w)| for 任意路xwy和不相邻点x,yÎSÍV(G), |S|≥3, Scyclable

        1992Häggkvist教授在Twente大学的哈密顿图会议提出度和条件d(x)+d(y)≥n-k三个猜想-下面猜想是第一个:

猜想:若含k -因子的2-连通n阶图G的不相邻的任意两点x,y均有d(x)+d(y)≥n-k,则G是哈密顿图。

1995年美国Faudree校长和英国有16诺贝尔奖获得者的LSE的数学系主任Heuvel教授证明推广上面猜想的下面结果:

定理若含k -因子的2-连通n阶图G的不相邻的任意3x,y,z均有d(x)+d(y)+d(z)≥3(n-k)/2,则G是哈密顿图或一类例外图

我们因此提出邻域并条件|N(x)N(y)|≥n-k相应的下面猜想(另二个的相应猜想也是合理的-即也可有相应的另二个猜想):

猜想 (赵克文等):若含k -因子的2-连通n阶图G的不相邻的任意两点x,y均有|N(x)N(y)|≥n-k,则G是哈密顿图(按Faudree校长等证明也不算简单则也可能有例外图

下面是原北京大学分校校长-现陕西理工大学校长教授的泛圈图著名定理:

定理9.13. Gn阶哈密顿图,如果存在一点x以及和x不相邻的任意y均有d(x)+d(y)n,则G是泛圈图或G=Kn/2,n/2.

一般而言,和前面比较这一节的图结构不算太复杂,有些问题虽然也很困难但只要努力一般都能解决。然而,象前8节中的6节的某些泛圈性问题才是对长期压力的挑战和考验,才较符合美国麻省理工学院要求的不做只要努力一定能成功的课题”

10节、平面图、正则图、线图、随机图、竟赛图、一般有向图的哈密顿性-以及模糊图论(如刚见影响因子1.130SpringerPlus发表的这篇模糊哈密顿图论文“A new algorithm to find fuzzy Hamilton cycle in a fuzzy network using adjacency matrix and minimum vertex degree”就引用一些图论大师和我们海南琼州大学的哈密顿图论文。即,可把上面结果推广到带权图以及已是模糊数学重要领域的模糊图--1999年以前模糊图的论文全世界每年至多三十篇如此可查到迄今中国只有牛院士-四川大学校长刘应明院士和琼州大学赵克文2在欧洲数学会的《数学文摘》评论这模糊图论学科--当然我仅是后来者。这节的第3段见我们琼州大学数学系俞峰博士后也做模糊数学,它的基本是Lotfi A. Zadeh1965年提出的模糊集--集合X[0, 1]的一个映射,换句话映射体现集合中对象(抽象为图的)的模糊程度或隶属关系(用的权从01表示),因此,模糊集就是点权≤1带权图,如此现在已有非常广泛应用的Lotfi A. Zadeh模糊集并不是什么新东西(当然不管是前人的带权图还是下面的模糊图,就使是已蕴含模糊集概念,但也属他正式提出,归于他善于提取归纳和发展--确实Zadeh博士论文Time Varying Networks,而他提出模糊集前也还发表多篇Variable Networks论文,也许就是在研究各类网络的基础上才积累到质的感悟-而各种网络最共性的就是我们图论的图),其实,带权图在许多方面比它更丰富、意义更深远--如它还蕴含模糊集没有的点对的隶属关系、它还超出考察隶属关系或应说程度等等当然它的应用不象模糊数学那么直接--因此发展它的应用一般多数就已不属于带权图了:关于带权图,450年已出现Erdös的一些论文中甚至萌芽于其他人的更早的论文中,哈代的博士Rado1945年数学年刊考察对点和边赋予实数的模糊化的图等等就是模糊集的雏形,这里的论文论文1论文2论文3论文4论文5等推广国际数学联盟秘书长Martin Grötschel的“dd则对每点有长不少于2d的圈过它或是哈密顿图”以及相关结果也是,比较明确的如Lee White1967年带权图的博士论文TraigerGill1968年的带权图论文等,其实1856创立哈密顿图问题就是为了解决类带权巡回路线问题。而我评论的国际数学联盟主席和诺贝尔奖得主的带权图就更是也。因此模糊集实际上就是仅限制带权图的点元素的权(即隶属度)满足0≤权≤1足够--而点对或集点对的权或隶属度可考虑可不考虑都仅是带权图的研究内容。有了模糊集其后这学科的发展就容易了,也就是模糊数学就是在其上发展起来的模糊拓扑、模糊测度论等数学领域的统称:而关于模糊拓扑空间:设LF格,X是非空集,dÌLX,如果 i)  0, 1Îd,即dLX的最大元和最小元; ii) A, BÎdÞ ABÎdiii) "tÎT, AtÎdÞ tÎTAt Îd,则称dX上的一个L-fuzzy拓扑,称(LX, d )L-fuzzy拓扑空间,它就是拓扑空间在模糊集上的推广(更多内容可见王国俊的专著);再说模糊测度,设{X, }是一个可测空间,若m:: ®[0, 1]满足:m:(Æ)=0, m:(X)=1, 即具正规性;A, BÎ, AÌB Þm:( A) Ìm:(B), 即具单调性;AnÎℱ (nÎN), AnAnWÎÞm:(limn®¥ An)=limn®¥ m:(An)= m:(W),则称m:模糊测度{X, , m:}称为模糊测度空间。如果函数f: X®[0, 1]对任意aÎ[0, 1]均有Fa ={xÎX | f(x)£a}ÎX幂集, Fa ={xÎX |  f(x)³a}ÎX幂集,则称f是可测函数。若f: X®[0, 1]是可测函数,则fA上关于m模糊积分 òA fdm =aÎ[0, 1][am(FaA),其中Fa ={xÎX | f(x)³a}, =sup, =inf  (它是日本Michio Sugeno在博士论文中提出的,常称为(S)模糊积分,其后,也由其他人建立(N)(G)等模糊积分。再关于n维模糊数和n维模糊数空间En,就要考察度量、收敛和连续等,设x, yÎEn,则称d¥(x,y)=sup rÎ[0, 1]dH(|x|r, |y|r)为模糊数空间En上的一致Hausdorff度量(或上确界度量,其中dH(|x|r, |y|r) Hausdorff距离)。设x, yÎEn,则称dp(x,y)=(ò01 dH(|x|r, |y|r)pdr)1/p为模糊数空间En上的Lp型度量。设xk, xÎEn,如果d¥(xk, x)®0k®¥),那么称模糊数序列{xk}依上确界度量d¥收敛于模糊数xxk, xÎEn,如果对任意的rÎ[0, 1],有dH(|xk|r,|x|r)®0k®¥),那么称模糊数序列{xk}依水平拓扑收敛于模糊数xxk, xÎEn,如果对任意e>0h>0,存在KÎN,使得当k³K时,有 m{rÎ[0, 1]| dH(|xk|r,|x|r) >e}<h,其中表示实直线R上的Lebesgue测度,则称模糊数序列{xk}依测度收敛于模糊数x。注意模糊数连续的定义,所有连续模糊数构成的空间记为Enc。设1£p<¥,对任意xÎEn,如果对任意e>0,使得对任意0£h<d,有òh1 dH(|x|r, |x|r-1)pdr<ep,那么称xp次平均左连续的,类似有子集的连续。设(X,Ж)是测度空间,Fμ(X,Ж)={m| m:Ж®R是有界变差的非可加测度--注意这概念}叫做实值有界变差的非可加测度的空间,简记为Fμ。已知Fμ关于范数||m||BV=|m|(X)"mÎFμ)是一个Banach空间,记作(Fμ,||×|| BV)B+={ f|  f:X®R +是非负有界Ж可测函数}B={ f|  f:X®R 是有界Ж可测函数}(Fμ,||×|| BV)B+拓扑是指:对任何fÎ B+,由Choquet积分所定义的从FμR的线性泛函Cf(m)=(C )òXf(x)dm"mÎFμ恒连续的最小拓扑。(Fμ,||×|| BV)B拓扑是指:对任何fÎ B,由非对称Choquet积分即(Č)积分所定义的从FμR的线性泛函Čf(m)=(Č)òXf(x)dm"mÎFμ恒连续的最小拓扑。(Č)积分即当下面等式的右边存在时有(Č)òXf(x)dm=ò-¥0(m({xÎX: f(x)³a})- m(X))da+ ò0¥m({xÎX: f(x)³a})da)。不过这里我们着重说模糊图论(关于下面模糊图的来源,是我研读撰写第一本“模糊图”专著的美国Mordeson主席寄给我的很多他的文献后我再从网上下载应有2百篇国外相关论文参考所得):元素(点、边)权是01表示不存在和完全确定,而0<<1就是介于其间的模糊强度,并要满足(x,y)≤min{(x),(y)}。如此强度是一切的出发点,而模糊图的元素强度不象图论的不是0就是1,则对强度类的研究是模糊图的主要课题(点强度只是限制模糊图是合理的一般没有多少研究价值,因此基本内容放在弧权),虽然和图论有所不同,但把图的概念、运算和性质等结合弧权的模糊度加以推广已可构建模糊图理论的基本体系。如模糊图先驱Azriel Rosenfeld 1975年的开创性论文定义模糊图的一些基本概念和建立一些性质就如此,Raymond  YehBang1975年的论文也引进不同的点连通度W(G)=min{åvÎD{min m(v,u): m(v,u)¹0}, D是割集}、边连通度l(G)=min{åuÎU ,vÎV{min m(u,v): U,V是不交点集}和讨论它们的应用特别是在聚类分析应用(聚类分析是指按确定的标准对客观事物进行分类的数学方法,如此他们主要是基于模糊等价关系的系统聚类法和基于模糊划分的逐步聚类法)。而这些定义都基于弧权强度。如此路的强度=minm(ei)是自然的基本的(类似定义圈、哈密顿圈等的强度),进而才定义两点x,y间的strength=strongest路的strength记为CONNG(x,y)和最强路,Rosenfeld 论文定义若CONNG(x,y)>0 for every x,y则说模糊图是连通的。再进而Bhutani主任和Rosenfeld院士最近定义强弧(x,y)m(x,y)CONNG-(x,y)(x,y)),那与其相连的点为强邻点,一端点也可说为另一端点的强邻点,若只有一个强邻点的点就称为结点,每边都是强弧的路称为强路(什么条件下两点间有强路?是唯一强路吗?两点间是否有哈密顿路?哈密顿路是否强路?最短路是肯定存在但是否强路?又是否强路?等等,绝大多数都还没有研究),类似研究强圈会有怎样的意义?国际不确定性数学学会主席John Mordeson定义的模糊圈一直得到国际上广泛公认极有必要研究(它是至少含两最弱弧。对某些特殊模糊图可能难度不大,但解决更一般图的难度就增大。我很荣幸得到John Mordeson主席花钱花费时间从邮电局寄他的一些很重要的论文给我。特别是最近Mordeson主席等撰写的《模糊图和模糊超图》是一个基本综述,Mordeson也写模糊线图并定义强模糊子图strong fuzzy subgraph if m(x,y)=s(x)s(y) for all (x,y)ÎE; while fuzzy subgraph if m(x,y)s(x)s(y) , 这是一类特殊模糊图则哪些图通过各类f图运算是这类图?这显然的一个有意义课题。),哈密顿圈同样可定义强哈密顿圈模糊哈密顿圈(研究哈密顿圈和圈经过某些特殊点是图论里长期的热门课题,但在这模糊图里,主要考虑弧的类型或说隶属范围。因此,研究这两类哈密顿圈甚至更一般的哈密顿圈经过某些特殊权弧肯定是要解决的优先课题,但至今还没有这方面的工作。这是有些困难的课题,而Multimin哈密顿圈更非常困难(还没有定义M哈密顿圈,因为是否存在此哈圈也很难判别?),这肯定是哈密顿图、可迹以及泛圈性等的最主要课题),因与强邻点相连的强弧既有一条(它是结点)、有多条的情况,如此最近Sameena的博士论文就自然引进强度数=关联的强弧的权之和(YehBang定义的v度数=åm(u,v)v的关联的弧权之和,因而图有最大小度)。(既然弧类决定着图的类型,则各类弧情况也要分类研究即还有很大空间。如根据m(x,y)>=<CONNG-(x,y)(x,y)的弧类可划分为3类,而分别研究清楚它们也应算是基本的课题。而模糊图的绝大多数各类概念是基于弧类型划分和定义的,从而模糊图的各类概念就相应随之细化和类型增多),也不仅有模糊子图还有partial模糊子图(H:(t,h), G:(s,m)Ût(u)s(u),t(u,v)m(u,v)。应抓紧时间优先把各方向的各个高楼的第一层最基本概念建立,随着研究的深入还可定义弧或点权取等号、或小于号的情况。类似可定义完全模糊图的2种主要情况)还有Arnold Kaufmann论文维基的模糊数学提到图的先驱工作就只说这书和前3篇。可这Eiji Takeda1973的和Dunn1974的更早,可惜我找不到这2篇论文,不知道它们建立怎样的连通度等概念和做出什么理论?Rosenfeld 论文定义割点,其后某别人的论文定义模糊点割X(fuzzy nose cut) if CONNG-X(x,y)<CONNG(x,y) for some x,yÏX|G-D|=1X是模糊点割则Xstrong权记为s(X)=åxÎXm(x,y),  xy是和x相连的strong弧中权最小的,最小的s(X)称为fuzzy node connectivity(模糊点连通度)k(应该可以定义x相连的弧中权最小的连通度,这是介于这k和下面Yeh等的之间的定义,这个定义应是比这两个定义提得更自然,真的还没有人提出?是这概念的现实意义不比这两个大?)。E={e1,e2,,en}Strong弧集,如果CONNG-E(x,y)<CONNG(x,y)G-E不连通for some x,y with at least oneE不关联则称E是模糊弧割(fuzzy arc cut简称FAC),模糊弧割Estrongs¢(E)=åeÎEm(e) 的最小者称为模糊弧连通度k¢(应该可以定义不必一定strong弧的弧连通度,这也是介于这k¢和下面Yeh等的之间的定义)。YehBang论文却定义另一类模糊点割G-D是不连通|G-D|=1的点集D(和图的定义相似),D的权=åxÎD{min m(x,y)| m(x,y)0},它的点连通度W(G)定义为割集中的最小权-因是一般图的推广-而一般图的定义只取一点那它就要取与此点关联的一弧权-取那一弧权呢-因定义是取最小权而取最小弧的权又并不矛盾则最自然也最合理。类似定义模糊边连通度l(G)YehBang定义它)是模糊弧割最小的strong权。如果k¢t,则说Gt-模糊边连通的。Gt-模糊边分支是G的最大t-模糊边连通子图。还有很多与图论很不同的基点概念也建立:模糊(multimin locamin)正则模糊图、模糊积图、模糊图的补图m(x,y)=0s(x)s(y))、模糊结点(至多关联一强弧)、模糊控制图(各类控制点)、模糊图的块(无模糊割点)、模糊树(与图的树非常不同,我不知道是否还有其它定义,这篇IS论文是指有唯一最强生成树的,已有很多应用),还有图论里也没有出现的强模糊图,等。点集C的导出图是Gt-模糊边分支则称Ct-聚类牛津博士Prabir Bhattacharya-cv论文也创立与点割和桥有关的连通性概念,最近RosenfeldBhutani定义Strong=它的权不少于它之外两端点的连接强度,Strong =每弧是strongend nodes=仅有一关联弧是strong,他们还定义geodesics等。点v的度d(v)=åu¹vm(u,v),图的最小度d(G)=(d(v): vÎs*), 最大度D(G)=(d(v): vÎs*);而若记Ns(v)strong邻弧集、点vstrongds(v)=åuÎNs(v)m(u,v),则类似可定义最大最小strong度,等等(除了下面吴望名吴乐光2篇和罗崇澍1篇论文我只看摘要外,我还真没有看过国内的论文,主要是国内还没有图论专家搞模糊图论,而这些模糊数学专家搞的模糊图论都不是以图论思想为主轴,如此上面这些概念都是我从国外模糊图论专家的论文上摘录,而且主要是近年出版的,我想绝大多数概念国内还没有人提出过才必要在此陈述)。用fuzzy graph在美国数学评论搜索2008年以前每一年都没有超过十篇,但其后每年都超过十篇,当然还有。我国这方面论文至今仍很少-主要基于上面提过的中国模糊数学副理事长吴望名以及我们海南省人大副主任吴葵光哥哥-华中科技大学副主任汕头大学第一任系主任吴乐光1980年有限的引进工作--前者主要介绍国外工作特别是图论对聚类问题的研究、后者给出一类连通定义和探讨其等价性,至今还没有见一个图论专家做一篇模糊图论文,这是一件憾事!虽现在不好说它模糊图的生命力是否强到今后能发展成为一个重要学科,但基于它已有许多重要应用--如已应用在评估心脏功能、地质灾害、大气环境、地下水质、飞行器故障、核武器事故、导弹电路故障、导弹核武器等,如此,我有必要在这里提出来,以引起我国图论界的注意!也因我国模糊数学界专家也仅在它的各个方向领域各放一、二枪并没有形成系统及可操作的理论(如吴乐光数学评论只有4篇论文更仅1篇是模糊图,吴望名虽多但模糊图也仅一篇,其中吴望名仅是介绍国外某些工作,吴乐光仅用3页考虑某类连通则很有限且之前已有RosenfeldYehTakeda等许多论文已讨论连通性,如此意义已小也会重复别人。可模糊图在模糊数学中之位置如没有写过一篇模糊图论文的模糊数学之父Zadeh在香港中大Yeung Yam任扬)教授等编辑的《模糊集与系统的未来的方向》论文集中写了“模糊控制、模糊图与模糊推理”把模糊图列在第二位,足见模糊图居模糊数学的前沿要位。我国较接近模糊图论工作的就是重庆大学城市科技学院常务副院长吴德垠教授和他的十个硕士所做的-但严格讲吴仍属于模糊数学专家如此他们也并没有从图论角度去建立理论体系 ---这重庆大学的这独立学院的正院长是全国人大代表、重庆政协副主席。而非常遗憾的是我国图论专家至今仍似乎普遍不屑模糊图论(如国家基金一个评审专家说“模糊图的研究基本上没有任何意义,是一个死去的研究领域”,不知道他说“基本上没有任何意义”是相对哈密顿图相对于图论的悠久历史的重要意义来说,还是绝对的结论?也是否多数图论专家有此看法?不过,模糊图的思想确是主要借助于图论和模糊数学,而模糊数学也似乎源于图论的权图,就有些名不正言不顺,就象在狭缝中生长;再者,更可量化的数据是:这么多年来每年MR收录的模糊图论文都是约十篇左右。不过,近两年有进入新阶级的迹象!),还有,不少人也有这样的误解:做模糊数学的人是因做不出严格的理论所以就"模糊"一下算,或认为因不能解决传统领域中的难题,才来到 "模糊"里面来混?(应该说因象我们有3百年历史哈密顿图的上面每一节的每一个定理都要用约十页才能证明,有些问题要几百页才能证明-因此证明一个定理可要痛苦多久啊--而我看到模糊集、粗糙集几乎都仅用几行就能证明--当然我接触的模糊数学还有限的那看法也就可能不全面-而且凡事也总有例外;而且模糊数学仅有几十年的历史,当模糊做久了仍长年攀登不上的也会是高峰般的艰难问题的),不受重视或是否如模糊数学之父Zadeh都不仅不是美国科学院院士甚至也不是艺术与科学院士而仅是可不需要严格理论的工程院士,然而图论却既有美国科学院副院长、也有国际数学联盟主席,甚至给我来信的图论专家Bollobás院士在MGP都有Biography而它就不给Zadeh这资格

模糊数学之父Zadeh1973再提出推广上面模糊集区间值模糊集A={(x, m-A(x), m+A(x))| xÎX}, 其中X是论域,m-Am+AX®[0, 1]的函数并满足对任意xÎX均有m-A(x)m+A(x)(这是因很多情况下很难用一个确切数值来表达一个对象隶属于一个模糊概念的程度,才必要提出推广模糊集的概念)。Zadeh1975年再用论文I、论文II和论文III论述它,正如著名模糊论专家李洪兴教授等对区间值模糊集的研究兴趣与日俱增 李洪兴等最近也说随着模糊集理论的发展各种L-模糊集相继出现而其中最常用的是直觉模糊集和区间值模糊集(注L-模糊集是X-L映射,其中(L,)表示满足在一个全序集中有上确界的完备格可见Kerre等的著作的第24Kerre也写了多篇这方面相关文章但最先是出现于Goguen1967的论文,又于起应用与日俱增,因此有必要建立它们相应的模糊图(关键是对图的点和弧怎样合理地派指令权,就有相应的区间值模糊图),这里给出的区间值模糊图G(A,B)规定为区间值模糊集A=(m-A(x), m+A(x)) 是对图的点集V的权函数,区间值模糊集B=(m-B(xy), m+B(xy))是边集EÍV´V的权函数且m-B(xy)min{m-A(x), m-A(y)}m+B(xy) min{m+A(x), m+A(y)}NNTDM主编K. Atanassov教授1983年在()文中提出后1986年以英文提出直觉模糊集A={(x, mA(x), vA(x))| xÎX}, 其中X是非空集合,函数mA(x):  X®[0, 1]vA(x): X®[0, 1]分别是X上元素x属于A隶属度和非隶属度,并满足0≤mA(x)+ vA(x)≤1直觉模糊集的特征虽是同时考虑隶属度和非隶属度两方面的信息,但李洪兴等说本质上与区间值模糊集是等价的)。相应的直觉模糊图G(A,B), 其中A={mA, vA} X上的直觉模糊集,B={mB, vB} X´X上的直觉模糊集,并mB({x,y})min{mA(x), mA(y)}vB({x,y})max{ vA(x), vA(y)}) for all x,yÎX satisfying mA(x)+vA(x)1 and mB({x,y})+vB({x,y})1;(关于相应的测度和积分2005年罗马尼亚Adrian Ioan BanSugeno integral with respect to intuitionistic fuzzy-valued measures, Notes on Intuitionistic Fuzzy Sets, 11 (2005) 2, 47-61中提出模糊测度:设{X, }是一个可测空间,t: ®L,若满足:t (Æ)=(0, 1), t:(X)=(1, 0), 即具正规性;A, BÎ, AÌB Þt:( A) £L t (B), 即具单调性,则称t上的直觉模糊值模糊测度,其中AA(x)={mA(x), vA(x)}x属于A的隶属度和非隶属度;再关于积分,根据格值函数的S-型格值模糊积分,他提出直觉模糊值Sugeno积分:设{X, }是可测空间,t: ®L是一个直觉模糊值模糊测度,f~: X®L 是一个-可测直觉模糊值映射,对任意的AÎ f~在集合A上关于t直觉模糊值Sugeno积分为:(Sl) òA f~dt =supL infLaÎL[a, t (F~aA)],其中F~a ={xÎX | f~ (x)³La}, aÎL  )。下面要介绍的Vague集是这里8说我们琼州大学石玉强和王鸿绪教授等最近热心研究的领域- 它是1989年成立才3台湾中正大学2个专家GauBuehrer-貝若爾中正大学为作者单位在这1993论文中提出等同于直觉模糊集用真隶属函数tV(x)和假隶属函数fV(x)表示的Vague:设X是一论域,称{x, [ tV(x), 1- fV(x)]| xÎX }确定一个VagueV,其中对论域X的每一元素x,  tV(x)是从支持x的证据所导出的的真隶属下界,  fV(x) 是从支持x的证据所导出的的假隶属下界, 0tV(x)+fV(x)≤1;假设AB都是Vague值,其中A=[ tA(x), 1- fA(x)]B=[ tB(x), 1- fB(x)]GauBuehrer定义AB的运算和关系如下:AB=[ tA(x)tA(x), (1- fA(x))(1- fA(x))]=[min{ tA(x), tA(x)}, min{(1- fA(x)), (1- fA(x))}], AB=[ tA(x)tA(x), (1- fA(x))(1- fA(x))]=[max{ tA(x), tA(x)}, max{(1- fA(x)), (1- fA(x))}], ABÛ tA(x) tA(x), (1- fA(x))(1- fA(x));(Vague测度和积分:X上的δ-代数,m:: ®I[0, 1]y↦⊢[p(y), 1-q(y)]满足;m:(Æ)=[0, 0], m:(X)=[1, 1]A, BÎ,  AÍB Þm:( A) m:(B)AnÎ (nÎN), AnAnWÎÞlimn®¥ m:(An)= m:(W),则称m:Vague测度{X, , m:}称为Vague测度空间。其中I[0, 1]表示单位空间[0, 1]中的所有闭子空间,m:( A) m:(B)Û p( A) p(B), 1- q( A) 1- q(B)。关于Vague测度可作如下解释:设某个元素xÎX px可能属于的某个元素A的模糊性的度量,qx可能不属于的某个元素A的模糊性的度量。因此,若A=Æ,则xÏA,从而p(Æ)=0,  q(Æ)=1,即m:(Æ)=[0, 1];类似有m:(X)=[1, 1];若AÍB Þx属于A的可能性比属于B的可能性小,x不属于A的可能性比不属于B的可能性大,因此m:( A) m:(B)。关于积分:设{X, , m:}Vague测度空间,V是定义在X上的全部Vague函数集,v(x)=[ t(x), 1- f(x)]Î V, AÎℱ, m:Vague测度,则vA上关于mVague积分 (s)òA v(x)dm =EÎ {xÎEv(x)m(AaE)}= [∨EÎ {xÎEt(x))∧p(AaE)},EÎ {xÎE(1- f(x)))∧1- q(AaE)} ] )。在台湾蒋介石大学2专家的Vague集的一些相关理论基础上,其后已有些人提出和研究VagueG=(s, m)是一对函数s, m,其中s是关于论域XVague, m是关于sVague关系,这里X称为点集。还有表达不确定数据能力更强的区间值VagueQ=(<x, tQ(x), fQ(x)| xÎX),  区间值Vague集合tQ, fQ分别表示x关于Q的真假隶属度tQ(x)=[tQ1(x), tQ2(x)] ,fQ(x)=[fQ1(x), fQ2(x)],且 tQ2(x)+ fQ2(x)≤1。还可定义区间值Vague,等等

Atanassov1989又再提出区间值直觉模糊集A={(x, mA(x), vA(x))| xÎX}, 其中X是非空集合,mA(x)=[m-A(x),m+A(x)]Ì[0, 1], vA(x)=[ v-A(x), v+A(x) ]Ì[0, 1], X®[0, 1], 对应的 mA(x), vA(x) 分别表示隶属度和非隶属度。m-A(x)m+A(x)mA(x)的上限和下限,v-A(x)v+A(x) vA(x) 的上限和下限且要满足m+A+v+A 1。此外,xA(x)= [x-A(x), x+A(x)]表示区间值直觉模糊集的犹豫度,其中x-A(x)=1-m+A(x)- v+A(x)x+A(x)=1-m-A(x)- v-A(x)。显然m-A(x)=m+A(x), v-A(x)= v+A(x)A就退化为直觉模糊集。(上一段李洪兴等说直觉模糊集本质上与区间值模糊集是等价的,那区间值直觉模糊集和直觉区间值模糊集更都是A={(x, [m-A(x),m+A(x)], [ v-A(x), v+A(x) ]| xÎX}。而我们琼州大学数学系俞峰的2008年在南京理工大学的博士论文就做“基于直觉区间值模糊理论的近似推理与多属性决策研究”,俞峰博士毕业后接着在华南理工大学做博士后-而在和导师李荣钧合作7篇论文中竟有5是对这里8说的我们赵家的初中毕业生创造的“集对分析”应用的,其中也说我是因2002年一篇模糊数学论文获海南省最高奖,我才关注这学科。其后,黑龙江省科技出版社2003年出的著作的“模糊逻辑模糊推理”一章署名上是我独写的其实要归功于王教授。模糊推理就是上面俞峰教授的近似推理,当然这书仅是基础。这书由海南省模糊数学开创者-下几节说到的海南师范大学张诚一校长作“序”,中对全书章节内容只说“模糊逻辑已成为智能计算的重要组成部分”--因此很荣幸。关于相应的测度和积分测度定义:称映射p~: ®L上的区间直觉模糊值模糊测度,当且仅当满足如下条件;p~ (Æ)=(0, 0, 1, 1), p~ (X)=(1, 1, 0, 0), 即具正规性;A, BÎ, AÍB Þp~ ( A) £L p~ (B), 即具单调性;AnÎℱ (nÎN), AnÞp~:(n=1¥ An)= lim n®¥ p~(An)An Þp~(n=1¥ An)=lim n®¥ p~(An)。可测映射的定义;如果映射f~: X®L对任意a~ÎL均有Fa~={xÎX | f~ (x)£L a~}ÎX幂集, Fa~ ={xÎX | f~ (x)³L a~}ÎX幂集,则称映射f~区间直觉模糊值可测。,或简称映射f~L-可测的。积分定义:如果映射f~L-可测的,p~上的区间直觉模糊值模糊测度,则映射在集合X上关于p~区间直觉模糊值Sugeno积分为:(S~l) ò f~dp~ =a~ÎL[a~p~(Fa~))。现照搬这里的直觉区间值模糊集的定义D={a|a=á[-a-,-a+],[-a-,-a+]ñ, [-a-,-a+][0,1], [-a-,-a+][0,1], -a++-a+≤1[-a-,-a+][-a-,-a+][1--a+--a+, 1--a---a-]分别表示隶属程度、非隶属程度和犹豫程度区间},规定a≤bÛ-a--b-,-a+-b+, -a--b- ,-a+-b+ab=á[-a--b-,-a+-b+],[-a--b-,-a+-b+]ñ, ab=á[-a--b-,-a+-b+],[-a--b-,-a+-b+]ñ。则直觉区间值集合(D,≤)是一个完备格,á[1,1],[0,0]ñá[0,0],[1,1]ñ分别为最大值和最小值。我认为,显然最大小值完全决定于①的规定而与②无关。至于②的规定,只考虑它是否有违于①等以及这样规定会建立什么运算公式和导出怎样的模糊运算性质,而似乎怎么规定如最后的2∧改为∨都有最大小确界如此都是完备格?②的规定可能是最常规的,因我没有时间了解到很多涉及的东西就不能有更多体会)。我还没有时间多考虑:虽这两类模糊集叙述的顺次有所不同,但是否实质都是殊途同归A={(x, [m-A(x),m+A(x)], [ v-A(x), v+A(x) ])| xÎX}?这样我们可统一定义区间直觉值模糊图直觉区间值模糊图(在Google搜寻见区间图直觉也仅有几篇论文,这段的两类图更没有见任何定义,现在我们可定义它们为G(A,B)规定为直觉区间值模糊集A={ [m-A(x),m+A(x)], [ v-A(x), v+A(x) }是对图的点集V的权函数,直觉区间值模糊集B={ [m-B(xy),m+B(xy)], [ v-B(xy), v+B(xy)}是边集EÍV´V的权函数且m-B(xy)min{m-A(x), m-A(y)}m+B(xy) max{m+A(x), m+A(y)}v -B(xy)min{ v -A(x), v -A(y)}v +B(xy) max{v +A(x), v +A(y)}(也可以不做如此规定只结合目标规定就行,因为现实世界中的图可能其结点已模糊不清而连接它们的边却是较清楚的)并限制m+A(x)+v+A(x)1 m+B(xy)+v+B(xy)1,还要做一些规定以便能确定各种情况下的关系和运算(这里仅止于提出以便有时间的时候再进一步思考。这第10节的各类模糊图内容除了补充的这段俞峰的外都约在2003年黑龙江出版上面模糊数学著作时已草拟,然而已过去了这么多年却这直觉区间值模糊图竟还没有一点研究,那研究它的上面任何模糊图性质都是填补空白。我对俞峰的博士论文基于直觉区间值模糊理论的近似推理与多属性决策研究还是较感兴趣,那相应的直觉区间值模糊图理论在哈密顿图已艰难的情况下也不妨换个思路用为博士学位论文,如上面第1节哈佛大学权威的39页博士论文的弟子至今仅有1篇杂志论文,上面第7节和三个权威合作的台湾从98年到07年做了9博士的也仅有2篇论文,如我的这篇200的除了年轻时无知被诱骗得头痛之极外--只剩下后悔…,以前可是5行字就可成海南最伟大数学家。这是痛忆以前,现在已是金钱衡量价值的时代…真他妈付出这么多年…

Wen-ran Zhang1994年也提出推广模糊集Bipolar双向模糊集B={(x, mP(x), mN(x))| xÎX}并也已很受到广泛关注, 其中X是集合,mPX®[0,1]的映射,mNX®[-1,0]的映射。这里给出Keon-Myung Lee 教授其后提出并被接受的双向模糊图G(A,B),他定义双向模糊图G(A,B)为双向模糊集A=(mPA(x), mNA(x)) 是对图的点集V的权函数,双向模糊集B=(mPB(x), mNB(x))是边集EÍV´V的权函数,且mPB({x,y})≤min{mPA(x),mPA(y)}mNB({x,y})≥max{mNA(x),mNA(y)} for all {x,y}ÎE    

此外,最常用的L-模糊集还有:模糊值模糊集和二型模糊集。不过,在一定条件下,模糊值模糊集可由区间值模糊集生成;每一个二型模糊集可转化成一个区问值模糊集且每个区间值模糊集可看做一个二型模糊集。

上面已看到模糊集之父Lotfi Zadeh模糊集的思想源于哈密顿图之父的图论的图权思想;下面的粗糙集之父Zdzisław Pawlak1958年完成的博士论文更是做图论应用的。现在粗糙集也已发展出很广泛的应用,因此就象模糊图论一样粗糙图论也可期待发展。只是除了上面吴望名吴葵光哥哥2介绍性论文之外--非常难以置信的是我国至今还没有其它谈得上有意去建立模糊、粗糙图论核心理论的论文,其它零星的都只仅各为个人目的去做些重复应用

粗糙集理论把知识看作是关于论域的等价划分。U为有限论域,U上的一族等价关系,K=(U, )为知识库,若RÍ,且R≠Æ,则∩R也是一个等价关系,记为Ind(R),并称之为R不可区分关系,U/Ind(R)表示不可区分关系Ind(R)U上的导出的等价类。设(U, P), (U, Q)是两个知识库,对两个等价类U/Ind(P)U/Ind(Q),如果对任意AÎU/Ind(R) BÎU/Ind(R),使AÍB,则称知识P比知识Q较细,记P≤Q,该关系可以看作知识库K上的一个偏序。定义AR上近似、R下近似分别为R-A={[x]R| [x]R∩A≠Æ}R-A={[x]R| [x]RÍA},其中[x]R表示UR等价类。   EÍRq是一个非空可测集,如果E=Ei, i取值有限,Ei为互不相交的非空可测集,则称集合族D={Ei}E的一个可测分划,简称分划。设D*={Ei*}E的另一个可测分划,如果" Ej*ÎD*, $EiÎD使是Ej*ÎEi,则称D*D细。" AÍEmAALebesgue 测度,f(x)为定义在Rq中的测度有限集E上的有界函数,对E的任一分划D={Ei},令Bi=sup f(x), bi=inf f(x), 其中xÎ Ei,则S(D, f)=å BimEis(D, f)=å bimEi,为别称为f(x)关于分划D的大和与小和,ò*Ef(x)dx = infDS(D, f)ò*Ef(x)dx = supDs(D, f)为别称为f(x)E上的Lebesgue上、下积分。如果ò*Ef(x)dx =ò*Ef(x)dx,则称f(x)E上的Lebesgue可积,且称此共同值为f(x)E上的积分,记为òEf(x)dx

下面是结合模糊集定义的各类粗糙集。模糊粗糙集2000年才从大陆来海南省最悠久的高等学府的上几节说过的海南师范大学副校长的张诚一教授刚出版的论文“关于模糊粗糙集的相似度量”定义它为:“设S为粗糙集之集合,X=(XL,XU)ÎS,则X中的一个模糊粗糙集A=(AL,AU)由一对映射mAL, mAU来刻画,这里mAL: AL®[0, 1],  mAU: AU®[0,1],并且mAL(x)mAU(x), "xÎAU”。我用中文英文搜索还没有见模糊粗糙这几个字,如此为了我或图论界的人来更准确合理定义这类图,就要先确保张诚一校长的定义正确,因为各类模糊粗糙图的定义是建立在各类模糊粗糙集的基础上。但我对张诚一校长的定义感到困惑,就核对以求确信。因为模糊粗糙集若是把粗糙集X看做一个集来确定模糊集,映射应是X®[0,1](即(XL,XU) ®[0,1],而非张校长的(AL,AU) ®[0,1] 当然还应确保mAL(x)mAU(x)否则失去粗糙集的上下近似之特征,也就不是模糊粗糙集了。显然,因我不是搞此专业的才提出如此初等的问题,因为教授做为权威该专业的人都知这样的问题只是笔误或排版错且也不会影响专业人的判断)。 此外,对于区间值模糊粗糙集直觉模糊粗糙集直觉区间值模糊粗糙集双向模糊粗糙集优势区间直觉模糊粗糙集区间值模糊粗糙概率集可根据需要的类型可类似定义它们的上近似和下近似在U上的一对区间值模糊集直觉模糊集区间值直觉模糊集双向模糊,但我也还没有见国际上有它们相应的每类模糊粗糙图的定义和任何一点研究。为定义这几类进一步的图类,这里先只着重给出区间值直觉模糊粗糙集的几类定义:R是论域U区间值直觉模糊关系,称二元组(U,R)是一个区间值直觉模糊近似空间。假设TL上连续区间值直觉模糊T模,I是定义在L上的区间值直觉模糊蕴涵,对于任意的AÎIVIF(U)A关于近似空间(U, R)T-上近似和I-下近似是定义在U上的一对区间值直觉模糊集,其中R-T(A)(x)=yÎUT(R(x,y), A(y)),"xÎUR-I (A)(x)=yÎUI(R(x,y), A(y)),"xÎU。注意 LTI的定义。这里算子R-T, R-IIVIF(U)® IVIF(U)称为T-上和I-下区间值直觉模糊粗糙近似算子; 二元组(R-I (A), R-T(A))称为A关于(U,R) (T,I)-区间值直觉模糊粗糙集。另一定义:设UW是两个有限非空论域,RUW之间的一个IVIF关系,三元组(U,W,R)称为一个IVIF近似空间。"AÎ IVIF(W)A关于近似空间(U,W,R)的下近似R-(A)和上近似R-(A)U上的一对IVIF集:R-(A)={<x, ÙyÎW[mA(y)Ú(1--mR(x,y))], Ú yÎW [vA(y)Ù (1--vR(x,y))]>| xÎU}和上近似R-(A)={<x, ÚyÎW[mA(y)ÙmR(x,y)], Ú yÎW [vA(y)ÙvR(x,y)]>| xÎU}。再另一定义:设二元组(U,R)Pawlak近似空间,A={(x, mA(x), vA(x))| xÎX}区间值直觉模糊集,记A-R={(x, [infyÎ[x]R{inf mA(y)}, infyÎ[x]R{sup mA(y)}], [supyÎ[x]R{inf vA(y)}, supyÎ[x]R{sup vA(y)}] | xÎX}, A-R={(x, [supyÎ[x]R{inf mA(y)}, supyÎ[x]R{sup mA(y)}], [infyÎ[x]R{inf vA(y)}, infyÎ[x]R{sup vA(y)}] | xÎX}。若A-RA-RA-RA-R分别称为区间值直觉模糊粗糙集A的下近似和上近似。虽Vague集也属模糊集,但下面仍进一步给出结合Vague集定义的各类粗糙集。Vague粗糙集U是论域XUVague集,关于UVague粗糙集A用真隶属函数mA(x)和假隶属函数vA(x)表示,并[mA(x), 1-vA(x)]=[1, 1] for xÎR-X[mA(x), 1-vA(x)]=[0, 0] for xÎU- R-XmA(R-X - R-X)+vA(R-X - R-X)1, 其中近似空间A是由论域U上的等价关系R决定,XÍU的上近似R-X={xÎU| [x]RXÆ}和下近似R-X={xÎU| [x]RÍX}拓扑粗糙VagueX={<x, [ tX(x), fX(x)]>: xÎU}是拓扑空间(U, T)Vague. 拓扑空间(U,T)X的拓扑下近似X-T和上近似X-T分别为:X-T={<x, [inf {tX(y): yÎG, GÍX},sup{ fX(y): yÎG, GÍX}]>, xÎU, GÎT}, X-T ={<x, [sup {tX(y): yÎG, GXÆ},inf{ fX(y): yÎG, GXÆ}]>, xÎU, GÎT} , (X-T, X-T)称为拓扑空间(U, T)VagueX的拓扑粗糙Vague集。粗糙区间值VagueX={<(x, tX(x), fX(x)>: xÎU}是论域U的区间值Vague集,X的下近似X-和上近似X-分别为:X-={<(x, t-X(x), f-X(x)>: xÎU} X-={<(x, t-X(x), f-X(x)>: xÎU},其中t-X(x)=[inf{inf tX(y), yÎ[x]R, xÎU }, inf{sup tX(y), yÎ[x]R, xÎU }] f-X(x)=[sup{inf fX(y), yÎ[x]R, xÎU }, sup{sup fX(y), yÎ[x]R, xÎU }] t-X(x) =[sup{inf tX(y), yÎ[x]R, xÎU }, sup{sup tX(y), yÎ[x]R, xÎU }]f-X(x) =[inf{inf fX(y), yÎ[x]R, xÎU }, inf{sup fX(y), yÎ[x]R, xÎU }] ,称(X-,X-)Pawlak近似空间的粗糙区间值Vague集。类似可定义它们的各类Vague粗糙图,等等

我刚看到这里第8说的我们琼州大学跑去广州的石玉强和他唤醒的王鸿绪教授单在上面一个Vague的应用就发表非常多论文,那象我们搞图论等几百年悠久历史学科的为什么不重视象这些新领域,因要是上面每一类都搞起应用来,仅论文就将何其多(再比Vague更进一步的这Vague粗糙图世界上还没有人研究--甚至比Vague进一步的Vague以及其它各类Vague模糊图世界上也仅有几篇离核心尚远的论文-根本谈不上有一点研究)。当然,不提倡一蜂窝的蜂拥而来,但象战胜解决图论等几百年悠久历史遗留大问题还是更有意思的

最近邀请海南琼州大学担任他主编的杂志的编委的Bijan Davvaz校长也开创模糊代数学的许多领域,当然相关领域还有模糊拓扑学等等

赵克文得到若干更进一步更深化的各类图及相关课题的结果。因篇幅所限待另述。

几十年来Prism Hamiltonian也是一直受到一定关注的课题。最近OzekiA degree sum condition for graphs to be prism Hamiltonian得到

定理10.1: n阶图G的不相邻的任意3x,y,z均有d(x)+d(y)+d(z)≥n,则GPrism 哈密顿的

Tomáš Kaiser, Daniel Král, Moshe Rosenfeld, Zdeněk RyjáčekHeinz-Juergen VossHamilton cycles in prisms主要考虑平面图等的情形和提出几个问题猜想:

2-连通无爪图是Prism 哈密顿图”猜想已被Čada证明,还有2个猜想“3-连通平面图是Prism 哈密顿图”4连通4-正则图是是Prism 哈密顿图”

最近赵克文得到哈密顿图的泛圈性论文“Pancyclism and bipancyclism of Hamiltonian graphs

定理[47] (赵克文等)G是哈密顿图,若存在一点x使得对任何与x的距离是2的任意一点y均有|N(x)N(y)|≥n-δ,则G是泛圈图或Kn/2,n/2

赵克文等得到含独立边集FH论文“On F-Hamiltonian graphs”:

定理[48] (赵克文等)n阶图G的不相邻的任意2x,y均有|N(x)N(y)| +δ≥n+1,则对G的任一独立边集FGF- 哈密顿的。

赵克文等也得到圈含匹配的论文Proof of a conjecture of Häggkvist on cycles and independent edges”

定理[49] (赵克文等)n阶图G的不相邻的任意2x,y均有|N(x)N(y)|+δ≥n+1,则对G的任一匹配MG有一圈通过M

定理[50] (赵克文等) n阶图Δ-freeGNC+δ≥(n+1)/2,则G的任何最长圈都是控制圈

赵克文也得到推广和改进上面英国皇家科学院院士Béla Bollobás教授的和有2千个教师的南京理工大学七个国家有突出贡献的中青年专家之一的施容华教授的度和工作如下(施教授1980年的第一篇和现在的最后一篇不是图论论文外其余全部论文都是图论论文。迄今为止施教授只有《图论杂志》的这篇度和的和《线性代数应用》杂志上的另一篇共2篇论文是SCI杂志论文,但施教授的其它论文也重要足见以前情况。这度和的其它结果也有趣。施教授是我佩服的国内图论专家之一,正如国务院特殊津贴专左光纪教授在期刊上所说施容华教授的工作“是我省数学界第一次在全国崭露头角”):

根据定理10.1NC所起的作用等,我们提出下面猜想是合理的(不成立的可能性也存在,即NC+δ+kn充分性可能稍微偏弱一些?若不成立,但要发现反例也需要先做很多工作)

Faudree校长、FlandrinRyjáček校长的1997年的著名无爪图综述文章95页有三个表,表1列出1连通无爪图的度型和邻域并型条件的进展,表2专门列出2连通图无爪图度型条件的进展;表3专门列出2连通图无爪图邻域并型条件的进展。因从上面第1节看到名垂青史的结果都是一般图,因此我主要做一般图。不过,我当时也对Gould主席和Faudree校长在大会报告的工作感兴趣,因此,这方面我把表1和表3的邻域并型的条件全都做到极至,得到包括最极限的情况1≤|N(x)N(y)|≤α-1

值得关注:“哈密顿圈+某些限制如固定一点的Ore or NC等的点泛圈®最短泛圈”的课题。“k-树”是最大度至多是k的树,“k-链”通过每点至多k次的闭迹。那“k-树”和“k-链”含给定某些特别点的度和、邻域并条件是什么?对于特殊限制图,除了前面说到的一些图包括超立方体网络外,其它许多著名的图也有好的哈密顿性或次哈密顿性,如Kneser (它由Kneser1955年最先研究而得此名。因它的高度对称性而一直受到关注,Biggs1979年猜想当k>2K(2k+1,k) 是哈密顿图。这猜想仍悬而未决),Square graphc-net或称polyhedral graphApollonian network有向完全图-竟赛图等。二分网络图也值得参考可见纽约州立大学石溪分校博士徐力行教授的Edge-bipancyclicity Bipancyclic等,及他和美国加州大学洛杉矶分校博士高欣欣教授的Bipanpositionable Hamiltonian;相关课题还有台湾数学会常务理事长张镇华教授和台湾中山大学朱绪鼎教授(台湾数学7个学术委员之一)的Pseudo-k Hamiltonian-connected等。最近美国伊利诺伊大学的我师弟的博士导师Kostochka 教授诺贝尔奖得主Gowers的师弟Balogh教授等2009年的论文quasi-line graphs-半线图引起了更多注意,如此也是值得关注的领域  

附录:这里美国纽约曼哈顿的哥伦比亚大学主办的图论网中排名世界第25图论权威张克民教授在1991年南京大学举办的哈密顿图研讨会前言中说“在哈密顿图及其应用方面,我国图论工作者做出了许多优秀的工作”。后言中说“会议自始至终是热烈和充实的,已达到预期的目的,对会后推动图论,特别是哈密顿图的研究起到积极的作用”“大多数代表认为这种务实的专题讨论会,议题集中,人员兴趣一致,从而收到显著的效果”。会议有百余人参加,交流论文64篇,由于当时信息不畅等原因,这南京哈密顿图会议的百来个参会的研究者主要来自中科院和南京地区的部分专家和研究生,而当时全国范围内除了边远地区外每一个省都有大批从事哈密顿图的专家和研究生--他们没有来参加这会议,他们也为探索哈密顿图、为我国哈密顿图赶超世界水平奋斗!现在的哈密顿图研究队伍更是倍增更是横跨各学科。因此,从事哈密顿图极具挑战性

从事三大难题之首的哈密顿图要能做到深入浅出,就是通常说的要见树木也要见森林。深入是从微观上的探求,浅出是在宏观上的把握。没有微观上的探求何谈科研,没有宏观上的掌舵可能越走越偏离正确的道路,其实宏微观是相对的在不同情况下其界线是变化的。当然一切要在十年如一日地不断突破问题和瓶颈难关的前题下在不断攀登科学高峰的基础上才谈得上,否则,就是决定现象、结构、性质等的原因和条件等到了凸现的程度仍是看不到或因生疏陌生的要认识的东西仍太多仍焦头烂额而顾及不到

美国大学联盟主席杨祖佑院士只问耕耘,不问收获。坚持这样做,自然会有收获。确实如此,如哈密顿图的不问收获,还因为没有二十年奋斗就不会有收获,如对一个图论专家的评价是“他是有着广泛研究兴趣的数学家,其工作源于他对庞大的图论、组合论特别是圈结构图体系及方法的深刻理解,他精通许多有助于其研究工作的强有力的数学工具”。记得许多诺贝尔奖获得者都认同往往一些现在看来枯燥无用的领域,在将来会比一些看上去很漂亮的方向更加有意义”。当然,总有些学科不论怎么做也领导不了世界潮流,但诺贝尔奖获得者说的“一些枯燥无用的领域”“将来更加有意义”是有许多历史事例的。考虑到这里权威说40岁的爱因斯坦的脑袋已经不行,行的脑袋是做相对论的26岁左右时的”,则不要在找寻找和选择中使青春年华流失。虽然中央电视台的星光大道或这里网页的最后一段几十个中小学文化程度却都成为世界水稻玉米大师的可能并不太适用于科学,但部分道理是相通的,一些选手和这些中小学文化程度的是经过十几或几十年刻苦磨练的。因此若认准了,就不要做太多的改变,只有长年始终如一地坚持奋斗,才有可能向前推进(记得爱因斯坦赞居里夫人的可贵品质时说到“一旦她认定了一条路是正确的,她就坚定地走下去,决不改变”)。

返回琼州大学数学与信息科学研究所主页

附世界各国著名的若干哈密顿图综述文章

Gould主席,Updating the hamiltonian problem - a survey, J. Graph Theory 15 (1991), no. 2, 121--157.(全方位综述)

Gould主席,Advances on the hamiltonian problem: A survey, Graphs Combin. 19 (2003), no. 1, 7--52. (全方位综述)

Faudree校长等,Claw-free graphs---a surveyDiscrete Math. 164 (1997), no. 1-3, 87--147. Claw-free graphs

Faudree校长,Survey of results on k-ordered graphs. Discrete Math. 229 (2001), no. 1-3, 73--87.k-ordered graphs

WitteGallian主席等,A survey: Hamiltonian cycles in Cayley graphs. Discrete Math. 51 (1984), no. 3, 293--304.Cayley graphs

Gallian主席等,Hamiltonian cycles and paths in Cayley graphs and digraphs---a survey. Discrete Math. 156 (1996), 1--18(Cayley graphs)

BondyBasic graph theory: paths and circuits. Handbook of combinatorics, Vol. 1, 2, 3--110, Elsevier, Amsterdam, 1995

BondyHamilton cycles in graphs and digraphs. (Florida Atlantic Univ.,, 1978), pp. 3--28, Congress. Numer.,

BondyKotzig's conjecture on generalized friendship graphs---a survey. Cycles in graphs ( 1982), 351--366,Kotzig's Conjecture

Jung On maximal circuits in finite graphs. Ann. Discrete Math. 3 (1978), 129—144 (这篇论文还是得到Jung教授亲自邮寄来给我,没办法,早期的论文实在不好找Jung1962年博士毕业后一直在柏林工业大学任教,他是这些综述文章作者中综合资格最硬的;现任国际数学联盟2号人物、一直也从事哈密顿图工作的Grötschel1977年博士毕业后不久就一直在柏林工业大学任教;现任德国数学会主席图论组合学专家Ziegler1987年博士毕业后也一直在这大学任教。一群一群地成长这应不是偶然,足见做为图论家长的Jung的能量)

  Bauer等,Toughness in graphs---a survey. Graphs Combin. 22 (2006), no. 1, 1--35.Tough graphs

BroersmaOn some intriguing problems in Hamiltonian graph theory---a survey. Discrete Math. 251 (2002), 47--69(Regular and tough graphs)

Ryjacek校长等 Closure concepts: a survey. Graphs Combin. 16 (2000), no. 1, 17--48.Closure concepts

Bang-JensenPaths, trees and cycles in tournaments. Surveys in graph theory  Congr. Numer. 115 (1996), 131--170 tournaments

Hakimi Schmeichel Graphs and their degree sequences: a survey(度序列)

LesniakNeighborhood unions and graphical properties.. Vol. 2  783--800, New York, 1991.(邻域并)

Dean, Knickerbocker Lock等,.A survey of graphs Hamiltonian-connected from a vertex. Vol. 1  297--313, New York, 1991(哈密顿连通图)

Mitchem SchmeichelPancyclic and bipancyclic graphs---a survey., 271--278,  New York, 1985(泛圈图)

BermondThomassen等,Cycles in digraphs---a survey. J. Graph Theory 5 (1981), no. 1, 1--43.digraphs

Kawarabayashi, A survey on Hamiltonian cycles. Interdiscip. Inform. Sci. 7 (2001), no. 1, 25—39

朱永津老师,A survey of the research on the Hamilton problem in graph theory. Qufu Shiyuan Xuebao 1983, no. 4, 1--7.

相关领域的Jin Akiyama, Mikio Kano, Factors and factorizations of graphs—a survey. J. Graph Theory 9 (1985), no. 1, 1--42.Jin Akiyama, Mikio Kano, Factors and factorizations of graphs. Lecture Notes in Mathematics, 2031. Springer, Heidelberg, 2011. xii+353 pp,等等

Other network graphs: Cubes(hyper, crossed et al.), Star graphs (arrangement et al.), Some types of product graphs(Cartsian et al.); Cayley graphs et al.

还有一篇较早的综述,就是中科大博士导师徐明俊教授列给他的学生研读的第“7)”节的J. C. Bermond, Hamiltonian graphs. Selected Topics in Graph Theory , I, (edited by L. W. Beineke, and R. J. Wilson),  Academic Press INC, 1978, 127- 167。(田丰秘书长和张莲珠教授的上面1991年的综述文章的开篇第一行中就仅列出Gould主席的上面当时还没有出版1991年的第1篇综述文章和Bermond,的这篇arXiv,  Nikoghosyan,  Disc Math Graph Theory

图论在工程技术中应用的若干有影响的专著

1邓小平布什总统等多次接见的陈树柏院士担任主编、听他讲座的中科院左垲教授安徽大学校长张良震2人任副主编的名著《网络图论及其应用, 科学出版社, 1982.(本书中一特别史料是说这篇李和杨的论文中中国最先获得诺贝尔奖的“李政道和杨振宁提出应用图论研究量子统计力学”,我一直遗憾的是因没有经费,我一直不能购买这篇论文及相关论文来看一下。本书之严谨如舒贤林校长、许珠教授、卢开澄教授、李瀚荪理事长、黄汝激教授、李育珍教授、赵永昌教授、申石虎教授分别审阅各章,书中还说他被邀请来中科院做以这书名为题的专题报告和其后汇成本书都得到中科院副院长钱三强等的支持。并说下面伊利诺大学陈惠开教授提有向图、普度大学林本铭教授提供流图、伯克莱分校葛守仁教授提供应用资料,并历时2年写成--那向现在的书大学生都能下载来修改几天就成自已的,我购买的是1984年科学出版社第二次印刷的560页精装本陈树柏院士的几本图论著作在我国改革开放早期对我国确实有一定的影响,他创办并担任首届校长的美国加州国际科技大学也是华人创办的美国第一所有资格授予博士学位的大学,由于他的国际影响力,该校“所聘教授都是世界第一流的学者、专家,不是院士就是某专业权威,阵容鼎盛,实力强劲”,被誉为“华人之光”,但说是美国著名十大华人科学家之一可能是来自这书《走近大师---12位科学家的美丽人生》所写之一是陈树柏院士,此书并得到北京大学校长丁石孙说希望这本书的出版能够对读者有所启迪, 特别是对年轻的同志有所帮助,但写12个人是作者的偏好并不就代表美国十大华人科学家,不论如何,智者见智。可参考美国加州大学樊畿大师的博士袁传宽教授的既写华罗庚大师也写陈树柏院士的文章。但陈树柏院士退下只任退休校长后,他的继任者们虽然常和北大清华等世界各地大学合作但合作似乎更多的是表面形式不如以前得到从各国世界级学者到中央领导的支持。在这里最后一段胡耀邦总书记也曾代表党中央邀请陈树柏院士回国创办一所新型的国际大学。在改革开放之初为促进中国科学国际化,1982年陈树柏教授在北京中国科学院主持暑期讲学班,他主编的《图论及其应用》一书为讲学班之主要教材

2全美杰出教育家IEEE迴路與系統學會主席陈惠开院士编著的《应用图论人民邮电出版社1990.12,以及《网论-网络流人民邮电出版社1992.8陈惠开院士也受担任上面美国国际科技大学副校长。这里倒数第25行东北大学说聘请了陈香梅、陈惠开邵象华130多位国内外知名学者为东北大学兼职和名誉教授东北大学这简介中只列三个世界名人陈惠开列在我国1955年的首批院士邵象华之前-居所有专家之前-足见陈惠开院士是重要,他的介绍中也说主要从事图论工作,仍任SCI杂志JCSC主编

3Swamy M.N.S 主席和Thulasiraman K副主席编著的《图、网络与算法, 左垲主译,北京:高等教育出版社,1988

4Reinschke KJ 编著的《多变量系统的图论方法, 吴启迪部长, 萧蕴诗校长 (同济大学研究生院院长) ,同济大学出版社, 1997(关于图论,瑞士博士吴启迪部长开首就说“图论在自动控制、计算机技术、系统工程等领域得到了广泛应用”)

5、冠绝20世纪其他首相的英国首相威尔逊Wilson的儿子Wilson编著的这里第四本《图论引导,Addison Wesley Longman 1996

6Henley E J , Williams R A编著的《现代工程中的图论》(Graph theory in modern engineering, New York: Academic Press ,1978

7博士论文做哈密顿树的Narsingh Deo院士的Graph Theory with Applications to Engineering and Computer Science图论及其在工程与计算机中的应用

8Abraham Kandel院士和国际模式识别学会主席Horst BunkeMark LastApplied Graph Theory in Computer Vision and Pattern Recognition计算机视觉与模式识别中的应用图论

9Kasyanov V.N.编著的《图论编程--分类树算法, 科学出版社20061

10Johnson D E , Johnson J R编著的《图论与工程应用,孙惠泉,李先科译. 北京:人民邮电出版社, 1982

11、唐策善,《并行图论算法》,中国科学技术大学出版社,1991(因普通的计算机(即单处理器的计算机其称串行计算机)在一些重要应用中无能为力,因此,必然就需要更多的处理器的计算机其称为并行计算机。而从上面第8节后小结见图论的特性使它在并行计算机方面大有可为)

中国大学视频公开课中国大学视频公开课首批课程名单(附有美国著名公开课)第二批课程名单

关于较适合计算机系以及其它非数学系用的浅显一些的图论组合数学或离散数学教材可用中国离散数学学会第二届理事长北京大学计算机系王攻本教授等翻译的哈佛大学博士Daniel Isaac Aryeh Cohen教授的《组合理论的基本方法》(Cohen教授是美国数学会主席Gleason院士的博士。这美国主席有许多著名图论博士,如台湾徐力行教授的导师Joel Spencer。这Cohen教授现在是有20多万学生的纽约市立大学Hunter学院计算机系教授,这计算机系有5个正教授,另一正教授Christina Zamfirescu是德国亚琛工业大学Klaus Wagner大师的哈密顿图博士(这Klaus Wagner大师还有2个博士是我们所熟悉的哈密顿图权威:这2个博士就是这里第5行的哈密顿图世界权威Heinz A. Jung教授和创造一类哈密顿图-Halin graph的权威Rudolf Halin教授),纽约还有一个州立大学系统)。非数学专业的图论组合或离散数学课程也可参考北京大学计算机系3个博士导师袁崇义屈婉玲 、王捍贫 等翻译的Kenneth Rosen写了《离散数学及应用》(Kenneth Rosen是麻省理工学院Harold Stark院士的博士,Harold Stark院士最近和Audrey Terras合作在涉及数论等的图论新交叉学科Zeta Functions of Graphs(图的Zeta函数)取得好进展。国外主要是美国搞这图论交叉学科、而国内图论界也除了北京大学数学系副主任冯荣权教授和韩国合作的这篇有向图覆盖的Zeta函数论文外再没有人做这领域-图的Zeta函数用于计算有给定长度的所有圈的个数-包括计算最长圈和哈密顿圈的个数。现在来到三亚不仅已三流、在海南数学也已三流,琼南、三亚科学之父不仅以前是别人的现在更要很多人后也轮不到我 

和琼州大学合作多篇论文的美国十大老牌大学学术委员会主席Gould教授被多数专家公认为哈密顿图当今世界第一大师或最灸手可热的权威,如从上面见近二十年在SCI专业杂志只有两篇最综合最全面的哈密顿图综述文章且均由Gould主席独立撰写,也如1965年已在哥伦比亚大学养出博士的Gross教授最近邀请各大师编写的被世界各国奉为经典指南的《图论手册》中的哈密顿图一章就由Gould主席撰写(1985年获得哈佛大学组合学博士Gasarch也在美国计算机协会算法与计算理论分会-ACM SIGACT评论这图论手册;把书名Handbook of Graph Theory在美国数学评论搜索,见百年来仅有此图论手册,当然另一组合手册也众所周知)Gross邀请来撰写各章的作者主要是该章的最著名的代表性权威。即此手册值得参考是如除了Gould主席外,Gross自已写第一章第1节,第2节撰者Beineke1965密执根大学博士,第3节作者Wilson1968宾大博士第二章作者Aho1967普林斯顿博士,第三章是1972年普林斯顿博士Maurer,和1969年香槟分校博士Reid,还有Bollobas大师写极图Faudree校长写Ramsey  ,欧洲数学会CDC主席Fleischner主席写欧拉图,美国数学协会第一副主席Alan Tucker写完备图等Gross的博士陈建二的项目也是2003国家自然科学一等奖43个提名项目之32数学只有三个提名项目且也只有上面摘要中范更华教授的43获国家奖。陈建二的博士学位论文是线复杂性和图嵌入问题的。可见图论重要特别哈密顿圈图(即圈和路图的核心)。这次三大奖一共270项目合作单位上千个可很遗憾海南竟没有参与一项 

Gould主席在世界图论学科的影响,还有如多个排名网都列为华人第一大学台湾大学的图论教材就只用Gould主席的“图论”书。这里是Gould主席的图论教材的上一学期用书的内容下一学期用书的内容(用PDF软件可看整本书内容。Gould主席的这本书世界《图论网》上公报的最全面性的图论中的倒数第10本。倒数第2本是泰斗级大师Ore的,倒数第5本是Bondy大师的,倒数第7本是Bollobas大师的,第1本是前段Gross的,它们仅是按出版时间顺次排列,都是世界一流教材都极具研读价值)。很有缘的是我研究生毕业刚来琼州大学之初竟突然接到Gould主席打电话来给我,因而我成为国内和台港澳地区唯一得到和Gould主席合作的专家,促使我一直多方面的探究其精华发展其精髓。以和牛顿等并列为现代科学之父莱布尼茨为名的莱布尼茨实验室的网上最后段见只收录两篇图论综述文章,其中就有一篇是哈密顿图的而且是由Gould主席撰写。此综述文章收录的第一作者论文达到4篇的除上面写综述文章的BauerBondyFaudreeGouldBollobas权威专家的外还有现任国际数学联盟主席Lovasz

琼南科学中心主页