从日本(以及亚洲)最先几批当选ACM(国际计算机协会)院士的全都是图论专家,可窥探组合图论与计算机科学的关系:
页头注:亚洲第一个ACM(国际计算机协会)院士是这里1994年当选的Liu, C. L.刘炯朗校长--他就是我们海南琼州大学曾研读他的几本组合数学图论及离散数学书籍的美国伊利诺伊大学香槟分校副校长兼台湾清华大学教授刘炯朗(即这亚洲第一个计算机院士的组合数学书就是海南的3个大学-琼州大学、海南大学、海南师大的3篇论文都参考的这里的C. L. Liu 刘炯朗的书,就是这里中下部说到的书);第2个当选院士姚期智就是第一个刘炯朗独自指导的博士并当然也做组合数学图论并姚期智更是至今唯一获得计算机诺贝尔奖的亚洲人、刚又见姚期智也获得奖金非常高的“日本诺贝尔奖”京都奖-是首位中国籍获奖者等等;第3个是日本图论专家在下面再专讲;第4个当选院士李德财校长的第一篇等论文也都是图论的--并李德财教授就是这里第一、“组合几何和计算几何”部分最后的台湾中央研究院计算机研究所所长台湾计算机学会主席中兴大学校长并2008年台湾只有他和世界医学权威台湾大学正校长杨泮池2人当选世界科学院院士-但他主编的杂志影响因子不到0.1而海南琼州大学是创刊编委的1.2或见这里第一段所指。
除了我们所熟知的上面三个华人,这页先主要讲前6位ACM(国际计算机协会)院士中的第3和第6个当选者-他俩都是日本人-并也都是图论专家:
1996年亚洲第3个当选ACM(国际计算机协会)院士的日本第一人-Takao Nishizeki可说是最正宗的世界图论权威专家(在他的个人网也看到他确实是1996年当选ACM(国际计算机协会)院士),并这个1996年亚洲第3个当选者Takao Nishizeki指导的20多个博士学位论文全都做图论,他本硕博都在Tohoku
University东北大学读(看该校“知名校友”见苏步青和陈建功2个数学大师等都在该校读)。再看这里见他的一百多篇论文几乎全部都是图论论文,最后见他写的3本书中他是第一作者的2本是平面图论的他是第2作者的是离散数学的-接着见他主编别人参于写的6本都是图论的-最后他翻译的4本书中3本是图论的另1本是美国组合数学和图论学家Herbert
S. Wilf的(我有他为第一作者的1988年出版的《Planar
Graphs: Theory and Algorithms平面图论:理论与算法》-这书最后2章分别是“Hamiltonian
cycles哈密顿圈”和“Flows in Planar Graphs平面图中的流”)
其后,1998年有一人当选-是印度人。
1999年有4人当选ACM院士--这4人中最著名的是京都大学Toshihide Ibaraki大师-即亚洲第6位有4人同当选ACM(国际计算机协会)院士但比其他三位更具国际化卓越成就的Toshihide
Ibaraki是著名图论专家,如Toshihide Ibaraki是组合图论方面的著名杂志Journal of Combinatorial Optimization(《组合最优化杂志》)的5个顾问之一(要知他是和Ronald L. Graham,Richard Karp,Alexander Schrijver,Andrew Chi-Chih Yao这4个诺贝尔奖级别的世界大师同为顾问;这个杂志的编委象第一个Sanjeev Arora虽年轻远不如顾问资深但也已是美国国家科学院院士和AAAS院士并和图论大师Shimon Even的徒孙现哈佛大学冠名教授在最近2009年合作出版《计算复杂性:现代方法》一书),Toshihide
Ibaraki曾任多个大学领导,现担任京都情报大学院大学(Kyoto
College of Graduate
Studies for Informatics)校长(他的三位副校长都是著名科学家),这大学是日本第一所计算机专业为主的大学院(中国称为研究生院) 。最近Toshihide Ibaraki和他的已成世界级图论权威的博士Hiroshi Nagamochi合写连通图论的算法方面的书籍《Algorithmic
Aspects of Graph Connectivity》(其对图论的研究特别是图论的优化问题的研究是促进计算机科学等发展的关健,即图论大多内容都是最优化的如此我也读Toshihide Ibaraki茨木俊秀校长和Masao Fukushima福岛雅夫教授合写的《最优化方法》一书-中文译者是他的博士日本东北大学曾道智教授即是中国人Dao-Zhi
Zeng).
如第2个院士姚期智的有20多个徒子徒孙远远领跑其他博士的Joan Feigenbaum的博士论文做“Product
Graphs: Some Algorithmic and Combinatorial Results乘积图论:一些算法和组合结果”,再如姚期智最近独立指导的博士论文做“Algorithms
for graph multiway partition problems图论多路划分问题的算法”的Mingyu Xiao肖鸣宇并他2009年6月-2010年7月做访问学者在日本京都大学,开启和上面第6个院士Toshihide
Ibarak校长指导的唯一博士Hiroshi Nagamochi合作很多好论文的卓有成效的合作序幕而且全部都是图论论文,下面是部分他俩最先合作的图论论文:
2011年“Further
Improvement on Maximum Independent Set in Degree-4 Graphs”
2011年“Parameterized edge dominating
set in cubic graphs”
2012年“A refined exact
algorithm for edge dominating set”,Theoret. Comput. Sci.2014年也发表。
2012年“An Improved Exact Algorithm for TSP in
Degree-4 Graphs”,
2012年“An
FPT algorithm for edge subset feedback edge set”
2013年“Exact
Algorithms for Maximum Independent Set”,
2013年“An Improved
Exact Algorithm for Undirected Feedback Vertex Set”,J. Comb. Optim.2015年也发表
2013年“Parameterized
edge dominating set in graphs with degree bounded by 3”
2013年“FPTASs for
trimming weighted trees”
2013年“Exact
Algorithms for Annotated Edge Dominating Set in Graphs with Degree Bounded by 3”
肖鸣宇在专任教师140余人的这电子科技大学计算机科学与工程学院工作但毕业不久的他看来他的图论也在计算机的引人瞩目的如此非常多领域中已得到认可--我国冠其名为中国电子科技大学那本就是以电子计算机为该校我国的支柱如“电子科技大学计算机专业创建于1956年,是我国首批建立计算机专业的高校之一”,‘2020 U.S.News全球计算机学科排名26位;计算机学科位于ESI前0.379‰,位列全球第22位’,该院的戴元顺已去担任西南交通大学计算机与人工智能学院全职正院长,那这年轻图论专家就将成常务院长“中国电子计算机”的主力--以改变为啥这么多年该校远不如姚期智教授的清华--其实啥是好-在中国做得好不如骗得好抢得好贪得好…娘希屁(如刚见“江西炫富的周劼,让世人知道上流生活如此多姿多彩”--他大伯二伯三伯仅是厅级芝麻骗猪狗官父母更仅处级狗妓官的文盲垃圾也敢井底之蛙(你把遍地留学博士当啥看客)不过伯叔似是油水岗位应查--就象这里首行说我月工资仅240元但这几十年借了很多钱“付出非常多钱等”-在五指山的2012年前几乎没吃过肉-因开创的海南科技各方面都荒芜无奈-要是象现在泛滥那何至让骗抢夺反差…)。
上面亚洲第一个ACM院士刘炯朗教授的博士中著名的除了姚期智院士外,还有最近动作频繁的从事组合优化、图论演算、电子设计自动化等的Martin Ding Fat Wong黄定发教授、特别是姚黄的师弟Jason
Cong丛京生(从事设计自动化)大有后来赶上超越之势
总之,图论在非常多学科都有广泛的应用,上面计算机仅是其中之一,如在世界上最大的学术演讲视频网中见到(Graph Theory)图论竟有3百多而数学其它学科一般是几十就不错了,就是(Operations Research)运筹学也才1百多而要知运筹学已是一个庞大包含很多学科的学会。
(刚见Manin评论说“It is a difficult book,…”的哲学类书《Triangle
of thoughts思维三角》-作者是3个数学家:诺贝尔奖得主Connes、大师Lichnerowicz和组合图论大师Schutzenberger--S的组合学博士Foata的博士有韩国牛,S的博士M. Nivat是T计算机S创办主编--Nivat的博士Flajolet是解析组合数学之父--现TCS主编是欧洲主席Spirakis-此人是哈佛组合结构博士-其导师也是组合学博士及3个有徒弟的哈佛师叔全都做组合学);附:《Computer
Systems:A Programmer's Perspective深入理解计算机系统》作者Randal E. Bryant写了很多与图论相关的论文如现在逐渐产生深远影响的早期的“Graph-Based Algorithms for Boolean Function Manipulation基于图论的布尔函数操作算法”, IEEE Trans.
Computers 35(8): 677-691 (1986) 并Randal E. Bryant是图灵奖得主姚期智院士的导师的师兄。