这页论述2分别获得数学、化学诺贝尔奖并也是哈佛大学所在学科最伟大科学家的工作:

  1首届国家最高科技奖得主吴文俊院士说遵从陈省身先生的建议,我开始研究惠特尼(H. Whitney)的乘积公式, 并终于得到这公式的简短证明(下面H. Whitney定理是组合学的基石,是哈佛大学的代表性经典-哈佛大学高级学者的5个博士中就有2个组合学博士分来海南大学数学系Whitney的定理也是组合学奠基人编选的《组合学经典论文》39篇中的2H. Whitney美国第一个获得不受年龄限制的全球数学界唯一最高奖Wolf奖的人(Fields奖只授予40岁以下的人Zariski完成博士后前都没到过美国-不算美国人)如此下面我给出世界大师说的最好证明:

H. Whitney的拓扑连通性定理的证明

赵克文

琼州大学数学与信息科学研究所,海南省五指山市,572200

摘要:本文给出H. Whitney定理的新证明(1932起的近百年来对这定理的证明全都用归纳法-如从较早的世界第一图论教材BondyMurty的《图论及其应用》(这书引用哈佛大学的文献也只有这一篇的这定理)到最近中科院大学副书记副校长高随祥独撰的中国科学院2本精品教材之一等全都用归纳法证明下面定理。而我下面不用归纳法的证明却更简捷。其实原证明虽引用一个定理但它的证明不算太复杂-所以本证明只算稍简捷--必竟就象下面说这样近百年来每年全世界师生都用的最经典定理的证明有进展几乎是不可能的-必要更多是出于象下面Shannon所说的不同的证明)

关键词: 拓扑路;拓扑图的连通性嵌入;H. Whitney充要条件。                                                                 

定理(H. Whitney ,1932[1][5])一个网络流是2连通的,当且仅当任两点至少有两条内部不交的拓扑路相连。

近一个世纪来世界各国的证明归纳法而较繁杂,而1993已报道不用归纳法的非常简捷漂亮的证明并得到某些国外专家的赞赏:

证明:若G2连通,却存在点u,v没有两条内部不交的路。记其中内交点数S是最少的两条路为RP,则连接这两条路上内交点两边各一点为端点的图G的路中的最短路(u’,v’)RP都不再有交点,记这两点u’,v’间的RP交点数为S’,则易知路(u’,v’)RP的部分路就可构造出u,v为端点的两条交点数=S-S’的路,矛盾。而若任何两点至少有两条内部不交的路相连,但G有割点w。则分属G-w不同分支的2点为端点的每条路都经过点w即任何2条路都有交点w,矛盾(我这证明发表在1872创刊的欧洲百年杂志。世界名著《图论导引的作者-普林斯顿大学Douglas West教授给我来信说这是最好的证明(这应是我已记不起是否我当时对他的重要成果钦佩而他顺便回复的客气话。因上面已说,这样定理证明的进展是有限-他也至多可能是看到纸面上的表达和非实质的程序少些。这书由3次当选院士候选人的李建中校长翻译,上面高随祥校长的书的前言说他主要引用的文献的前2个就是这书和上面Bondy的书)

 参考文献

1H. WhitneyNon-separable and planar graphs,Trans. Amer. Math. Soc. 34 (1932), 339–362.(这论文也是以最优等成绩从哈佛大学本科毕业的Ira Gessel近代组合学奠基人Gian-Carlo Rota组编的《组合学经典论文》39篇中的2,第1篇给Ramsey拉姆塞定理就正如李乔教授的《拉姆塞理论》引这Gian-Carlo Rota的话“假如要求在组合学中举出一个而且仅仅一个精美定理,那么大多数组合学家会提名拉姆塞定理”,1994年5月在他的著名的书上还签“赵克文同志指正”。这选编的39篇经典论文中也有开创网络流理论的下面第3篇参考文献)

有点上年代的世界第二图论教材-最丰产的现代图论之父 Harary独撰的《图论》中接着这一般化定理说:‘说来奇怪,类似于上面定理的结果直到最近才发现,就是由下面3篇论文发现的’,也正如完爆爱因斯坦媲美牛顿的C.E. Shannon等人的下面论文说他们自己的证明不同于Ford等人的2篇(即下面第34)的证(这也说明我们更完全不同又极其简捷的上面证明之意义)。

2P. EliasA. FeinsteinC.E. Shannon,A note on the maximum flow through a network, IRE Trans. Inform. Theory, 1959, 117-119.(关于这3个作者,看这页见P. Elias的博士Gallager LDPC及其博士ArikanPolar就是中国华为和美国高通在5G标准的唯一对决;而第3作者C.E. Shannon可见他完爆爱因斯坦媲美牛顿;另一作者A. Feinstein虽不如这2作者但他的导师Fano的导师Guillemin的导师Sommerfeld的诺贝尔奖学生是历史上各学科中最多的

3L. R. FordD. R. Fulkerson,Maximalflow through a network. Canadian J. Math. 8 (1956), 399--404.这篇开创网络流学科的论文仅有3篇参考文献并第2篇是上面Whitney的第1--可见海南琼州大学证明的上面定理不仅是更广泛的学科的根基也是更狭的网络流学科的直接鼻祖。正如百度说基于T. E. Harris提出的问题-使福特和富尔克森在1956年的这篇论文开创“网络流”或“网络流理论”这个学科,可参看“新加坡科技设计大学”创校校长托马斯.L.马尼安提Thomas L. Magnanti院士等人合撰的世界名著《网络流:理论、算法与应用》)。还可附点有意思的即L. R., Ford同年获得博士学位的只有最早获得国外数学博士的中国第一人-胡明复

4G. B. DantzigD. R. Fulkerson,On the max-flow min-cut theorem of networks., pp. 215--221. Ann. Math. Studies, no. 38. Princeton,1956.Dantzig是线性规划奠基人,并国际上设有以这2个人命名的奖:Fulkerson奖与Dantzig

54图灵奖得主:M. BlumR. FloydR. RivestR. Tarjan和现代计算机之父Knuth的高徒Pratt的论文Time bounds for selection, J. Comput. Sys. Sci. 1973, 7, 448-461它说明上面L. R. Ford[其后的诺奖得主姚期智的算法也同样]需要一个线性复杂度的选择算法

附注: 关于上面美国第一个数学诺贝尔奖得主H. Whitney惠特尼, 1931年在使哈佛大学数学系从三流学系到世界中心美国科学促进协会主席George Birkhoff指导下以The Coloring of Graphs(图论着色)的博士论文获得哈佛大学博士学位。载入史册参考文献第4是他导师Birkhoff主席图论着色论文, 海南琼州大学的第一篇图论文章就做图论着色, 发表在我国组合图论开创者徐利治主编的当时排名全国第二数学杂志的《数学研究与评论》. 惠特尼国际数学教育委员会主席其外祖父Newcomb曾任美国数学会主席不到30岁被林肯授他予将军 (下面附这20世纪前期美国最重要数学家Birkhoff确信图论着色极其艰难的一个故事:

H. Whitney图论工作传承于美国科学促进协会主席的他导师George Birkhoff-就如Birkhoff数学论文集第3卷图论四色问题(Vol. III: The four color problem)就有896页(并看到这卷的5个编辑都是Birkhoff的博士:他们是David Widder任编委会主席,编委由Clarence AdamsRudolph Langer、美国数学会主席Marston Morse国际数学联盟1952第一届正主席Marshall Stone等组成。他的学生都厉害,如杨振宁院士曾说“Marshall Stone加哥大学数学系的地位大大地提高了”,但还是做为美国第一个数学诺贝尔奖获得者的H. Whitney更厉害!其中Birkhoff图论代表性论文:1912年在《数学年刊》发表的这篇经典的以及后来的这篇极其著名的就如维基网说最先由Birkhoff定义等等。并图的色多项式是 Birkhoff1912年的论文中作为可能攻克四色猜想的一种手段而提出:P(G,l)=avlv+ av-1lv-1+ av-2lv-2++ a1l=i=1v aili,其中vl分别是点数和色数。

其后,正如清华大学数学系林翠琴教授的论文中说:计算图的色多项式最简单的办法是利用添加(或删去)一边和缩去一边的H. Whitney得到的递推公式P(G)=P(G+e)+P(G×e)

关于“网络流”学科,首先要参考上面新加坡校长的书以及早期的L. R. FordD. R. Fulkerson合撰的Flows in Networks,他俩的著名成果-最大流问题的Ford-Fulkerson算法以及极具独特个性的Edmonds和图灵奖得主Karp合作发展的最大流算法等等更要深入掌握;还要多看一些其它著名书籍如:和海南琼州大学合作的IEEE电路与系统学会主席Thulasiraman院士编写的世界名著《图、网络与算法》来信高度评价海南琼州大学在多方面都居国际水平的林诒勋教授的最顶级杂志论文最先参考的《线性规划与网络流》;90年代高度肯定在全世界内做得最好的是海南的宋增民理事长的书《图论与网络最优化》--这书虽出版于1990年但现在仍如被浙江省卜月华校长(他的学校仅是独立大学竟也比我们三亚海南热带海洋学院美丽-其实它下面的学院比琼大少-不过它招聘的教学人员主要是全国前3的浙江大学博士--卜月华2014年已是正校长在他下面的现任书记是市长1990年南京上海国际会议只有我和他坐同一火车再没参会的人但我只看出他一心科研,不曾料已离开数学学院多年的他也曾把华人中最国际化的朱绪鼎从台湾拉入该校做全职和1989年已获丘成桐的哈佛博士的郑方阳只排在他下面、把上面来信肯定海南琼州大学得到最好的证明的普林斯顿大学West搞成该校国家外专“千人计划”等等硬生生使仅是省级不知名的该校变成全国中心--这个视频中最先出现的是“学术大师云集千人学者为你授课“图与网络优化”入选国家111计划-如网上可见“浙江省外国专家局局长厉勇、时任校长共同为“图与网络优化”创新引智基地揭牌-这也是该校这视频中唯一夸吹的课也竟听到West中文-他在普林斯顿大学独立指导的博士Scheinerman已是排名世界第11的霍普金斯大学研究生院院长)和浙江省副理事长王维凡以及韩国吕新忠博士3人合写的书就唯一特别参考宋增民理事长的这书图灵奖得主Richard Karp哈佛师弟Eugene Lawler独著的《网络与拟阵;新加坡孙捷教授的导师Rockafellar独撰的《Network flows and monotropic optimization》;Mokhtar S. Bazaraa和其博士 Hanif D. Sherali以及 John J. Jarvis合撰的《Linear Programming and Network Flows-这里下载IEEE电路与系统学会主席陈惠开的《网论一网络流》;Te Chiang Hu撰写的《Integer programming and network flow-他和IBM高级副总裁Ralph Gomory院士合创网络流求解恰好n-1个最大流问题构造出一个流等价树。更一般的书可看“完成了第二次世界大战情报界最伟大壮举,这缩短了战争,换救了数百万人的生命…”的英国皇家学会院士Tutte撰写的《图的连通性名著等等。

从上面看到很多学科领域的最重要领袖都曾从事网络流研究,这正如从事涉及网络科学的多个领域研究的有300多院士世界最大大学党委书记校长高随祥独撰的《图论与网络流理论》一书中同意肯定上面新加坡校长的书所说“网络流问题在工程技术、计算机科学与技术、电子科学与技术、通信网络技术、工业制造、交通运输、管理科学、区域规划、物流安排、财经分析等领域有广泛的应用”,其实还如国际交叉科学家联合会主席魏冬青教授等得到我国顶级杂志《科学通报》认同接受的生物学工作“代谢网络流分析进展及应用”等等等。(关于上面近代组合数学奠基人Gian-Carlo Rota选编的《组合数学经典论文》可看到他说得到哈佛大学权威大师美国数学会正主席Andrew Gleason院士、美国数学会正主席George Andrews院士、Richard Stanley院士、David JacksonAdalbert Kerber等的关键建议,所以,不只是近代组合数学奠基人Gian-Carlo Rota个人的选编-因此值得多看这些论文)(网络流领域还应参考他和他学生包办25G标准码R. G. Gallager的论文Basic limits on protocol information in data communication networks. IEEE Trans. Information Theory IT-22 (1976), no. 4, 385—398,以及他的Finding parity in a simple broadcast network. IEEE Trans. Inform. Theory 34 (1988), no. 2, 176180,还有他和最近在人工智能很火的Bertsekas院士等的Second derivative algorithms for minimum delay distributed routing in networks. IEEE Trans. Comm. 32 (1984), no. 8, 911919,他和P. A. Humblet, P. M. Spira的论文A distributed algorithm for minimum-weight spanning trees,创建另一5G标准的R. G. Gallager的博士Erdal Arikan的论文Some complexity results about packet radio networks. IEEE Trans. Inform. Theory 30 (1984), no. 4, 681--685.等等)。

rainban.gif

2这里化学部分见:哈佛大学百年奖章的23个获得者之一、诺贝尔化学奖获得者就研究化学分子轨道图的哈密顿圈性另外,这里见图的能量在近些年非常火热复杂网络已被广泛应用

关于海南琼州大学在哈密大学化学大师方向的相关研究工作点击进入2网将看到这2个领域令整个中国非常震惊

                    p-电子总能量最小的化学分子轨道

赵克文

海南琼州大学数学与信息科学研究所,海南省五指山市,572200 

返回主页