下面分别简介普林斯顿、哈佛、耶鲁大学的3个获得数学诺贝尔奖-Wolf并兼做哈密顿图的世界大师(Fields奖只授40岁以下-Wolf奖较匹配诺贝尔奖选人标准至今全世界仅有33获此奖-却有不少曾搞哈密顿最下面也见许多获得计算机诺贝尔奖的也涉及哈密顿图…

1Wolf获得者伟大数学家Paul Erdös1938Erdös已到普林斯顿大学,他在普林斯顿的博士J. B. Kruskal主席是一个怪才,曾在图论做出许多著名工作:如1956年得到克鲁斯卡算法Kruskal算法);Kruskal1960年再证Vázsonyi的猜想(Vázsonyi20出头时就和Erdös合作研究图论),哈密顿图权威大师Nash-Williams1963年也给出Vázsonyi猜想更简单的证明,2004Robertson和普林斯顿Seymour把结果从树推广到一般图;1963Kruskal和给我们琼州大学来信和资料的欧盟数学会主席Gyula O. H. Katona得到应用很广的KruskalKatona定理,如康内尔大学最近深化其图论型)。

     关于Erdös的世界著知性,仅与Erdös关系不大的美国奥克兰大学做的The Erdös Number Project的网页就已有百万人访问参考,那其它大学单位的…,全世界人类史上也稀有哪一个数学家…,你能想象

Erdös(中译为埃尔德什爱多士)和公元前500年的毕达哥拉斯等并列为人类历史上十大数学天才(要知,排在Erdös前面的人中最近代的康托尔1883年完成出版《集合论基础》专著后就病到了。这样,Erdös或是1883年以来最天才的人!这康托尔的集合论确实伟大,如希尔伯特赞誉康托尔的集合论是最数学天才、人类智力最高、最巨大的工作”)

众所周知,全世界科学界有个通用的Erdos数,这里最后就说:物理学家费米的Erdos=3,海森堡的Erdos=4,爱因斯坦的Erdos=2这里倒数第二段说楊振寧Erdos=4,李政道Erdos=5。其中见到丘成桐、陈省身的Erdos=2。很侥幸海南琼州大学赵克文的Erdos=2Erdos数越小表示越近Erdos,这仅为一佐料,别较真。如芝加哥大学现任校长Robert ZimmerErdos=32001年在东京大学毕业的哈佛大学生物系进化动力系统研究所研究科学家的网页最后段说感谢D. Rand帮助发现他的Erdos=4;哈佛大学计算机系Gortler教授的网页也说他的Erdos+Bacon=5 第三世界科学院院长兼巴西科学院院长、国际数学联盟主席Jacob Palis教授的Erdos number is 3,足见Erdös大师的影响力)。

Paul Erdös已于1996年逝世,但如这组织从1999年起每年都有一个Erdos纪念演讲人而且都是数学大师担任(1999年是美国科学院副院长Ronald L. Graham00年是John Conway01年是Carl Pomerance02年是Hillel Furstenberg03年是Avi Wigderson04年是Persi Diaconis05年是Béla Bollobás以及诺贝尔奖获得者William GowersEndre Szemerédi等)。除了这个组织举办的,还有如欧洲举办的有多个诺贝尔奖得主出席的他100纪念,美国主办的Erdos101岁的获奖人Enrico Bombieri1974年已获诺贝尔奖,等等。总之,世界很多国家都举办纪念,可堪比爱因斯坦的纪念

关于Erdös,国内常把他的名翻译为埃尔德什爱多士厄多斯艾狄胥埃尔笛希厄杜斯等竟然各都有成千上万WFNMC颁发的David Hilbert and Paul Erdös。关于天才,武汉大学校长齐民友所说的天才是不可培养的,是可遇而可求的在这有点道理

Paul Erdös毕业后先在英国的曼彻斯特大学等欧洲几个大学任教。随着第二次世界大战爆发Erdös1938-1939年也来到美国普林斯顿大学,1943年又在普度大学谋得职位,40年代后期和50年代Paul Erdös又回到美国普林斯顿大学

