图论与组合网络研究方向成果介绍

Size: px

Start display at page:

Download "图论与组合网络研究方向成果介绍"

答贺邴
7 years ago
Views:

1 科大组合与图论专业三十五年为科大校庆五十周年而写李乔李炯生徐俊明中国科学技术大学组合与图论专业从李乔发表的第一篇论文算起, 经历了整整 35 年在这 35 年里, 逐渐形成了自己的研究特色 : 组合矩阵论和组合网络理论发表学术论文 300 余篇, 专著和教材 16 部获得 1993 年国家教委科技进步一等奖 ( 合作 ) 和 2003 年安徽省自然科学二等奖培养硕士研究生 57 名, 博士研究生 26 名, 进站博士后 5 名, 接收国内高校青年进修和访问学者 9 名回忆这段历史, 科大组合学与图论专业的创立和发展大体上分为三个阶段一创立阶段 ( ) 中国科学技术大学数学系的组合学与图论研究始于上世纪七十年代初北京大学段学复教授向曾肯成建议 : 国内可由科大牵头研究组合与图论李乔和冯克勤凭借代数方面的深厚功底开始涉及组合与图论, 在国内率先开展代数图论研究 1973 年, 李乔在中国科学技术大学学报上发表的关于偶图的极大对口是本专业第一篇学术论文随后, 李乔和冯克勤合作完成了关于树和其他图的联系矩阵图的谱性质的若干结果和论图的最大特征根 3 篇论文, 分别发表在中国科学技术大学学报 (1976,1979) 和应用数学学报 (1979) 上这些论文是国内代数图论研究最早的学术论文, 现成为此研究领域的经典论文之一在此期间, 李乔和冯克勤还从数学角度介入当时国内兴起的量子化学的图论研究, 成为国内最早开展此项研究的学者 1977 年 8 月在上海举行的全国第一次量子化学学术会议上, 李乔介绍了他与冯克勤在这方面的研究成果组合学是经典的数学分支, 被人熟知图论是组合学的一个活跃分支, 但当时数学界对它还不大了解 1977 年底, 李乔对数学系师生做了题为图论的介绍性报告他以图论语言简洁证明在任意六人中必存在三人, 要么都相识, 要么都不相识为开场, 来介绍图论, 生动有趣正是这个报告引起了不少人对图论的兴趣在此以前, 国内出版的图论教材只有李修睦于 1962 年译自法国图论专家 C.Berge 的图的理论及其应用 J.A.Bondy 和 U.S.R.Murty 的图论教科书图 1

忆这段历史, 科大组合学与图论专业的创立和发展大体上分为三个阶段一创立阶段 (1973-1985) 中国科学技术大学数学系的组合学与图论研究始于上世纪七十年代初北京大学段学复教授向曾肯成建议 : 国内可由科大牵头研究组合

2 论及其应用 (Graph Theory with Applications) 于 1976 年出版 1978 年, 由李翊神推荐, 陶懋颀从内蒙古大学调入科大他带来该书中文版油印本 ( 用铁笔和钢板, 将文字写在蜡纸上, 然后油印, 装订而成的书 ) 1978 年, 该书英文版由光华出版社作为内部材料翻印出来李乔冯克勤陶懋颀杜锡录单墫骆新华和徐俊明等人组织图论读书班, 把 Bondy 和 Murty 的图论教科书作为教材, 每人讲一到两章, 并负责做该章后的所有习题, 然后进行交流 1978 年, 李炯生调回科大数学系 1982 年, 王树禾和沈韵秋相继调入科大数学系, 涉及组合与图论此时, 科大数学系从事和涉及组合与图论研究的人数多达 9 人, 被誉为全国四大最有影响的图论研究群体之一 1979 年, 全国图论研究会在烟台成立, 选举第一届理事会, 李乔当选为理事会理事 1979 年, 北京大学段学复教授组织有限群讲习班, 李炯生和陶懋颀被邀请做专题讲座李炯生介绍了利用图论方法构造有限单群, 引起讲习班学员的极大兴趣 1980 年, 单墫编写的趣味的图论问题由上海教育出版社出版, 成为国内较早的图论入门参考书这一年, 李乔被派往美国 Wisconsin 大学 (Madison) 当访问学者, 合作导师是著名的组合矩阵论开拓者之一,R.A.Brualdi 教授, 从事组合矩阵和图论方面的研究李乔在访问期间, 与 Brualdi 教授合作, 在国际专业杂志上发表多篇有关组合矩阵论和图论学术论文 1982 年, 李乔如期回国后一方面, 他为本科生开设矩阵论八讲, 介绍组合矩阵的研究前沿另一方面继续组合矩阵论和图论方面的研究 1983 年, 李乔译自 H.J.Ryser 的组合数学由科学出版社出版, 李炯生与黄国勋合著的计数由上海教育出版社出版 1986 年, 陶懋颀李乔李炯生译自 C.Berge 的组合数学原理由上海科学技术出版社出版截至到 1984 年底, 李乔冯克勤陶懋颀李炯生杜锡录沈韵秋王树禾徐俊明等在国内外学术杂志上共发表学术论文 20 余篇, 其中李乔 12 篇直到八十年代初, 学校图书馆有关图论的图书资料非常少, 由于文革浩劫和科大下迁合肥, 部分资料丢失即使找到部分参考文献, 因阅览室狭小, 也没有复印设备 ( 数学系第一台复印机是 1983 年李翊神从美国访问回国用自己的经费购买赠送给系里的 ), 只有手工抄下文献由于地理位置的原因, 我们很难得到有关图论文献资料除了李乔在国外访问期间带回一些资料外, 陶懋颀在这方面做出许多贡献, 搞到当时流行的 Bondy 和 Murty 的图论及其应用 O. Ory 的图论和它的应用 C. Berge 的图与超图中文手抄本他利用回北京探亲机会, 去北京中科院图书馆寻找文献资料他从广西师范大学图书馆借到一本 W. T. 2

