|
|
关于Hamiliton图(哈密顿图)，美国三院院士Papadimitriou(P也是这里最后部分和世界首富比尔×盖茨唯一合作论文的导师)撰写的世界名著《算法概论》第259页说哈密顿图是在一千多年之前已提出的问题--其世界性程度就如其研究人员仅国内就遍布全国,对哈密顿图的研究大有席卷全国之势 ，不仅世界重大悠久更又非常艰巨（象理工科世界第一的麻省理工学院就说“不做只要努力一定能成功的课题”）
这段先简说我们哈密顿图大师Ore以及在其门下出的一对男女博士-即“现代计算机之父Knuth”和“计算机之母Hopper”(也许是基于计算机科学“成也算法,败也算法”)。这真可谓人间一奇景！其中Ore院士是这里的12个20世纪美国数学家之一的奧斯坦.奧勒(Oystein Ore)-他是近代哈密顿图(Hamilton图)最具革命性大师。他在1926年之前在哥廷根、瑞典数学所和巴黎大学这三个当时的世界数学中心工作如此和数学之王希尔伯特等曾是同事。随着科学中心由欧洲向美国转移他也到耶鲁大学任教授--直到1968年在耶鲁逝世（Ore院士也是在颁发第一届“数学诺贝尔奖”的国际数学家大会上几个做全大会最高规格的1小时报告的大师之一）。Ore院士1936年在耶鲁大学指导出的博士Marshall Hall, Jr.院士后来也成为现代组合数学奠基人并下面见“组合数学诺贝尔奖”是以他的名来命的（Ore院士还协助这Marshall Hall,院士在1963年指导出的博士Donald E. Knuth被尊称为现代计算机科学鼻祖[Knuth不历经硕士生阶段-所以再没有其他导师起作用]。这里倒数第3段见这鼻祖的博士论文和海南琼州大学导师钟集教授传授给我们的课题相同（且是以前中国几个中心能开出的）。Knuth在加州理工学院博士毕业后留校并其后相继当上助理教授和副教授，或因加州理工学院计算机科学稍逊些如此已有2个孩子的他其后挪去加州的斯坦福大学并其间1972年-1973年去欧洲Oslo大学担任数学教授2年--这Oslo大学就是上面Knuth的导师的导师Ore攻读博士学位并其后担任助理教授的大学--并见至今2002年以前Knuth只在欧洲Oslo大学和加州这2个大学工作过（即看他的简历知他那怕再在其它大学呆上一个月一周都没有过）--那他远去欧洲却放去其它强国名校只唯一选择Oslo大学是否或因景仰追随导师的导师Ore？再其后Knuth在1974年11月11日就被授予计算机诺贝尔奖-并且至今仍是史上最年轻获奖者，更有华人唯一计算机诺贝尔奖获得者姚期智院士说“Knuth几乎是唯一一个有这样的能力及学识来建立一门学科的人。他的一系列巨著，使计算机科学成了一门科学”）。Knuth在图论组合学的杂志发表的“The asymptotic number of geometries”等的论文的作者单位都是在上面欧洲的Oslo大学-可见并非只去景仰追随还有超越。Hall和Knuth师徒两人在1965年合写的“组合分析与计算机”以及Knuth在1967年独立发表的图论成果等等就是奠基性工作。计算机科学鼻祖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 graph；Ore type graph；Ore condition；Ore type condition；Ore 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年逝世后的1993年Gould一当上全校主席，就立即着手以这美国十大名校为主要既设立该校的Hall奖也发起单位设立全球性的下面Hall奖）。看“国际组合数学及其应用协会”网页见和海南琼大合作的Gould教授也担任这国际组合数学及其应用协会副主席，这是图论与组合数学界前世纪很受崇敬的最权威的世界性学会，并这国际组合数学及其应用协会每年颁发Euler奖、Hall奖和Kirkman奖三种奖项：即Euler奖是终身成就奖、Hall奖和Kirkman奖分别授予不超过40岁和博士毕业不超过4年的杰出青年学者（其中第1个Euler是1707年生的“所有人的老师”、历史上的四大数学家之一。关于第2个Hall是1910年生的上面现代计算机科学鼻祖的导师[Hall奖授予年龄不超过40岁的杰出组合数学家就是仿照数学诺贝尔奖-菲尔兹奖]。关于第3个Kirkman是1806年生的，即设立这3个奖项时Hall和2个古人并列可见Hall之伟大。关于第3个之可名垂青史就如我国是应最熟知的或许多报导都说到“陆家羲的论文宣称，基本上解决了Steiner斯坦纳三元系的大集问题”，虽然“Kirkman科克曼三元系大集的存在问题则更为困难。可惜陆家羲因为积劳成疾而英年早逝，来不及深入研究这些工作”--可参考这领域权威专家河北师范大学学术委员会副主任康庆德教授撰写的“斯坦纳和柯克曼三元系及大集问题”等）。如1967-1996年这30年间一直在已有13人获得诺贝尔奖的贝尔实验室担任研究员的国际著名组合学家黄光明教授撰写的《组合学漫谈》的第一篇参考文献就是Hall的《组合论》一书。黄光明教授这篇著名文章倒数第23行说：数学大师Hardy把Hamiliton 圈问题等列入圖形學三大难题（这句话也见这里倒数第2页倒数第5行。这第2页见Hardy述什么是美丽的猜想。Hardy等世界大师公认的这3大难题就是：美国三院院士等说是有一千多年之悠久历史的Hamiliton 圈问题、有150年悠久历史的四色问题 以及1941年提出的Kelly-Ulam猜想（就因前2个问题是已经悠久历史考验的非常有价值、非常有挑战性问题，如此20年前我就已在Hamiliton 圈问题和四色问题的某些方面取得战报），也就是上面三大难题中的前2个问题是一直得到世界各国权威和历史公认的最著名的2大难题（而大家都知道我这么多年一直忙“Hamilton图”，可其实看这里见我1990年做Hamilton图之前就已在“四色问题”做出非常有意义的开拓性工作--即我当时可似“划破夜空”般地成为一百多年来全世界第一次发现染色类不唯一的，而这问题之划时代意义也如这领域排名前三的三个最权威大师未能解决它而合作提出，但基于问题本身而非大师才使我感到我其后在这领域做再多也已无法超越此意义--现在仍如此认为它在这领域具划时代性--而为了不使自已在寻求意义的超越中迷失，如此我当时也为这学科开创“八”个基本定理就鸣金收兵，认为这是最好的结局）、（这里复印件也见我其后1990年完成的一篇论文的引言第一行说“著名的四色猜想等价于平面图荫度小于3”，足见我其后已想办法再从其它领域去解决“四色猜想”，只因后来搞哈密顿图牵制进太多精力，使得无时间去考虑更多有意义的问题）。前二大难题是已历经世纪考验的，长期以来全世界各国科学家都没有疑义它们的重要影响作用，而第3个难题-即由在多个学科有建树的Stanisław
Marcin Ulam
关于誉为现代计算机科学鼻祖、计算机大师中大师Donald Knuth ，普林斯顿大学资深教授、计算机诺贝尔奖获得者
下面是计算机鼻祖Donald Knuth的著作和一些最近的图论与组合论文，除了1篇外都是独立完成的论文，可见他对图论与组合有精深的造诣
我以前已有Donald Knuth的“旷世巨著”前3卷包括中文版：《计算机程序设计技巧 第一卷:基本算法》、《计算机程序设计艺术 第二卷:半数值算法》(英文版)、《计算机程序设计技巧 第三卷:排序和查找》的部分内容也与下面20世纪最伟大的十大算法有关系。进入21世纪Knuth好象又出版：计算机程序设计艺术:第4卷第0册组合算法与布尔函数导论; 第4卷第A册组合数学算法; 第4卷第2册生成所有元组和置换-(这是元组组合问题-每次置换也是一次组合); 第4卷第3册生成所有组合和划分; 第4卷第4册生成所有树-组合数学生成史--所以,这5本书竟然全是组合数学的（正如这里所说:我们读研时代全世界图论学子学者必定以Bondy和Murty的图论书为第一用书而这图论书的第一章第1篇参考文献就是下面要说的图灵奖得主John
Hopcroft等的《计算机算法的设计与分析》一书、第二章第2篇参考文献就是这现代计算机科学鼻祖Donald Knuth的《计算机程序设计技巧 第三卷:排序和查找》一书）
Donald
E Knuth. Oriented subtrees of an arc
digraph. J. Combinatorial Theory 3 (1967), 309--314. MR0214511
Donald
E Knuth. Subspaces, subsets, and partitions,
J.
Combin. Theory Ser.A , 10
(1971), 178--180. MR0270933
Ronald L. Graham, Donald
E Knuth et al. Complements and transitive closures. Discrete Math. 2 (1972), 17--29. MR0323577
Nicolaas G. de Bruijn, Donald E Knuth et al. The average height of planted plane
trees. Graph theory and computing,1972, pp. 15--22. MR0505710
Robert W. Floyd, Donald E Knuth. The Bose-Nelson sorting problem. A survey of combinatorial
theory ,1973, pp.
163—172.
MR0368469
Donald
E Knuth. A generalization of Dijkstra's algorithm. Information
Processing Lett. 6 (1977), no. 1,
1--5. MR0455525 （Dijkstra's algorithm是著名的图论算法）
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
（组合数学杂志A）73 (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.
Donald E Knuth. The
sandwich theorem. Electron. J. Combin. （组合数学电子杂志）1 (1994) , 1-48 MR1269161
Donald
E Knuth. Leaper graphs，Journal 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)| 1≤x≤m,1≤y≤n}的图的边定义为若|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,n和OCm,n的点数分别是émn/2ù 和ëmn/2û。当mn是偶数时，ECm,n和OCm,n同构。最先是14岁时以满分42分获得国际奥林匹克数学竞赛金奖、26岁时成为哈佛大学正教授的Noam Elkies等合作的论文1和论文2称OC2n+1,2n+1为n阶Aztec菱形并证明OC2n+1,2n+1刚好有2n(n+1)/2完美匹配（这Noam Elkies教授很有意思，创造了很多世界第一，上面国际奥林匹克数学竞赛最年轻的满分和哈佛大学历史上最年轻的教授仅是其二。他1993年当正教授时才有十篇论文，除了发表在2个组合数学杂志，其它的都是综合杂志-或有与组合数学有关-可见组合数学助他成为哈佛大学历史上最年轻的教授）。匹配和完美匹配可以扩展为哈密顿路和哈密顿圈--即是否存在包含或说经过匹配的哈密顿路和哈密顿圈？这显然是一个更有意义的课题！当然是指相对于某类匹配而存在才更有意义（当然有哈密顿路和哈密顿圈就也有匹配和完美匹配，也更清楚各类匹配和完美匹配的结构和性质）。麻省理工学院Richard Stanley院士在这里猜想EC2n+1,2n+1的生成树是OC2n+1,2n+1的4倍。这确实是一个巧妙有趣的猜想。显然，由定义可知道内部结构是一致的，其对匹配的决定的就在于边特别是四角。如此，提出这猜想虽需要独到眼光但也很自然，这就是吸引计算机科学鼻祖Knuth用这篇论文主要证明这猜想之因吧。
记 2个二分图G的二部分点数为(p,q)、H的二部点数为(r,s)，它们的弱有向积weak
direct product G´H定义为点(u,v)和点(u’,v’)相邻当且仅当u和u’相邻、v和v’相邻，记子图E(G,H)的点集为{(u,v)| u∈V(G)和v∈V(H)是属于相对应的部分的点}, O(G,H) 的点集为{(u,v)| u∈V(G)和v∈V(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)，其中Pm和Pn分别是点数为m和n的路。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=
特别是,现代计算机科学的鼻祖Donald Knuth-高德纳撰写的上面《计算机程序设计艺术》1999年底被《美国科学家》（American
Scientist）杂志列为20世纪最佳12部学术专著之一，即它与哈密顿图的第一个革命性突破者Dirac的父亲老Dirac狄拉克的量子力学、爱因斯坦的相对论、曼德布罗特的分形论、鲍林的化学键、冯.诺伊曼和摩根斯坦的博弈论、维纳的控制论、费曼的量子电动力学等并列为20世纪12部最重要经典著作！
也被推为上帝的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的这高徒Sedgewick于1990年在普林斯顿大学指导出的博士-现在香港科技大学任教授的Mordecai J.
Golin的简介中就说研究领域是“组合论”，而这图算法大师Sedgewick的高徒中就只有这香港科技大学的在MGP网有博士并指导的八个博士中的Leung、Zhang和Trippen等是做图论博士学位论文的，其他也是做与图论、组合论相关的学位论文的）
最后再补充介绍一点上面哈密顿图大师Ore院士：他于1924年博士毕业，3年后的1927年被美国数学会副主席、已在耶鲁大学培养了20多个数学博士的James
Pierpont大师招聘到耶鲁大学