关于Hamiliton图(哈密顿图),点击这里最后部分见世界首富比尔×盖茨唯一合作论文的导师在世界名著《算法概论》第259页说哈密顿图是在一千多年之前已提出的问题,如此是世界最悠久的既非常艰难又有非常广泛重大的作用的问题(理工科世界第一麻省理工学院就说不做只要努力一定能成功的课题--那如此一千多年都解决不了的就更),这里倒数第23看到哈代(HardyHamiliton问题列为图学世界三大难題之首(现代Hamiliton1开拓者Gabriel Dirac的导师Richard RadoSchur和这哈代-Hardy做的博士都是组合论图论的,Gabriel Dirac的父亲爱因斯坦并居前3而其舅舅也获物理诺奖;现代Hamiliton2开拓者Ore指导出现代计算机之父计算机之母等。海南琼大的工作是探索揭示比他俩及所有科学家的更深入的实质),此问题之难如中国各省的先驱们-特别是云南的工作更基于堪称一代佳话的北京大学11才子的合作却仍…。关于命名为哈密顿图是因它是哈密顿最先做出有影响的工作且哈密顿被认为是牛顿第二,下第3段再详述

这段先简说我们哈密顿图大师Ore以及其门下出的一对男女博士-即“现代计算机之父Knuth计算机之母Hopper”。这真可谓人间一奇景!其中Ore院士是这里的1220世纪美国数学家之一的奧斯坦.奧勒(Oystein Ore)-他是近代哈密顿图(Hamilton)革命性大师。他在1926年之前在哥廷根瑞典数学所巴黎大学这三个当时的世界数学中心工作如此和希尔伯特等曾是同事。随着科学中心由欧洲向美国转移他也到耶鲁大学教授一直到1968年在耶鲁逝世Ore院士也是在颁发第一届数学诺贝尔奖国际数学家大会上几个做全大会最高规格的1小时报告的大师之一)Ore院士1936年在耶鲁大学指导出的博士Hall院士后来也成为现代组合数学奠基人(而这Ore院士协助他的博士Hall院士在1963年指导出的博士Knuth被尊称为现代计算机科学鼻祖。这里倒数第3段见这鼻祖博士论文和我导师钟集教授传授给我们的课题相同Knuth在图论的杂志发表的“The asymptotic number of geometries”等更是在Ore读博士的挪威的奥斯陆大学完成的可见极受影响)。HallKnuth师徒两人在1965年合写的《组合分析与计算机》就是奠基性工作。计算机科学鼻祖Knuth院士的关门弟子的博士学位论文又做Product Graphs积图。这计算机科学鼻祖也独立撰写《与稳定婚姻相关的组合学问题-这里是全文TEW把它列为图论的Monographs专题论著,参考名家Chvátal的网)。还有,誉为计算机之母Grace Hopper在上面哈密顿图大师Ore院士独立指导下1930年获得数学硕士、1934年获得数学博士(也见In 1934, Grace Hopper earned a Ph.D. in mathematics from Yale under the direction of Øystein Ore.或见:1934年成为耶鲁大学历史上第一位女数学博士。可见哈密顿图大师Ore院士门下完整地输出“现代计算机之父计算机之母!!!看这里也见其它很多也做哈密顿图的都获得计算机诺贝尔奖)。计算机之母Hopper就和图灵分别位居全世界IT市场十大技术伟人之第六、第八也和盖茨分居IT业十大最有远见人之才第七、第八电脑之母还是美国首个女将军美国就将最先进的导弹驱逐舰命名为“Hopper”号如此就是极平凡朴素的话都值得研究都是世界名言都成经典)。哈密顿图大师Ore院士于1968年逝世,但Ore逝世5年后仍有一个1973毕业的博士其博士学位论文也是做Traceable哈密顿路而且也随其师兄师姐同样成为计算机权威大师注:以Ore院士为名的Ore graphOre type graphOre conditionOre type conditionOre theorem等等全都是指具备这里定理1.2哈密顿图条件的图和条件--下面最后段再做一点Ore的补充介绍