数学系 1982 年, 王树禾和沈韵秋相继调入科大数学系, 涉及组合与图论此时, 科大数学系从事和涉及组合与图论研究的人数多达 9 人, 被誉为全国四大最有影响的图论研究群体之一 1979 年, 全国图论研究会在烟台成立, 选举第一届理

3 Tutte 写的 Connectivity in Graphs (1967) 他有一句名言 : 买书不如借书, 借书不如抄书徐俊明硬是把这本书全部手抄下来了也正是这本书引导了他对图的连通度研究产生极大兴趣, 为他后来开展组合网络理论的研究奠定了基础 1983 年, 校图书馆购进著名的图论专家 R. L. Graham 的专著 Ramsey Theory (1980) 一书冯克勤李乔和单墫等组织学习班, 还是采取分人包章讲授的方法, 学习了这本书 1985 年 5 月, 在广州举行的全国组合学与图论大会上, 中国数学会理事长吴文俊代表中国数学会宣布, 中国数学会组合与图论专业委员会正式成立, 李乔任常务委员 1985 年, 陶懋颀与北京计算机学院的洪家威联合招收硕士研究生本系 80 级本科生张忠良成为他的第一个研究生, 毕业后回校任教, 从事组合与图论研究 1992 年, 他考取数学系基础专业博士研究生, 两年后公派去日本东京大学攻读博士学位 1983 年, 李乔和李炯生晋升为副教授 ( 不知什么原因, 我校那批副教授到 1985 年才由安徽省批准下来, 延误了招收研究生时间 ) 1986 年, 李乔和李炯生开始招收研究生科大数学系 81 级本科生潘群, 黄道德, 李冰和在职教员徐俊明成为他的第一批硕士研究生同时也开始进行研究生课程建设, 主要专业课程有组合学组合论选讲, 图论代数图论, 置换群与组合结构和一些参考文献等所用的教材分别是 :B.Bollabas 的组合数学 (Combinatorics), J.A.Bondy 和 U.S.R.Murty 的图论及其应用 (Graph Theory with Applications),N.L.Biggs 和 A.T.White 的置换群与组合结构 (Permutation Groups and Combinatorial Structures), 组合论选讲和代数图论分别是李乔和李炯生自己的讲稿所有课程分别由李乔和李炯生授课很可惜, 他们的讲稿至今还没有整理出版从此, 科大数学系就有了组合与图论专业, 列为应用数学二级学科范畴 1986 年 5 月, 应用数学被批准建立博士点和博士后流动站二调整阶段 ( ) 1986 年, 陶懋颀李乔李炯生译自 C.Berge 的 : 组合数学原理由上海科学技术出版社出版 1988 年, 李乔的讲稿矩阵论八讲由上海科学技术出版社出版 1989 年, 李炯生与查建国合著的线性代数由科大出版社出版 1990 年, 王树禾的图论及其算法由科大出版社出版 1991 年, 李乔的拉姆塞理论一书由湖南科技出版社出版 1993 年, 李乔的组合数学基础由高等教育出版 3

Graham 的专著 Ramsey Theory (1980) 一书冯克勤李乔和单墫等组织学习班, 还是采取分人包章讲授的方法, 学习了这本书 1985 年 5 月, 在广州举行的全国组合学与图论大会上, 中国数学会理事长吴文俊代表中国数学会宣布, 中国数