而在此早先海南琼州大学的祖师叔已把Albert Einstein(阿尔伯特•爱因斯坦)从德国聘请到美国普林斯顿,如此Paul Erdös爱因斯坦几次是普林斯顿的同事,并他俩后期在普林斯顿大学有研究图论组合数学的共同助手恩斯特·施特劳斯(Ernst Straus-见这里这个简介网页Paul Erdös和爱因斯坦的这共同助手Ernst Straus恩斯特·斯特劳斯)在这里Einstein爱因斯坦)和Erdös这两个科学巨人的科学工作特点比较(以前在数学族谱展确实见到Ernst Straus爱因斯坦合作指导的唯一的数学博士、也是爱因斯坦唯一的博士生,但现在见已把爱因斯坦从合作博士导师删除、也把他从爱因斯坦的这个博士生删除-使爱因斯坦一个博士生也没有,不过,看维基网的Albert Einstein(阿尔伯特爱因斯坦)的右上角的Influenced见最受爱因斯坦影响的1就是上面Ernst Straus,而在德国读大学时就经常向爱因斯坦请教/并其后去美国仍和爱因斯坦有过多亲密合作的“曼哈顿工程”的第一推动手-美国科学院院士奥·西拉德才仅排在3最受爱因斯坦影响的人。这里最后爱因斯坦致这助手恩斯特·斯特劳斯的珍贵历史资料,这里说恩斯特·特劳斯收藏的爱因斯坦12份手稿和33封信件)(再注:爱因斯坦没有涉及数学工作的博士生,在介绍他的维基网右上角也没有见他博士生-就如上面说只见受他影响的第一个就是这Ernst Straus(恩斯特·施特劳斯),而Ernst Straus的维基网见其主要就是研究图论的)(“曼哈顿工程”研制的原子弹194586日和9分别在日本的广岛和长崎投下。随后苏联军队8日出兵我国东北,日本天皇才终于在15日宣布无条件投降,第二次世界大战才得以结束中国才尽早从战争的灾难中得以解救出来)