哈密顿图大师Ore院士出如此多计算机先驱,很值得研究。特别是Donald Knuth博士更被誉为现代计算机科学鼻祖以及计算机大师中的大师更为奇葩(许多评论认为他的书在计算机中的地位可等同于欧几里德的《几何原本》在数学中的地位!哈密顿图之重要也如国际数学联盟主席Lovász美国科学院五人领导成员之一的Graham国际数学联盟第二号人物-秘书长Grötschel三人于2003年合作修订的《Handbook of Combinatorics》(即《组合学手册》)是组合学至高无上的圣经。其中图论一共六章中路与圈哈密顿图占一章(图论380页中哈密顿图110页)。还有上面Lovász主席Pelikán(国际数学奥林匹克数学竟赛最高分者)等编写的Discrete Mathematics-Elementary and Beyond(即《离散数学-基础和超越)的这一章仅有三节而且后两节都是哈密顿图的

和海南琼州大学赵克文合作多篇论文的美国十大名校一直设立国际性的Hall(其和琼州大学赵克文合作的Gould教授是这美国十大名校学术委员会主席等多个全校委员会主席。上面Hall院士就是把1984年至1990年逝世时为止的这段最具世界影响力的时间一直专门放在美国十大名校任教,当时Gould教授已是这大学系主任和全校学术委员会副主席。自Hall院士1990年逝世后的1993Gould一当上全校主席,就立即着手以这美国十大名校为主要发起单位设立全球性Hall)。国际组合数学与应用学会网页见Gould教授也担任这国际组合数学与应用学会主席,这更利于此奖的全球化。这是图论与组合数学界唯一最权威的世界性学会,该学会只设三个奖:即Euler奖、HallKirkman 奖(所有人的老师Euler四大数学家之一)。如1967-1996年这30年间一直在已有13人获得诺贝尔奖的贝尔实验室担任研究员的国际著名组合学家黄光明教授撰写的《组合学漫谈》的第一篇参考文献就是Hall《组合论》一书黄光明教授这篇著名文章倒数第23说:数学大师HardyHamiliton 问题等列入圖形學三大难题(这句话也见这里倒数第2页倒数第5。这2Hardy述什么是美丽的猜想Hardy等世界大师公认的这3大难题就是:美国三院院士等说是有一千多之悠久历史的Hamiliton 问题、有150悠久历史的四色问题 以及1941提出的Kelly-Ulam猜想(就因前2个问题是已经悠久历史考验非常有价值、非常挑战性问题,如此20年前我就已在Hamiliton 问题四色问题的某些方面取得战报),也就是上面三大难题中的前2个问题是一直得到世界各国权威和历史公认的最著名的2大难题(而大家都知道我这么多年一直忙“Hamilton”,可其实看这里见我1990年做Hamilton图之前就已在四色问题做出非常有意义的开拓性工作--即我当时可似划破夜空般地成为一百多年来全世界第一次发现染色类不唯一的,而这问题之划时代意义也如这领域排名三的三个最权威大师未能解决它而合作提出,但基于问题本身而非大师才使我感到我其后在这领域做再多也已无法超越此意义--现在仍如此认为它在这领域具划时代性--而为了不使自已在寻求意义的超越中迷失,如此我当时也为这学科开创“”个基本定理就鸣金收兵,认为这是最好的结局、(这里复印件也见我其后1990年完成的一篇论文的引言第一行说“著名的四色猜想等价于平面图荫度小于3”,足见我其后已想办法再从其它领域去解决四色猜想,只因后来搞哈密顿图牵制进太多精力,使得无时间去考虑更多有意义的问题)。前二大难题是已历经世纪考验的,长期以来全世界各国科学家都没有疑义它们的重要影响作用,而3个难题-即由在多个学科有建树的Stanisław Marcin Ulam和他的博士生Paul Joseph Kelly提出的重构猜想因历史短尚未经历太多历史考验即还没有演绎扩展得太多。把这Kelly-Ulam猜想列入三大难题只因确实它是一个很基本的问题同时基于部分专家如Harary'哈拉里Bondy邦迪等的结果的影响以及某些综述文章也较有影响等,特别是历史上十大数学天才之一的大数学家Erdös也证明对几乎所有的图这猜想成立等,如此对这第3难题虽有很大争议若要列出前三难题也就仅有少数几个难题够得上和它竟争。这三大难题中的四色问题也已于1976年被计算机解决,虽说也需要数学逻辑推理证明。然而对哈密顿图,就是用现有的最好计算机找仅<100个点Hamiliton 也得需要几百年因此,如果1976年之后还曾有过前二大难题并列为之首的话,那Robertson等再解决之后四色问题的队伍就已经大减了。确实,前二大难题之间虽大多数时间是哈密顿图居首,后来也曾几次一段不算短的时间内是四色问题也居首(确实,比获5个诺贝尔奖的庞加莱猜想悠久的哈密顿图可能要找到最好已不可能-只能找更好-但要找到更好中的更好可能都需要几百年-如此这里见琼州大学以前是全世界做到顶峰全面)。再注一点是已得到多数大师们公认是由Kelly Ulam共同提出的Kelly-Ulam猜想,不清楚为何国内多数人独称Ulam猜想还有国外?因Ulam是多学科的构建者(学位出物理学奖得主伊西多·拉比没有疑义的,,确实1967年诺贝尔奖获得者Hans Bethe说“氢弹被造后,很多记者开始称特勒为氢弹之父。为了历史起见,我认为这样说更精确:Ulam是父亲,因为他提供了种子;特勒是母亲,因为他“十月怀胎”。至于我,我猜我则是助产士” 。不过是否因如诺贝尔物理学奖得主伊西多·艾萨克·拉比曾经指出“这个世界没特勒的话会好得多”,如此他们都不怎么争这之父?。而他的博士生Paul Joseph Kelly一直主要专攻图论,他的学生的学生中有张存铨教授。如权威又是一说法及哈拉里早期也有一说法?还有这世界著名的数学网。如这里麻省理工Stanley院士论文称为K-U猜想是引自Bondy1977年的综述。关于哈密顿图这里刘振宏大师等也说是“三大难题之一”,“非常不容易”,也可参考台湾数学会理事长台湾大学数学系主任张镇华教授的教材。再说上面的黄光明教授:他从小就显露出多方面的天才,如黄光明教授1968年和台湾清华大学校长沈君山临时搭挡就获得世界桥牌赛亚军黄光明教授也和美国科学院副院长Ronald L. Graham院士合作多篇论文。台湾数学会理事长张镇华教授在这里倒数45行说‘黃光明教授由貝爾實驗室到交大,是大事一件。他本來要去北京大學主持應用數學’。要知道一直以来主持北京大学数学所的都是院士。这里中间见进入中国数学史的六个人就有黄光明教授--当然其它角度看可能有争议。上面提到的英国数学界领袖Hardy大师独立指导的博士生Wright也发表多篇哈密顿图论文如12等、是著名图论大师并曾是图论杂志名誉主编和1962-1976年在著名的阿伯丁大学担任了15年该大学正校长。培养出哈密顿图革命性大师的Rado也是Hardy的博士。Hardy虽不如哈拉里专攻图论但有担任15年校长的学生从事的问题等也应会使他接触关注特别还是具有百年历史长河的哈密顿图问题那列入三大难题也就可能。下面的维纳就称Hardy是他理想的导师和榜样)。世界各国多数大学以及中国科技大学徐俊明教授列给他的博士生应研读的第二本-《组合论》就是这Hall院士Gould教授当时是系主任的数学系任教时重修订的(我国4批教育部批准的数学研究生教材仅有4 ,其中的2本的作者分别是我的导师柳柏濂校长和中科大徐俊明主任---徐俊明主任之权威如他只在诺贝尔奖得主William Thurston1989年在普林斯顿大学毕业的博士胡森一人之下--中科大可不简单如数学学院5个有简介的讲师2个是国外顶尖大学2005年已毕业的博士、一个02-09在普度大学读了7年博士还有11991年已获得硕士-可他们仍仅是讲师,而高要求严标准的中科大这徐俊明教授列给他的博士生用的教学用书第一本研读书分别是李乔的《组合学讲义》和邵裕嘉的《组合数学》著作。如此柳柏濂和李乔、邵裕嘉这三个组合论权威大师合作获得的教育部科技进步一等奖的组合学的最重要十篇论文的全部成果就全被我们琼州大学用最好方法解决) (附:上面黄光明教授1993年写的《Combinatorial Group Testing and Its Applications》非常著名一再重印。可看维基网的“group testing”的介绍--在分子生物学等许多学科都有应用。1901年获得柏林大学博士学位的Issai Schur舒尔主要从事组合学和群论工作,他的许多博士是图论许多方向的开拓者,有上面提到的人。他的1870获得柏林大学博士学位的导师Ferdinand Georg Frobenius应说是我导师柳柏濂教授获得教育部科技进步一等奖的非负矩阵论的开创者之一。上面我们琼州大学的合作者Gould主席大学的Marshall Hall大师的专著的145–146介绍他的工作

关于誉为现代计算机科学鼻祖、计算大师中大师Donald Knuth 普林斯顿大学资深教授、计算机诺贝尔奖获得者姚期智先生就Donald Knuth “几乎是唯一一个有这样的能力及学识来建立一门学科的人),而这Donald Knuth的硕士、博士学位论文都做图论与组合数学,然而他却被誉为计算机科学的一代宗师(他既是历史上计算机诺贝尔奖最年轻的获奖者、最年轻的美国科学院院士等,也是第一个获得影响仅次于计算机诺贝尔奖的以上面计算机之母命名的Hopper的人)

下面是计算机鼻祖Donald Knuth最近的图论与组合论文,除了1篇外都是独立完成的论文,可见他对图论与组合有精深的造诣

Donald E Knuth. Selected papers on discrete mathematics.(离散数学的精选结集的一些论文) CSLI Lecture Notes, 106. CSLI Publications,CSLI 出版社出版) Stanford, CA, 2003. xvi+812 pp. ISBN: 1-57586-248-4 MR2030307

Donald E Knuth. Linear probing and graphs Algorithmica 22 (1998), 4, 561--568. MR1701629

Donald E Knuth. Partitioned tensor products and their spectra. J. Algebraic Combin. (代数组合杂志)6 (1997) , 259-267 MR1456582

Donald E Knuth. The Knowlton-Graham partition problem, J. Combin. Theory Ser. A  (组合数学杂志A73 (1996), 1, 185--189. MR1367620

Donald E Knuth. Overlapping Pfaffians. The Foata Festschrift. Electron. J. Combin. (组合数学电子杂志) 3 (1996), 2, 1-13 pp. MR1392490

Donald E Knuth. Two-way rounding. SIAM J. Discrete Math. (工业与应用数学学会的离散数学杂志)8 (1995),  2, 281--290. MR1329511

Donald E Knuth. The sandwich theorem. Electron. J. Combin. (组合数学电子杂志)1 (1994) ,  1-48 MR1269161

Donald E Knuth. Leaper graphsJournal of Mathematical. Gazette (数学公报)78 (1994), 274--297

Svante Janson, Donald E Knuth, Tomasz Łuczak, Boris.Pittel, The birth of the giant component. With an introduction by the editors. Random Structures Algorithms (随机结构与算法)4 (1993), no. 3, 231--358. MR1220220

Donald E Knuth. Rajeev Motwani, Boris Pittel, Stable husbands. Random Structures Algorithms (随机结构与算法)1 (1990), no. 1, 1--14. MR1068488

Donald E Knuth. Aztec diamonds, checkerboard graphs, and spanning trees. J. Algebraic Combin. (代数组合杂志)6 (1997) ,  253-257 MR1456581

等…

这里只着重历史上最年轻的这计算机诺贝尔奖获得者Knuth院士独立完成的我认为是最有趣的上面最后篇论文,其论文标题应该译为Aztec菱形, 棋盘格图,和生成树,这样就更进一步接近知道所研究的是什么东西了?(单词Aztec可能是专有名词,不过不管是A菱形或B菱形,以论文内的定义为标准)。其mn个点集={(x,y)| 1xm,1yn}的图的边定义为若|x-x’|=1,|y-y’|=1(x,y)(x’,y’)相邻。记子ECm,n的点集为{(x,y) | x+y 是偶数}, OCm,n的点集为{(x,y) | x+y 是奇数},则子图ECm,n的点和OCm,n的点都不相邻而且它们刚好把这图划分。显然,则ECm,nOCm,n的点数分别是émn/2ù ëmn/2û。当mn是偶数时,ECm,nOCm,n同构。最先是14岁时以满分42获得国际奥林匹克数学竞赛金奖26时成为哈佛大学正教授Noam Elkies等合作的论文1和论2OC2n+1,2n+1nAztec菱形并证明OC2n+1,2n+1刚好有2n(n+1)/2完美匹配(这Noam Elkies教授很有意思,创造了很多世界第一,上面国际奥林匹克数学竞赛最年轻的满分和哈佛大学历史上最年轻的教授仅是其二。他1993年当正教授时才有十篇论文,除了发表在2个组合数学杂志,其它的都是综合杂志-或有与组合数学有关-可见组合数学助他成为哈佛大学历史上最年轻的教授)。匹配和完美匹配可以扩展为哈密顿路哈密顿圈--即是否存在包含或说经过匹配的哈密顿路和哈密顿圈?这显然是一个有意义的课题!当然是指相对于某类匹配而存在才更有意义(当然有哈密顿路和哈密顿圈就也有匹配和完美匹配,也更清楚各类匹配和完美匹配的结构和性质)。麻省理工学院Richard Stanley院士在这里猜想EC2n+1,2n+1的生成树是OC2n+1,2n+14倍。这确实是一个巧妙有趣的猜想。显然,由定义可知道内部结构是一致的,其对匹配的决定的就在于边特别是四角。如此,提出这猜想虽需要独到眼光但也很自然,这就是吸引计算机科学鼻祖Knuth用这篇论文主要证明这猜想之因吧。

2个二分图G的二部分点数为(p,q)H的二部点数为(r,s),它们的弱有向积weak direct product G´H定义为点(u,v)和点(u’,v’)相邻当且仅当uu’相邻、vv’相邻,记子图E(G,H)的点集为{(u,v)| uV(G)vV(H)是属于相对应的部分的点}, O(G,H) 的点集为{(u,v)| uV(G)vV(H)是属于相反的部分的点},由定义则显然子图E(G,H)的点和子图O(G,H)的点都不相邻,且|V(E(G,H))|=pr+qs, |V(O(G,H))|=ps+qr。也显然ECm,n=E(Pm,Pn)OCm,n=O(Pm,Pn),其中PmPn分别是点数为mn的路。Knuth证明(i):特征多项式P(E(G,H); x)P(O(G,H); x)满足P(E(G,H); x)P(O(G,H); x)=Õj=1p+qÕk=1r+s(x-mjlk)P(E(G,H); x)=x(p-q)(r-s)P(O(G,H); x);也证明(ii): P(ECm,n; x)P(OCm,n; x)满足P(ECm,n; x)P(OCm,n; x)= Õj=1mÕk=1n[x-4cos jp/(m+1)cos kp/(n+1)];和证明(iii): P(ECm,n; x)=xmn  mod 2P(OCm,n; x);并证明(v): ECm,n的生成树数是P(OCm-2,n-2; 4) OCm,n的生成树数是P(ECm-2,n-2; 4)。如此由(iii)(v),上面Stanley院士的猜想得证

现代计算机科学的鼻祖Donald Knuth-高德纳撰写的《计算机程序设计艺术》1999年底被《美国科学家》(American Scientist)杂志20世纪最佳12学术专著之一,即它与哈密顿图的第一个革命性突破者Dirac的父亲老Dirac狄拉克量子力学爱因斯坦的相对论、曼德布罗特的分形论、鲍林的化学键、.诺伊曼和摩根斯坦的博弈论、维纳的控制论、费曼的量子电动力学等并列为20世纪12最重要经典著作(现代计算机鼻祖Donald Knuth的这套书有一卷是计算机程序设计艺术,卷4A:组合算法--即组合数学算法,它的其他卷也有很多与组合数学算法有关)

被推为上帝Donald Knuth图论杂志创立者之一并任第一届编委,Knuth独立指导的最后的关门第子Feder教授的博士学位论文是做积图论,我也在2002年接到美国《数学评论》送来Feder教授为第一作者和加拿大大师、欧洲大师和一代宗师Knuth等多人合作的论文给我评论Feder教授的这篇论文的美国《数学评论》编号是:MR2033312)

Donald Knuth独立指导的高徒博士Robert Sedgewick普林斯顿大学计算机系的创始人,并也步其师Knuth以图论思想写出图算法的系列名著,其中3卷书的前期版本多年来一直被世界各地的学者广泛使用而成为享有盛名的算法畅销书 如“没有人能够将算法和数据结构解释得比Robert Sedgewick更清楚易懂了是得到公认的,那学这些课程的就不能不读他,Robert Sedgewick1988年在美国东南部第十九届组合数学与图论学术会议报告的课题就是这方面思想的名篇,此文也发表于Congr. Numer. 65 (1988), 253--259.)(Knuth的这高徒Sedgewick1990年在普林斯顿大学指导出的博士-现在香港科技大学任教授的Mordecai J. Golin的简介中就说研究领域是“组合论”,而这图算法大师Sedgewick的高徒中就只有香港科技大学的MGP网有博士并指导的八个博士中的LeungZhangTrippen等是做图论博士学位论文的,其他也是做与图论、组合论相关的学位论文的)