4 社出版 ( 本书第二版更名为组合学讲义, 作为十一五国家级规划教材于 2008 年在高等教育出版社出版 ) 李乔与同济大学邵嘉裕华南理工大学柳柏濂合作的研究成果组合矩阵论获得 1993 年国家教委科技进步一等奖 1987 年, 美国 Wisconsin 大学 R.A.Brualdi 教授夫妇应李乔邀请来科大访问黄道德特意请他的朋友为 Brualdi 教授篆刻了一枚牛角印章, 取名白劳迪上世纪 80 年代中期, 改革开放起步不久, 人员大流动知识结构大调整由于种种原因, 组合与图论专业组成人员也发生了变化陶懋颀和杜锡录相继调离科大, 沈韵秋去美国留学黄道德 1988 年硕士毕业留校后, 不久也留学美国去了冯克勤和单墫的主要研究方向不是组合与图论, 他们的主攻方向是数论, 但与他们在一起读书和讨论有关问题, 受益匪浅冯克勤一直关心和支持该研究方向, 为创建组合与图论专业功不可抹他任数学系主任期间, 关心年轻教师的成长, 为年轻教师的成长创造条件年轻教师没有科研经费, 系里拿出经费, 鼓励年轻教师尽可能参加国内举办的学术会议我们需要查找的资料几乎都是通过科学院图书馆复印, 其费用都由系里报销只不过履行一个小手续, 在系资料室登记一下复印材料的名字就可以了中国科学院系统科学研究所部分从事运筹学的同行在朱永津带领下从事图论研究, 也是国内最早招收图论方向研究生的单位, 他们的主要研究方向是 HAMILTON 圈 80 年代末, 从该所毕业的研究生或者受其影响的图论工作者遍布全国, 从事圈的研究, 大有席卷全国之势当时, 李乔研究的是组合矩阵论和图的极值问题, 李炯生研究的是代数图论和度序列问题, 徐俊明研究图的连通度问题怎么整合我们的研究力量, 体现我们的研究特色? 一直是该专业思考的问题图与网络有个自然的对应关系, 网络设计和分析中的许多问题可以归结图论问题因此, 图论是网络设计和分析的最有力的数学工具李乔在美国访问期间曾接触过网络中的图论问题, 并做过一些研究李乔以他敏锐洞察力, 带领徐俊明和张忠良开展组合网络理论研究与此同时, 李乔与时任计算机系主任陈国良教授联合开办讨论班, 主要成员是各自的研究生主要是研讨计算机网络中的数学问题讨论班进行了一年, 由于双方科研背景不同, 这个讨论班没有坚持下来但陈国良教授一直与我们保持密切联系, 关心和支持组合与图论专业的建设和发展他曾接收两名博士生 ( 尹建华和吕敏 ) 到他那里做博士后和两名研究生 ( 韩国文和吕敏, 后来, 韩国文留学美国 ) 去计算机系任教 1987 和 1988 年, 李乔和李炯生分别晋升为教授 1988 年, 李乔和李炯生招 4

Brualdi 教授夫妇应李乔邀请来科大访问黄道德特意请他的朋友为 Brualdi 教授篆刻了一枚牛角印章, 取名白劳迪上世纪 80 年代中期, 改革开放起步不久, 人员大流动知识结构大调整由于种种原因, 组合与图论专业组成人员也发生

5 收科大 83 级本科生蔡海亮刘念东李广兴和于渤成为本专业第二批研究生, 他们大多没有完成学业就留学去了美国和加拿大 1989 年, 由李乔教授主持申请国家自然科学基金委项目关于计算机网络的组合学研究得到批准我们完成的第一个研究工作是与堵丁柱 ( 时任美国麻省理工大学访问教授 ) 和许德标 (D. F. Hsu, 美国 Fordham 大学计算机与信息科学系教授 ) 合作, 给出了无向双环网络无限族的最优设计, 发表在 Networks (1990) 上对于有向双环网络的最优设计问题, 我们利用几何方法完成了最优双环网络的无限族一文利用这种方法构造出 69 类紧优无限族和 33 类几乎紧优无限族双环网络为完成这篇论文, 我们花了一年多时间, 仅手稿就有 100 多页此时, 科大 58 级校友刘彦佩正受 Discrete Mathematics 主编 Peter L. Hammer 的委托, 编辑一期反映中国离散数学方面的研究工作李乔将完成的文稿交给刘彦佩等了一段时间, 李乔收到 Hammer 的信, 说编辑部也接到西班牙巴塞罗那大学的 M.A.Foil 等人的类似结果的文稿, 并建议合作发表我们也见到 Foil 等人的文稿, 发现除了方法不一样外, 他们给出的方法只能找到紧优无限族, 不能找到几乎紧优无限族我们不同意合作发表, 通过万哲先 ( 时任编委 ) 推荐, 在 Discrete Applied Mathematics 上发表了一篇通讯, 全文在中国科学 (1993) 上发表了在此期间, 我们还解决了网络中其它几个问题, 分别在 Networks 和科学通报上发表初战告捷, 信心倍增后来, 我们又在中国科学上发表了两篇有关双环网的文章这三篇论文所提供的研究方法为国内从事双环网设计和分析研究奠定了基础, 成了必引论文 1990 年, 组合学研究会第四届全国大会在合肥召开会议上, 许德标做了有关网络可靠性的报告 1992 年, 许德标教授应邀请来科大作为期两星期的访问, 为我们带来许多最新参考文献资料他以 A graph-theoretical study of transmission delay and fault tolerance 为题做专题讲座, 详细介绍了网络理论中图论问题概念和研究进展来听讲座的除了本专业师生外, 还有科大计算机科学系安徽大学合肥工业大学中科院合肥分院漳州师范学院的师生, 这个讲座使我们大大开阔了眼界, 明确了组合网络的研究内容和目标 1993 年, 我们看到一本文集 Quo Vadis, Graph Theory? ( 图论向何处?) Quo Vadis 是拉丁语, 意思是 : 君往何处? 来源于波兰作家显克维支 (Henryk Sienkiwicz) 在 1859 年所作的描写罗马暴君尼禄时代的历史小说君往何处 1990 年在美国阿拉斯加 (Alaska) 大学举行国际图论讨论会, 主题是 : 图论向何处? 这本文集包括了国际图论大家 (Tuttle, Bollobas, Roberts 等 ) 为讨论会写的背 5