广义相对论100: 看爱因斯坦如何推翻牛顿力学说把引力和相对论结合起来重组相对论的过程中爱因斯坦采用了自己的老师Hermann Minkowski提出的时空几何理论,把时间和空间结合在一起(很多几何是图论的演绎,而这爱因斯坦的老师Hermann Minkowski的几个博士中就有图论大师Dénes König,这König的唯一博士就是和下面Erdős合作里程碑性的哈密顿图论文 On maximal paths and circuits of graphsGallai--Gallai2个博士之一有下面国际数学联盟主席Lovász

世界第一报纽约时报》在Paul Erdös逝世第3天就汇集众多顶尖数学家的评价:美国科学院副院长Graham在第7段说“Erdös是本世纪最顶尖的十名数学家之一”,上面爱因斯坦的助手也是世界数学大师的Ernst Straus在第9段说“Erdös我们时代的欧拉 (“欧拉可是从古到今的四大数学家:高斯, 欧拉, 阿基米德, 牛顿之一

泰晤士报》即《The TIMES在第2段说“Erdös是最有才能的科学家”。他虽1984年才获得数学诺贝尔奖,但1981年以前我国就已大力报道他

即,Paul Erdös1913年出生在一个父母都是数学教师的家庭,他们对他进行早期教育,3岁的时候,当大家都还在沉溺于儿歌时,Paul Erdos就已经开始阅读数学书籍,中学时他常是全国数学竟赛冠军,19岁就获得数学博士学位。Erdös是一个三无人员(一无财产、二无妻小、三无固定居所),他经常从一个大学到另一个大学,从一个国家到另一个国家,从一个洲到另一个洲,拜访了一位又一位数学家,把自已提的问题分给全世界他认为最有才能的数学家去解决。不断讨论,提出问题,并解决问题。到了老年仍每日工作19个小时。在几十年间陆续写了百篇由自已提出或汇集他人问题的文章, Paul Erdös主要合作者有和我合作的Gould主席等世界权威Erdös虽已于1996年逝世,但2001年还有他为第一作者和Gould主席等合作的论文2002, 2003, 2004,2005年也有Erdös的论文到了2006仍有奥斯卡获奖影片《心灵捕手》的主角原型- Daniel J Kleitman院士Erdös合作的论文Kleitman 六十年代至今麻省理工学院培养了30多个数学博士。只因有《泰坦尼克号》挡道,使《心灵捕手》只获得一项奥斯卡奖 下面附一些关于数学奇才Paul Erdös的趣闻轶事:前中国数学会理事长王元院士等翻译的关于天才数学家Paul Erdös的传记:《我的大脑敞开了》    这里也有两本分别由Paul Hoffman写和Bruce Schechter写的介紹艾狄胥(Erdös)充滿戲劇性一生的传记    如此美国数学会副主席Rudin院士1988毕业的博士-德高望重江守礼教授放眼世界数学历史首先就推举Erdos为榜样,这就是影响我日后教学的老师   纽约哥伦比亚大学物理博士卢昌海的网页中说他将“分篇介绍数学中一些著名命题的证明。本文就是该系列的第一篇”的本文就是Erdös在博士毕业前证明而一举成名”的。物理人来评选数学成果在整个科学界的著名程度一般是客观的。这里是北京大学录用的的一些话和故事这第3Chartrand图论书中说:Erdös父母都数学教师,他4岁时已能心算四位数的乘积,高中时做为全国数学竟赛冠军,他和TuránGallai被送同一个大学数学系,19岁就获得数学博士学位。

上面奥斯卡获奖影片的主角原型-Daniel Kleitman院士独立完成并使其闻名于世1965年得到的著名定理也被琼州大学赵克文在这里的结果超越,并得到东南亚数学主席K.P.Shum教授请我发表在他的杂志。 这里Erdös Sam终于肯接纳我了,大概它认为我已经老迈不堪,不足以推翻它了!。其中“Sam”是山姆大叔的缩写, 即指美国. 他说此话是出于积怨, 不过他在科学界的号召力是不容置疑的, 如果美国太过分, 使世界科学界不瞒, 必然招致国际上的压力, 这会招来些麻烦甚至震动不可思议的是才逝世就涌现如此多神话, 可想以后, Erdös将是怎样一个神一般的人

下面是Erdős的几篇较有代表性的哈密顿图论文,其中最著名的是被琼州大学赵克文推广C-E定理。

1959Erdős和下面国际数学联盟主席Lovász的博士导师Gallai On maximal paths and circuits of graphs一文得到:若≥r(n-1)/2则是有长为r的圈;若n(n-1)/2,则图是哈密顿图。

1962ErdősRemarks on a paper of Pósa一文得到:dn/2 or mmax{(n-d2)+d2, ([(n+2)/2]2)+[(n-1)/2]2},则图是哈密顿图。

加拿大从斯坦福大学和新泽西请来担任加拿大组合优化研究首席教授的ChvátalErdős1972年在 A note on Hamiltonian circuits一文得到著名结果:ak,则图是哈密顿图。 (该网页介绍说: 每年投入3亿美元当时可是相当于约30亿人民币Chvátal任主任的这加拿大组合优化研究中心, 以便使该国达到世界顶级研究水平)

给我来信称赞我的论文的剑桥大学Bollobas院士和Erdős1976年在Alternating Hamiltonian cycles一文研究:完全图有交替哈密顿图圈的情况。

Erdős和评价我的结果是very interesting美国大学教授协会中南区主席Arthur Hobbs教授合作多篇正则哈密顿图论文。

Erdős和高度评价我的论文并和我合作多篇论文的Gould主席也合作多篇论文。等等。

Leo Moser  An extremal problem in graph theoryOn Hamiltonian bipartite graphs宾州大学和普林斯顿大学斯坦福大学和剑桥大学

附注:关于Erdős普林斯顿指导的博士J.B Kruskal主席,他在图论学科最著名的定理是给出最小生成树的一个算法,就是Kruskal算法。他在捷克图论学家Otakar Borůvka1926年的里程碑性论文“Über ein Minimalproblem”(On a minimal problem)解决了最小树存在性和唯一性问题的以及提出怎样给出构造最小树的作法的基础上,在1956年创造这Kruskal算法(此外,Robert C. Prim1957也创造Prim算法。巧的是他俩都在50年代获得林斯顿博士,都在50年代创造最小生成树的这两个算法)

Erdős开拓许多重要的领域,其中最有影响的当推随机图

2Wolf获得者国际数学教育委员会主席哈佛大学Hassler Whitney院士

Wolf获得者Hassler Whitney院士1932年在哈佛大学获得染色图博士学位,其后Whitney院士一直在哈佛大学任教并哈佛大学培养六个的博士(其中的博士Robbins的博士Wilf是宾夕法尼亚大学图论大师,而Wilf的博士Fan-Rong Chung金芳蓉是个女中豪杰,其丈夫曾任美国数学会主席也是图论大师)。Whitney院士在1931年曾对平面三角剖分图的哈密顿性问题进行深入研究,并得到著名结果:“4连通平面三角剖分图有哈密顿圈-Annals of Math.32 (1931)378-390  Hassler Whitney院士曾任国际数学教育委员会主席美国科学促进协会副主席,他数学天分被认为是来自他的外祖父西蒙·纽康(Simon Newcomb)。这西蒙·纽康1897-1898年曾任美国数学会主席、美国科学促进协会主席,还创建了美国天文学会,并任第一任会长,等

Whitney院士的哈密顿图工作的基础上,1956现代图论奠基人Tutte院士再推进Whitney院士的上面哈密顿图结果,即Tutte院士证明名垂青史的结果4连通平面图有哈密顿圈-Trans. Amer. Math. Soc. 82 (1956), 99--116。此文也是进一步发展和完善Tutte更早十年的1946发表的On Hamiltonian circuits. J. London Math. Soc. 21, (1946). 98–101论文,他在这论文中构造一个4669弧的被称为“Tutte graph”的3连通平面图来否定Peter Guthrie Tait1884提出的猜想every 3-regular polyhedron has a Hamiltonian cycle。这也是自1884Tait猜想被提出后世界第一个否定Tait猜想的工作,即它历经62年才得到否定。不过其间得益于德国基尔住过的九个名人之一的数学家Ernst Steinitz1922年得到的3正则凸面多面体就是3连通平面图(在德国基尔任教过的诺贝尔奖获得者就有六人,而Ernst Steinitz在基尔时间并不长他在波兰出生主要在柏林工业大学、柏林大学和波兰的大学读书和任教,可见他比诺贝尔奖获得者还有名)

其后,美国数学协会主席Victor Klee院士一直花了不少精力致力于研究这问题--如看这里美国院士等专家对Klee的回忆后附的论文有多篇是多面体图的(或见1959年论文、1964d-多面体图性质、1964年多面体图直径、以及1965年和1966年多面体的路的论文等)。如此,Victor Klee席的博士论文是Polyhedral Graphs-多面体图的学生-加州大学Barnette教授在1965年还发现点数更少-38点的3连通平面非哈密顿图(大约是同一年斯洛伐克科学院正院长、捷克斯洛伐克科学院副院长Schwarz的将要毕业的博士生Juraj Bosák也发现这非哈密顿图。非常有趣的是微生物遗传学、人工智能和美国太空计划专家、生物医学诺贝尔奖获得者Lederberg也大约在这1965年也发现这非哈密顿图。关于这诺贝尔奖获得者Lederberg,他因发现了基因的同源重组而获得1958诺贝尔生理学或医学奖,他1965又和图灵奖获得者Feigenbaum等人合作,开发出了世界上第一个专家系统程序DENDRAL1965又发现的非哈密顿图

即大约同一年就有三个世界权威分别独立地发现这点数是38的平面非哈密顿图,如此这图被称为Barnette-Bosák-Lederberg,这可成为科学史上的一段佳话!也说明这哈密顿图问题在国际上受重视程度

3Wolf获得者国际数学联盟主席László Lovász院士Lovász主席在耶鲁大学指导出多个博士)

国际数学联盟主席Lovász1971年的博士学位论文是做“factors of graphs-因子图”(巴黎大学图论大师Berge院士在1958年出版的《图论的理论及其应用》教材就有2章分别讲“因子图”和“半因子图”,而2章都是讲哈密顿图,确实,哈密顿圈2-factor of graphs)。国际数学联盟主席Lovász的博士学位可能也跟着Berge大师的这2章哈密顿图的思路做。Gould主席2003年的综述文章第10页说哈密顿圈may be the most difficult 2-factor to find”。Lovász主席的简介见他做为第一作者提出的名垂青史的猜想只有一个--就是这可迁图哈密顿路图猜想:连通有限可迁图都有哈密顿路(因5-可迁图没有哈密顿圈,如此Lovász主席猜想除此外都有哈密顿圈。又因每个凯莱图都是点可迁图,如此有更弱些的猜想:每个凯莱图都有哈密顿圈。这里3László Babai却提出相反的猜想:并非凯莱图都有哈密顿圈。然而这问题之艰巨如就是要证明或否定“凯莱图有哈密顿路”甚至“有大于某长度的路”或虽阿贝尔群已有更进一步的结果如有限Abel群上围长为3,阶数至少为3的连通Cayley图是泛圈的等但对一般的群等仍是非常困难,更不用说哈密顿圈Knuth名著中说这问题来源于英国的campanology,但也似乎启蒙于Rapaport1959年的这论文。见Savage说与灰密码密切)Lovász主席还提出一些相关的著名猜想,如这杂志中提出“n连通图G的任何n条独立边集N都含在一圈中或N是奇割集”也非常著名(Lovász主席1979年证明n=3时这猜想成立ErdősGyőri证明n=4时成立Sanders证明n=5时成立;其后来信说我的证明是“确的nice”的Kawarabayashi教授最近以非凡才智用40余页长论文证明能有至多2个不相交的圈含N--虽然离解决猜想还很较远但比仅解决n=5让人似乎看到某些希望)。这里再说上面Lovász主席的凯莱图猜想:几十年来已做了很多研究,但进展不大最近哈佛大学博士PakKleitman的博士Radoicic证明:若有限群G的生成集S满足|S|log2|G|则相应的凯莱图G(G,S)有哈密顿圈。能提出这些令人头痛的猜想,确实要具备非凡的眼光,难怪Lovász主席在学生时就已是罕见的天才,如他1963-1966年连续4届获得国际数学奥林匹克竞赛奖3金奖1银、1965年和1966年连获2特别

国际数学联盟主席Lovász获得不少重要的奖,除了上面的Wolf奖获得者外,还有380万人民币的京都奖。在以现代科学之母-莱布尼茨Leibniz命名的实验室网的综述文章只有两篇,其中一篇是哈密顿图综述文章,它是Gould主席1991年撰写的,确实一直被世界各国奉为经典指南。这篇哈密顿图综述文章收入国际数学联盟主席László Lovász独立完成的论文就达4篇,还有合作的。因这篇收录一个多世纪以来出版的重要论文的哈密顿图综述文章一共才收录170篇论文,可说他的占了相当的份量!

李乔教授在他的再版新书《组合学讲义》前言中兼说组合学的前景时说“Lovász因在图论等领域的众多重大贡献而于1999年荣获用以表彰在世数学家终身成就的最高奖Wolf数学奖,他又从2007年起担任国际数学联盟的主席,国际数学联盟的秘书长则是德国组合学家Martin Grötschel

下面再附美国几个获得数学诺贝尔奖-Wolf奖的数学家:

4. Wolf获得者(2005也是 1978Fields获得者Margulis院士,发表了著名的Explicit constructions of graphs without short cycles and low density codes一文等;

5. Wolf获得者(2001ShelahGurevich院士也发表著名的Expected computation time for Hamiltonian path problem一文等。

最后,要说计算机诺贝尔奖-Turing。八十年代左右可以说是计算机时代。那时候还没有什么21世纪是海洋的世纪、生物的世纪等。而对于计算机科学,以前就普遍认为:计算机科学“成也算法,败也算法”。而众所周知国外的每本有创造性的计算机算法教材中图论的理论方法技术等占居算法的主导地位,其实图论思想的挖掘揭示和运用还很不够,而算法顶层设计的最优试金石一直被众多专家首推哈密顿图!就因计算机是死的,你得用算法告诉它做什么、怎么做,如此,计算机的智慧就取决于你的思想取决于算法而哈密顿图算法优化理论的很多技巧和方法对思想和算法的提炼、优化甚为促进基于:计算机科学是“算法的科学”,如此哈密顿图扮演很难预想的角色。就因也许哈密顿图问题是已有一千多之悠久历史的问题,还因它的大发展时期也就是算法大步向前发展时期,且一直有非常紧密的并行发展关系。谁促进谁?至少是互相促进。它的每一次突破都展示出极为的重要。在此附一些我研究生毕业之前世界各国主要以算法方面工作而获得计算机诺贝尔奖的大师:斯坦福的D. E. Knuth,哈佛的M. O. Rabin奥斯汀E. W. Dijkstra伯克莱的R. M. Karp,多伦多的S. A. Cook,普林斯顿的R. E. Tarjan,康内尔的Hopcroft,卡内基Robert W  Floyd,康内尔Juris Hartmanis,纽约奥尔巴尼Richard Stearns,其中如R. E. Tarjan许多人的算法取得重大突破是基于在哈密顿图算法的进展,如Robert E.Tarjan发表的Gauss codes, planar Hamiltonian graphs, and stack-sortable permutations一文就有非常影响   此外,最近还有计算机诺贝尔奖获得者Leonard M.Adleman通过DNA序列的方法来解决著名的NP完全性问题 Hamilton Graph等。还有这里最后段见今年获得计算机诺贝尔奖-Turing的以色列科学家Goldwasser也一直多多篇哈密顿图论文  等等。除了在计算机,在这里见哈密顿图还用于物理、化学、生物、地理甚至医学医药

返回主页