最后再补充介绍一点上面哈密顿图大师Ore院士:他于1924年博士毕业,3年后的1927年被美国数学会副主席、已在耶鲁大学培养了20多个数学博士的James Pierpont大师招聘到耶鲁大学任助理教授、1928年为副教授、1929年为正教授,一年一级跳,这也算是一奇观1931年为耶鲁大学最高学术教授的Sterling Professor(关于这最高荣誉,耶鲁大学历史上一共有近2百个教授获得,但数学只有美国数学会正主席Ernest Brown、诺贝尔奖获得者Benoit Mandelbrot、非标准分析奠基人Abraham RobinsonOre4。 这美国数学会副主席James Pierpont1912年前已培养20多个耶鲁大学数学博士,却不留一个在耶鲁大学而只去聘Ore)。Ore1936年又在数学界最高大会--4年一届的“国际数学家大会”,和泛函分析主要开创者巴拿赫、控制论创立者维纳等一起做最高规格的1小时报告(他俩比Ore大但也是第一次被邀请在国际数学家大会做报告)。现在,数学界奖金最高、也被认为是数学最高荣誉的奖是“阿贝尔奖”,阿贝尔也是现代数学的主要奠基人之一。而这里该国维基网上对阿贝尔的介绍6篇参考资料中的第1篇参考文章是这Ore院士撰写的阿贝尔传记《Niels Henrik Abel, Mathematician Extraordinary》即阿贝尔-非凡的数学家,确实做为阿贝尔的后代徒孙,Ore是最有资格写阿贝尔的大师之一