Hsu, 美国 Fordham 大学计算机与信息科学系教授 ) 合作, 给出了无向双环网络无限族的最优设计, 发表在 Networks (1990) 上对于有向双环网络的最优设计问题, 我们利用几何方法完成了最优双环网络的无限族一文利用这种方法构

6 景材料其中,Bollobas 在图论的未来一文的结尾时预测 : 今后二十或五十年, 图论是否会存在? 将变化吗? 如果是, 将以何种方式变化? 我相信图论的未来是灿烂光明的, 因为有太多美好的事情为它纷至沓来图论有一个极大的问题源供给漂亮自然的问题, 它还是与计算机科学非常密切的一个数学分支我们几乎没有开始发展解决我们的问题的工具, 也几乎未利用我们与计算机科学的这种亲近关系当二者均发生时, 我们将真正腾飞看到这篇文章, 我们更加坚信了图论与计算机网络理论研究的前景 1991 年, 本专业第三批研究生是科大 86 级本科生张翊和韩国文 1994 年, 学校开始对本科生实行分流培养模式,90 级本科生是这种新培养模式的第一批受益者本专业招收第四批研究生是来自科大分流的 90 级本科生吴耀琨刘宏芳,89 级杨秀文和来自安徽大学的宋梓霞除宋梓霞在李炯生指导下研究代数图论与度序列外, 其余的都在李乔名指导下研究组合网络理论这些研究生毕业后, 除吴耀琨继续读李乔的博士研究生 ( 上海交大 ) 外, 其余的都先后留学美国 1993 年, 李乔被国务院学位办公室批准为博士生导师同年, 徐俊明晋升为副教授研究项目组合学及其应用 ( ) 获国家教委博士点资助李乔为我们的研究方向起了一个很响亮的名字, 叫组合网络理论 1994 年, 李乔主持的国家自然科学基金项目组合网络理论 ( ) 获得批准, 李乔与徐俊明参加中科院国际合作项目图论在计算机通讯网络中应用 ( ) 也获得批准该项目的国外合作单位是法国国家科学研究中心 (CNRS) 信息研究实验室 (LRI), 该实验室是开展组合网络理论最早的单位之一数学系 77 级本科生李皓在中科院系统所攻读博士学位, 师从朱永津研究员, 研究图论,1986 年取得博士学位, 成为我国授予的图论界第一位博士,1993 年 5 月获得法国巴黎南大学博士导师资格和大学教授资格, 现任法国国家科学研究中心主任研究员在这两个项目支持下, 我们邀请该实验室的 D. Sotteau 和李皓教授来校访问, 李皓还被科大聘为兼职教授同时, 李乔访问了美国, 应邀参加美国的离散数学与理论计算机科学 (DIMACS) 中心举办的离散数学与理论计算机国际会议, 做了大会报告李乔和徐俊明还先后去 LRI 访问, 结识了许多国际同行, 并与他们进行了广泛的交流与合作例如, 我们与该实验室的 Sotteau 教授合作, 完成了 De Bruijn 无向图 B( 2, n) 的 2 宽直径等于它的直径 n 的研究, 发表在 Networks (1996) 上许德标曾称这是一个意想不到的结果, 因为它是至今为止发现的 2 宽直径等于它的直径唯一的一类图为了证明这个结论, 我们整整花了两年的时间 6

与计算机科学的这种亲近关系当二者均发生时, 我们将真正腾飞看到这篇文章, 我们更加坚信了图论与计算机网络理论研究的前景 1991 年, 本专业第三批研究生是科大 86 级本科生张翊和韩国文 1994 年, 学校开始对本科生实行

7 1994 年 7 月在太原举行的第八届全国图论大会上, 李乔被推选为第四届图论研究会副理事长 1995 年, 李乔开始招收博士研究生来自华南师大, 柳柏濂的硕士生李乔良成为他的第一位博士生, 从事网络理论研究李乔良现任湖南大学计算机系教授 1995 年底, 李乔调离科大去上海交通大学实际上, 他于 1996 年 6 月离开科大徐俊明负责他的几位硕士研究生的后期课程和学位论文, 开设研究生课程互连网络拓扑结构分析, 为这些研究生寻找组合网络方面的研究课题 1989 年 10 月, 骆新华被派往英国牛津大学进修, 学习随机图论回国后, 因患病不能坚持正常工作, 但他仍然乐于为数学系做些力所能及的事情他有业余摄影爱好, 现挂在系资料室墙上的老教师的肖像都是他生前拍摄的他生病住院期间, 仍保持乐观, 告诉前来看望他的同仁 : 我只不过是数学系的一支粉笔, 现在被折断了终究医治无效, 于 1998 年 11 月英年早逝三发展阶段 ( ) 李乔离开科大后, 组合和图论专业仍然保持两个研究方向李炯生主要从事组合矩阵论研究, 徐俊明主要从事组合网络理论研究 1994 年, 李炯生被聘为博士生导师, 评为中国科学院优秀教师 1997 年, 第九届全国图论大会在西安召开, 李炯生被推选为第五届图论研究会理事同年, 李炯生当选安徽省数学会第五届理事会秘书长 1999 年, 李炯生被评为安徽省科技系统先进个人 1995 和 1996 年, 李炯生分别招收了数学系 91 级的王平 92 级的罗荣何力锋潘永亮和刘云凯,94 级的杨凯 1995 年, 李炯生开始招收博士生来自安徽大学的硕士生张晓东和徐常青成为他的首批博士生 1998 年, 王平尹建华和潘永亮成为他的第二批博士生 1999 年, 范益政 ( 安徽大学委培 ) 高玉斌 ( 华北工学院委培 ) 1999 年和 2001 年, 侯耀平 ( 北京师范大学王伯英教授的博士, ) 和苗正科 ( 南京大学张克民的博士, ) 来本专业做博士后, 合作教师李炯生 2001 年, 李炯生退休,2004 年被返聘课程讲座教授, 招收博士生李红海 1997 年 9 月, 李炯生邀请国际矩阵论界知名人士 A.Berman 教授来科大作为期 14 天的讲学, 内容为完全正矩阵与完全正图听众除本专业的师生外, 还有来自安徽大学和安徽教育学院的教授和学生在这个讲习班上, 徐常青张晓东和宋梓霞也分别报告了他们自己的研究工作, 深受 Berman 教授的好评 7

1989 年 10 月, 骆新华被派往英国牛津大学进修, 学习随机图论回国后, 因患病不能坚持正常工作, 但他仍然乐于为数学系做些力所能及的事情他有业余摄影爱好, 现挂在系资料室墙上的老教师的肖像都是他生前拍摄的他生病住院期

8 这些博士生毕业后都成为组合与图论研究的重要骨干力量和学术带头人张晓东和徐常青毕业后分别去以色列 Technion-Israel 工学院做博士后, 合作导师 A.Berman 教授回国后, 张晓东受聘上海交通大学教授, 博士生导师 ; 徐常青受聘安徽大学教授 ( 现为浙江林学院教授 ) 王平现任信息安全国家重点实验室副教授高玉斌现任中北大学理学院副院长教授博士生导师范益政现任安徽大学数学与计算机科学学院副院长教授博士生导师苗正科现任徐州师范大学数学科学学院院长教授侯耀平现任湖南师范大学数学与计算机科学学院教授博士生导师尹建华毕业后在本校计算机系做博士后, 合作教师陈国良教授, 现受聘海南大学教授潘永亮在读博士学位期间获中科院院长奖, 毕业后留校任教, 副教授 1996 年以来, 李炯生主持的组合矩阵论研究课题组主要由他的研究生和博士后组成, 得到国家自然科学基金委和高校博士点基金的资助这些项目有 : 国家自然科学基金委项目组合矩阵论 ( ) 组合矩阵论和组合网络理论 ( ) 和高校博士点基金项目组合矩阵和组合网络分析 ( ) 从 1997 年到 2002 年, 共发表学术论文 63 篇主要研究组合矩阵论中国际上具有重要理论意义和应用前景的几个前沿问题 : 图的 Laplace 特征值的估计图的邻接谱及其在化学中的应用极值图论与度序列符号模式矩阵以及其它相关问题给出了图的最大次大第 k 大 Laplace 特征值的估计, 解决了 1993 年法国数学家 Delorme 提出的确定图的所有正特征值之和的最小值问题, 证明了匈牙利数学家世界数学大奖 Wolf 奖得主 Erdos,Jacbson,Lehel 提出的关于蕴含可图序列的猜想成立, 确定了各种经典 Turan 数在度序列中的变形值, 解决了 1984 年 Bannai-Ito 提出的关于精确置换群的不动点个数问题, 以及以色列数学家 Berman-Kogen 于 1992 年提出的完全正图的所有矩阵实现的分解指数集是否有缺数问题 2003 年, 李炯生及其学生们的研究成果组合矩阵论研究获安徽省自然科学二等奖组合与图论专业的另一个研究方向是组合网络理论, 这是李乔在科大一手开创的新的研究领域 1996 年, 李乔调离科大, 张忠良出国留学, 无疑对刚刚有点起色的组合网络研究造成不可弥补的损失组合网络还要不要坚持研究下去? 徐俊明一边给李炯生老师的研究生继续上互连网络拓扑结构课程, 一边坚持搜集资料和组合网络研究当时主要是双环网络和限制边连通度的研究, 先后在中国科学数学年刊和 Discrete Mathematics 发表了有关双环网络设计和限制边连通度的论文后来, 南京大学张克民教授的博士生吕长虹加盟组合网络 8 P k

数学与计算机科学学院副院长教授博士生导师苗正科现任徐州师范大学数学科学学院院长教授侯耀平现任湖南师范大学数学与计算机科学学院教授博士生导师尹建华毕业后在本校计算机系做博士后, 合作教师陈国良教授, 现受聘海

9 研究, 并合作完成有关 De Bruijn 无向图 B ( 2, d) 的 (d,2) 控制数方面的研究论文 1997 年, 美国德克萨斯州立大学达拉斯分校计算机系汪宇科教授 ( 科大数学系 84 级本科生 ) 得知我正在研究组合网络理论, 便送给我们 F. T. Leighton 的专著 Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes (1992) 和一些相关资料. 许德标教授和 Bell 实验室退休后受聘于台湾交通大学的黄光明教授也寄来一些材料这些为我们开好研究生课程互连网络拓扑结构和后来编写研究生讲义互连网络拓扑结构分析提供了宝贵的资料研究生院和理学院非常重视这门课程, 列为研究生核心课程, 并予以经费支持 1999 年, 徐俊明开始招收研究生, 徐州师范大学本科生陶颖峰是他的第一个硕士研究生 2001 年 1 月, 徐俊明被晋升为教授,4 月被聘为博士生导师 2002 年春季, 南京师范大学硕士研究生徐敏是他的第一个博士研究生 2000 年 5 月, 在南京师大举行的全国图论会议期间, 堵丁柱教授得知徐俊明在为研究生开设组合网络课程, 希望课程内容写成一本书其实, 在这期间, 徐俊明正在编写研究生教材讲义互连网络拓扑结构分析此讲义于 2000 年 7 月编写完成, 由校研究生院胶印同年, 堵丁柱教授推荐翻译成英文 Topological Structure and Analysis of Interconnection Networks, 列入他主编的系列丛书 Networks Theory and Applications, 并在 Kluwer Academic Publishers 于 2001 年出版中文专著组合网络理论得到科学出版基金资助, 列入现代数学丛书于 2007 年 6 月由科学出版社出版该书的出版, 为研究生提供了一部教材, 为网络理论研究工作者提供了一部参考书, 也为更多的人了解和开展组合网络理论研究起到了推波助澜的作用 2001 年 7 月在大连理工大学召开全国组合学与图论大会, 将全国组合学研究会和全国图论研究会正式合并成立中国组合学与图论学会, 并选举产生了首届理事会, 徐俊明被推选为理事图论也是运筹学的重要研究分支 2004 年 10 月, 中国运筹学会在青岛大学召开第七次全国代表大会在侯定丕教授和中科院胡晓东教授的推荐下, 徐俊明应邀在会上做题为网络中几个组合优化问题的特邀报告, 并当选为中国运筹学会理事 2006 年 8 月学会在南开大学召开了第二届全国组合学与图论大会, 对理事会进行调整和换届, 徐俊明继续被推选为理事 2007 年, 徐俊明获宝钢优秀教师奖 2002 年, 徐俊明招收博士研究生, 南京师范大学的硕士徐敏, 安徽大学硕士吕敏和本专业硕士朱强成为他的第一批博士生同年, 中科院范更华的博士聂晓冬 9

许德标教授和 Bell 实验室退休后受聘于台湾交通大学的黄光明教授也寄来一些材料这些为我们开好研究生课程互连网络拓扑结构和后来编写研究生讲义互连网络拓扑结构分析提供了宝贵的资料研究生院和理学院非常重视这门课

10 ( ) 和大连理工大学王天明的博士侯新民 ( ) 来本专业做博士后 2003 年, 潘向峰, 杜正中, 田方, 马美杰以及来自伊拉克的 A. A. Najim 是第二批博士研究生 2005 年, 数学系 99 级本科生 ( 科大五年制最后一届 ) 黄佳杨超和王海亮是他的第三批博士研究生 ( 硕博连读 ) 这些博士生和博士后为我们从事组合网络理论研究增加了活力, 并成为主要力量我们申请的中国科学院基金项目组合网络理论 ( ), 安徽省自然科学基金项目网络拓扑结构理论 ( ), 国家自然科学基金项目网络性能组合分析 ( ) 和网络中若干图论问题研究 ( ) 都陆续获得批准, 赢得经费保障从 1996 年到 2007 年, 组合网络研究方向发表学术论文 105 篇主要研究超大规模并行计算机实时系统的互连网络可靠性容错性和有效性中的问题和度量参数, 如 : 双环网络设计, 路由转发指数宽直径容错直径限制连通度限制容错直径泛圈性和泛连通性距离控制等给出最优双环网络的设计方法, 找到 4 紧优双环网络无限族, 建立了路由转发指数紧的界, 得到限制边原子不交定理和点可迁图限制边原子分解定理, 确定了笛卡尔乘积图的边连通度的表达式, 宽直径和容错直径紧的上界, 给出有向图限制边连通度的下界和无向图的限制边连通度等于它的线图限制点连通度的充要条件, 对一些著名的网络确定了上述参数的精确值, 讨论了宽直径和容错直径之间的关系, 解决了超立方体某些变型网络的泛圈性和泛连通性, 得到距离控制数的紧的上界这些研究成果为网络设计网络性能的定量分析和评估, 也为下一代超大规模超级计算机系统的互连网络的设计提供进一步的理论基础和依据 2008 年 3 月 19 日, 中国科学技术大学组织专家对徐俊明主持的组合网络理论研究项目进行评审与会专家一致认为 : 该项目研究成果达到国际领先水平近几年已经毕业的博士基本都在高校从事组合与图论教学和研究徐敏获博士学位后去中科院做博士后, 合作导师胡晓东研究员, 现在北京师范大学任职吕敏在读期间获中科院院长奖, 获博士学位后在科大做博士后, 合作导师陈国良院士, 现留校任教朱强获博士学位后在西安电子科技大学任副教授潘向峰获博士学位后安徽大学任副教授马美杰获博士学位后去山东大学做博士后, 合作导师刘桂真教授, 现任浙江师范大学副教授田方获博士学位后去上海财经大学任教杨超获博士学位后去中山大学任教黄佳在读期间获科大研究生最高奖求是奖, 获博士学位后留学美国明里苏达大学另外, 本专业还接收了 9 位青年进修教师和访问学者合肥师范学院郭世平 ( ); 黄山学院胡跃进 ( ); 漳州师范学院赖春晖 10

请的中国科学院基金项目组合网络理论 (2001-2003), 安徽省自然科学基金项目网络拓扑结构理论 (2002.4-2004.

11 ( ); 泉州师范学院张锦景 ( ); 池州师院姚玉平 ( ); 淮南工业学院张闺秀 ( ); 黄山学院谢歆 ( ); 广西大学范英梅 ( ); 淮南技术学院徐利民 ( ) 他们在进修期间都完成了多篇学术论文, 其中谢歆获得本专业硕士学位现在, 他们都成为本单位的学术骨干, 教授或者副教授 1999 年, 潘永亮博士毕业留校,2004 年 1 月晋升副教授 2005 年, 他主持的国家自然科学基金项目图谱理论中的若干专题 ( ) 获得批准 2004 年, 潘永亮开始招生研究生梁浩孔伟和王健梁浩和王健现已转为博士研究生潘永亮和他的研究生继续组合矩阵理论和图谱理论研究 2004 年 6 月, 侯新民博士后出站留校, 同时晋升副教授 2008 年, 他主持的国家自然科学基金项目图的控制理论及其应用研究 ( ) 获得批准指导硕士研究生曹永昌江璠丁逸陆由和李宁, 其中曹永昌转为博士研究生现在, 科大组合与图论专业由徐俊明潘永亮和侯新民组成在读博士研究生 7 名, 硕士研究生 8 名研究方向为组合矩阵论组合网络理论和图论四本科生的培养 1985 年, 科大数学系为本科生开设组合学课程起初的几年都是由李乔讲授这门课程, 他的讲稿组合学基础于 1993 年由高等教育出版社出版, 成为组合学经典教材从那以后, 组合学一直成为科大数学系本科生必修课程除李乔外, 李炯生徐俊明和潘永亮都讲授过这门课程 1983 年, 王树禾为计算机系开设图论与算法, 一直开到 1994 年以后计算机系的图论课程是他们自己的老师 ( 也是本专业毕业的研究生 ) 讲授王树禾的讲稿图论及其算法于 1990 年由科大出版社出版, 一直作为计算机系本科生教材, 深受国内计算机专业师生的好评 1993 年, 本专业为科大全校本科生开设图论及其应用课程, 向本科生普及图论知识, 并着手编写讲义选修此课程的学生最多达 150 人, 大多来自计算机科学系无线电系物理系和化学系的本科生从 1994 年开始, 数学系本科生增设图论及其应用课程徐俊明在开设此课程的基础上编写讲义这本讲义经三次试用修改, 作为科大本科生和研究生通用教材, 于 1988 年由科大出版社出版 2002 年, 该书被国家教育部推荐为全国研究生指定用书 2003 年, 该书的英文版 Theory and Application of Graphs 由 Kluwer 科学出版社出版 2004 年, 该书第二版出版, 现已经列为科大校庆 50 周年精品教材 2006, 潘永亮与徐俊明合著的教材组合数学由科学出版社出版 11

02) 他们在进修期间都完成了多篇学术论文, 其中谢歆获得本专业硕士学位现在, 他们都成为本单位的学术骨干, 教授或者副教授 1999 年, 潘永亮博士毕业留校,2004 年 1 月晋升副教授 2005 年, 他主持的国家自然科学基金项目图谱理

12 在开设图论课程的基础上, 我们还为对图论有兴趣的本科生通过选修研究生课程做毕业论文 Seminar 课程和大学生研究计划提供科研实践活动的机会, 锻炼他们的科研能力近 10 年来, 从中受益的本科生达 80 人他们不仅来自数学系, 还有少年班计算机系自动化系和无线电系这些同学不仅得到科研能力的锻炼, 其中一些还做出了很优秀的工作, 其论文在高级专业杂志上发表如 97 级少年班学生刘琦在读期间就完成了两篇高质量论文, 其中关于双环网络设计的研究论文发表在中国科学 (2003) 上, 另一篇发表在 Australasian J. Combinatorics (2004) 上由此, 他获得宝钢优秀学生奖 99 级少年班学生周涛, 计算机系颜俊和杜野通过大学生研究计划完成 4 篇学术论文,2 篇在 Ars Combinatoria 上发表,2 篇在国内核心杂志发表, 其中发表在中国科大学报 (2004) 上的论文被评为中国科学技术大学学报 2004 年度优秀论文 99 级数学系本科生杨超在本科毕业论文期间完成的笛卡尔乘积图连通度论文在 Discrete Mathematics (2006) 上发表 2003 级数学系本科生叶和溪在本科毕业论文期间完成的容错直径论文被 Discrete Mathematics (2008) 接收, 即将发表还有一些同学 ( 如沈建李展宗尹治军李雷黄佳等 ) 本科毕业论文中获得的主要结果发表在国内核心杂志上, 不一一列举五结束语科大组合与图论专业从无到有整整走过了三十五年尽管我们是白手起家, 没有名师大腕, 却已取得了很大的成绩 2007 年, 科大数学系被国家教育部批准为一级重点学科组合与图论专业参与了科大数学系的发展和学科建设, 也为之做出了应有的贡献科大组合与图论专业取得的成绩, 在于本专业师生的艰苦创业和苦心耕耘, 在于科大数学系五十年来所形成的风清人正严谨治学传帮带的优良传统和自由民主的学术氛围, 在于中国科学技术大学我创新故我在的办学理念目前, 该专业师资力量结构合理, 研究生培养体系逐步走向完善我们坚信, 科大数学系组合与图论专业将会越办越好, 取得更大的成绩借此机会, 我们诚挚感谢长期关心指导帮助和支持科大组合与图论专业建设和发展的万哲先院士陈国良院士以及各级领导和组合与图论界同仁 ; 深切怀念对本专业的创立和发展做出贡献的段学复教授曾肯成教授陶懋颀教授侯定丕教授杜锡录教授和骆新华副教授 ( 本文由徐俊明执笔 ) 12

论文发表在中国科学 (2003) 上, 另一篇发表在 Australasian J.

Erdös ? 1 2

Erdös ? 1 2 1 1 Euler Menger Kuratowski Ramsey Whitney Dirac König Tutte Erdös Menger Kuratowski Ramsey 1 Erdös 2 1 2 1? 1 2 2 3 5 5 4 2 1 3 Haray [7] Haray 2 3 2 4 1. Mathematical Review Zentralblatt MATH http://www.ams.org/mathscinet