科大组合与图论专业三十五年

科大组合与图论专业三十五年

------为科大校庆五十周年而写

李乔、李炯生、徐俊明

中国科学技术大学组合与图论专业从李乔发表的第一篇论文算起，经历了整整35年。在这35年里，逐渐形成了自己的研究特色：组合矩阵论和组合网络理论。发表学术论文300余篇，专著和教材16部。获得1993年国家教委科技进步一等奖（合作）和2003年安徽省自然科学二等奖。培养硕士研究生57名，博士研究生26名，进站博士后5名，接收国内高校青年进修和访问学者9名。

回忆这段历史，科大组合学与图论专业的创立和发展大体上分为三个阶段。

一、创立阶段（1973-1985）

中国科学技术大学数学系的组合学与图论研究始于上世纪七十年代初。北京大学段学复教授向曾肯成建议：国内可由科大牵头研究组合与图论。

李乔和冯克勤凭借代数方面的深厚功底开始涉及组合与图论，在国内率先开展代数图论研究。1973年，李乔在《中国科学技术大学学报》上发表的“关于偶图的极大对口”是本专业第一篇学术论文。随后，李乔和冯克勤合作完成了 “关于树和其他图的联系矩阵”、“图的谱性质的若干结果”和“论图的最大特征根” 3篇论文，分别发表在《中国科学技术大学学报》（1976，1979）和《应用数学学报》（1979）上。这些论文是国内代数图论研究最早的学术论文，现成为此研究领域的经典论文之一。在此期间，李乔和冯克勤还从数学角度介入当时国内兴起的“量子化学的图论研究”，成为国内最早开展此项研究的学者。1977年8月在上海举行的全国第一次量子化学学术会议上，李乔介绍了他与冯克勤在这方面的研究成果。

组合学是经典的数学分支，被人熟知。图论是组合学的一个活跃分支，但当时数学界对它还不大了解。1977年底，李乔对数学系师生做了题为《图论》的介绍性报告。他以图论语言简洁证明“在任意六人中必存在三人, 要么都相识,要么都不相识”为开场，来介绍图论，生动有趣。正是这个报告引起了不少人对图论的兴趣。

在此以前，国内出版的图论教材只有李修睦于1962年译自法国图论专家C.Berge的《图的理论及其应用》。J.A.Bondy和U.S.R.Murty的图论教科书《图

论及其应用》（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.

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-1995）

1986年，陶懋颀、李乔、李炯生译自C.Berge的：《组合数学原理》由上海科学技术出版社出版。1988年，李乔的讲稿《矩阵论八讲》由上海科学技术出版社出版。1989年，李炯生与查建国合著的《线性代数》由科大出版社出版。1990年，王树禾的《图论及其算法》由科大出版社出版。1991年，李乔的《拉姆塞理论》一书由湖南科技出版社出版。1993年，李乔的《组合数学基础》由高等教育出版

社出版(本书第二版更名为《组合学讲义》,作为“十一五”国家级规划教材于2008年在高等教育出版社出版)。李乔与同济大学邵嘉裕、华南理工大学柳柏濂合作的研究成果《组合矩阵论》获得1993年国家教委科技进步一等奖。

1987年，美国Wisconsin大学R.A.Brualdi教授夫妇应李乔邀请来科大访问。黄道德特意请他的朋友为Brualdi教授篆刻了一枚牛角印章，取名“白劳迪”。

上世纪80年代中期，改革开放起步不久，人员大流动、知识结构大调整。由于种种原因，组合与图论专业组成人员也发生了变化。陶懋颀和杜锡录相继调离科大，沈韵秋去美国留学。黄道德1988年硕士毕业留校后，不久也留学美国去了。冯克勤和单墫的主要研究方向不是组合与图论，他们的主攻方向是数论，但与他们在一起读书和讨论有关问题，受益匪浅。冯克勤一直关心和支持该研究方向，为创建组合与图论专业功不可抹。他任数学系主任期间，关心年轻教师的成长，为年轻教师的成长创造条件。年轻教师没有科研经费，系里拿出经费，鼓励年轻教师尽可能参加国内举办的学术会议。我们需要查找的资料几乎都是通过科学院图书馆复印，其费用都由系里报销。只不过履行一个小手续，在系资料室登记一下复印材料的名字就可以了。

中国科学院系统科学研究所部分从事运筹学的同行在朱永津带领下从事图论研究，也是国内最早招收图论方向研究生的单位，他们的主要研究方向是HAMILTON圈。80年代末，从该所毕业的研究生或者受其影响的图论工作者遍布全国，从事“圈的研究”，大有席卷全国之势。当时，李乔研究的是组合矩阵论和图的极值问题，李炯生研究的是代数图论和度序列问题，徐俊明研究图的连通度问题。怎么整合我们的研究力量，体现我们的研究特色？一直是该专业思考的问题。

图与网络有个自然的对应关系，网络设计和分析中的许多问题可以归结图论问题。因此，图论是网络设计和分析的最有力的数学工具。李乔在美国访问期间曾接触过网络中的图论问题，并做过一些研究。李乔以他敏锐洞察力，带领徐俊明和张忠良开展组合网络理论研究。与此同时，李乔与时任计算机系主任陈国良教授联合开办讨论班，主要成员是各自的研究生。主要是研讨计算机网络中的数学问题。讨论班进行了一年，由于双方科研背景不同，这个讨论班没有坚持下来。但陈国良教授一直与我们保持密切联系，关心和支持组合与图论专业的建设和发展。他曾接收两名博士生（尹建华和吕敏）到他那里做博士后和两名研究生（韩国文和吕敏，后来，韩国文留学美国）去计算机系任教。

1987和1988年，李乔和李炯生分别晋升为教授。1988年，李乔和李炯生招

收科大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等）为讨论会写的背

景材料。其中，Bollobas 在“图论的未来”一文的结尾时预测:“今后二十或五十年，图论是否会存在？将变化吗？如果是，将以何种方式变化? 我相信图论的未来是灿烂光明的，因为有太多美好的事情为它纷至沓来。图论有一个极大的问题源供给漂亮、自然的问题，它还是与计算机科学非常密切的一个数学分支。我们几乎没有开始发展解决我们的问题的工具，也几乎未利用我们与计算机科学的这种亲近关系。 当二者均发生时，我们将真正腾飞。”看到这篇文章，我们更加坚信了图论与计算机网络理论研究的前景。

1991年，本专业第三批研究生是科大86级本科生张翊和韩国文。1994年，学校开始对本科生实行“4-2-3分流”培养模式，90级本科生是这种新培养模式的第一批受益者。本专业招收第四批研究生是来自科大“分流”的90级本科生吴耀琨、刘宏芳，89级杨秀文和来自安徽大学的宋梓霞。除宋梓霞在李炯生指导下研究代数图论与度序列外，其余的都在李乔名指导下研究组合网络理论。这些研究生毕业后，除吴耀琨继续读李乔的博士研究生（上海交大）外，其余的都先后留学美国。

1993年，李乔被国务院学位办公室批准为博士生导师。同年，徐俊明晋升为副教授。研究项目《组合学及其应用》(1993-1995)获国家教委博士点资助。李乔为我们的研究方向起了一个很响亮的名字，叫“组合网络理论”。1994年，李乔主持的国家自然科学基金项目《组合网络理论》(1994-1996)获得批准，李乔与徐俊明参加中科院国际合作项目《图论在计算机通讯网络中应用》(1994-1996)也获得批准。该项目的国外合作单位是法国国家科学研究中心(CNRS)信息研究实验室（LRI），该实验室是开展组合网络理论最早的单位之一。数学系77级本科生李皓在中科院系统所攻读博士学位，师从朱永津研究员，研究图论，1986年取得博士学位，成为我国授予的图论界第一位博士，1993年5月获得法国巴黎南大学博士导师资格和大学教授资格，现任法国国家科学研究中心主任研究员。在这两个项目支持下，我们邀请该实验室的D. Sotteau 和李皓教授来校访问，李皓还被科大聘为兼职教授。同时，李乔访问了美国，应邀参加美国的“离散数学与理论计算机科学(DIMACS)”中心举办的离散数学与理论计算机国际会议，做了大会报告。李乔和徐俊明还先后去LRI 访问，结识了许多国际同行，并与他们进行了广泛的交流与合作。例如，我们与该实验室的Sotteau 教授合作, 完成了De Bruijn 无向图的2宽直径等于它的直径的研究，发表在《Networks》（1996）上。许德标曾称这是一个“意想不到的结果”，因为它是至今为止发现的“2宽直径等于它的直径”唯一的一类图。为了证明这个结论，我们整整花了两年的时间。 ),2(n B n

1994年7月在太原举行的第八届全国图论大会上，李乔被推选为第四届图论研究会副理事长。

1995年，李乔开始招收博士研究生。来自华南师大，柳柏濂的硕士生李乔良成为他的第一位博士生，从事网络理论研究。李乔良现任湖南大学计算机系教授。

1995年底，李乔调离科大去上海交通大学。实际上，他于1996年6月离开科大。徐俊明负责他的几位硕士研究生的后期课程和学位论文，开设研究生课程《互连网络拓扑结构分析》，为这些研究生寻找组合网络方面的研究课题。

1989年10月，骆新华被派往英国牛津大学进修，学习随机图论。回国后，因患病不能坚持正常工作，但他仍然乐于为数学系做些力所能及的事情。他有业余摄影爱好，现挂在系资料室墙上的老教师的肖像都是他生前拍摄的。他生病住院期间，仍保持乐观，告诉前来看望他的同仁：“我只不过是数学系的一支粉笔，现在被折断了。”终究医治无效，于1998年11月英年早逝。

三、发展阶段（1996-2008）

李乔离开科大后，组合和图论专业仍然保持两个研究方向。李炯生主要从事组合矩阵论研究，徐俊明主要从事组合网络理论研究。

1994年，李炯生被聘为博士生导师，评为中国科学院优秀教师。1997年，第九届全国图论大会在西安召开，李炯生被推选为第五届图论研究会理事。同年，李炯生当选安徽省数学会第五届理事会秘书长。1999年，李炯生被评为安徽省科技系统先进个人。

1995和1996年，李炯生分别招收了数学系91级的王平、92级的罗荣、何力锋、潘永亮和刘云凯，94级的杨凯。1995年，李炯生开始招收博士生。来自安徽大学的硕士生张晓东和徐常青成为他的首批博士生。1998年，王平、尹建华和潘永亮成为他的第二批博士生。1999年，范益政（安徽大学委培）、高玉斌（华北工学院委培）。1999年和2001年，侯耀平（北京师范大学王伯英教授的博士，1999.4-2001.4）和苗正科（南京大学张克民的博士，2001.3-2003.3）来本专业做博士后，合作教师李炯生。2001年，李炯生退休，2004年被返聘课程讲座教授，招收博士生李红海。

1997年9月，李炯生邀请国际矩阵论界知名人士A.Berman教授来科大作为期14天的讲学，内容为《完全正矩阵与完全正图》。听众除本专业的师生外，还有来自安徽大学和安徽教育学院的教授和学生。在这个讲习班上，徐常青、张晓东和宋梓霞也分别报告了他们自己的研究工作，深受Berman教授的好评。

这些博士生毕业后都成为组合与图论研究的重要骨干力量和学术带头人。张晓东和徐常青毕业后分别去以色列Technion-Israel 工学院做博士后，合作导师

A.Berman 教授。回国后，张晓东受聘上海交通大学教授，博士生导师；徐常青受聘安徽大学教授（现为浙江林学院教授）。王平现任信息安全国家重点实验室副教授。高玉斌现任中北大学理学院副院长、教授、博士生导师。范益政现任安徽大学数学与计算机科学学院副院长、教授、博士生导师。苗正科现任徐州师范大学数学科学学院院长、教授。侯耀平现任湖南师范大学数学与计算机科学学院教授、博士生导师。尹建华毕业后在本校计算机系做博士后，合作教师陈国良教授，现受聘海南大学教授。潘永亮在读博士学位期间获中科院院长奖，毕业后留校任教，副教授。

1996年以来，李炯生主持的组合矩阵论研究课题组主要由他的研究生和博士后组成，得到国家自然科学基金委和高校博士点基金的资助。这些项目有：国家自然科学基金委项目《组合矩阵论》（1997-1999）、《组合矩阵论和组合网络理论》（2000-2002）和高校博士点基金项目《组合矩阵和组合网络分析》(1997-1999)。从1997年到2002年，共发表学术论文63篇。主要研究组合矩阵论中国际上具有重要理论意义和应用前景的几个前沿问题：图的Laplace 特征值的估计、图的邻接谱及其在化学中的应用、极值图论与度序列、符号模式矩阵以及其它相关问题。给出了图的最大、次大、第k 大Laplace 特征值的估计，解决了1993年法国数学家Delorme 提出的确定图的所有正特征值之和的最小值问题，证明了匈牙利数学家、世界数学大奖Wolf 奖得主Erdos,Jacbson,Lehel 提出的关于蕴含可图序列的猜想成立，确定了各种经典Turan 数在度序列中的变形值，解决了1984年Bannai-Ito 提出的关于精确置换群的不动点个数问题，以及以色列数学家Berman-Kogen 于1992年提出的完全正图的所有矩阵实现的分解指数集是否有缺数问题。2003年，李炯生及其学生们的研究成果《组合矩阵论研究》获安徽省自然科学二等奖。

k P 组合与图论专业的另一个研究方向是组合网络理论，这是李乔在科大一手开创的新的研究领域。1996年，李乔调离科大，张忠良出国留学，无疑对刚刚有点起色的组合网络研究造成不可弥补的损失。组合网络还要不要坚持研究下去?徐俊明一边给李炯生老师的研究生继续上《互连网络拓扑结构》课程，一边坚持搜集资料和组合网络研究。当时主要是双环网络和限制边连通度的研究, 先后在《中国科学》、《数学年刊》和《Discrete Mathematics》发表了有关双环网络设计和限制边连通度的论文。后来，南京大学张克民教授的博士生吕长虹加盟组合网络

研究, 并合作完成有关De Bruijn 无向图的控制数方面的研究论文。

),2(d B )2,(d 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年，徐俊明招收博士研究生，南京师范大学的硕士徐敏，安徽大学硕士吕敏和本专业硕士朱强成为他的第一批博士生。同年，中科院范更华的博士聂晓冬

（2002.07-2004.06）和大连理工大学王天明的博士侯新民（2002.07-2004.06）来本专业做博士后。2003年，潘向峰，杜正中，田方，马美杰以及来自伊拉克的A. A. Najim是第二批博士研究生。2005年，数学系99级本科生（科大五年制最后一届）黄佳、杨超和王海亮是他的第三批博士研究生（硕博连读）。这些博士生和博士后为我们从事组合网络理论研究增加了活力，并成为主要力量。我们申请的中国科学院基金项目《组合网络理论》(2001-2003), 安徽省自然科学基金项目《网络拓扑结构理论》(2002.4-2004.4)，国家自然科学基金项目《网络性能组合分析》（2003-2005）和《网络中若干图论问题研究》（2007-2009）都陆续获得批准，赢得经费保障。

从1996年到2007年，组合网络研究方向发表学术论文105篇。主要研究超大规模并行计算机实时系统的互连网络可靠性、容错性和有效性中的问题和度量参数,如：双环网络设计，路由转发指数、宽直径、容错直径、限制连通度、限制容错直径、泛圈性和泛连通性、距离控制等。给出最优双环网络的设计方法，找到4紧优双环网络无限族，建立了路由转发指数紧的界，得到限制边原子不交定理和点可迁图限制边原子分解定理，确定了笛卡尔乘积图的边连通度的表达式，宽直径和容错直径紧的上界，给出有向图限制边连通度的下界和无向图的限制边连通度等于它的线图限制点连通度的充要条件，对一些著名的网络确定了上述参数的精确值，讨论了宽直径和容错直径之间的关系，解决了超立方体某些变型网络的泛圈性和泛连通性，得到距离控制数的紧的上界。这些研究成果为网络设计、网络性能的定量分析和评估，也为下一代超大规模超级计算机系统的互连网络的设计提供进一步的理论基础和依据。2008年3月19日，中国科学技术大学组织专家对徐俊明主持的《组合网络理论研究》项目进行评审。与会专家一致认为：该项目研究成果达到国际领先水平。

近几年已经毕业的博士基本都在高校从事组合与图论教学和研究。徐敏获博士学位后去中科院做博士后，合作导师胡晓东研究员，现在北京师范大学任职。吕敏在读期间获中科院院长奖，获博士学位后在科大做博士后，合作导师陈国良院士，现留校任教。朱强获博士学位后在西安电子科技大学任副教授。潘向峰获博士学位后安徽大学任副教授。马美杰获博士学位后去山东大学做博士后，合作导师刘桂真教授，现任浙江师范大学副教授。田方获博士学位后去上海财经大学任教。杨超获博士学位后去中山大学任教。黄佳在读期间获科大研究生最高奖“求是奖”，获博士学位后留学美国明里苏达大学。

另外，本专业还接收了9位青年进修教师和访问学者。合肥师范学院郭世平（1995.09-1996.07）；黄山学院胡跃进（1995.09-1996.07）；漳州师范学院赖春晖

（1996.09-1997.07）；泉州师范学院张锦景（1996.09-1997.07）；池州师院姚玉平（1999.09-2000.07）；淮南工业学院张闺秀（1999.09-2000.07）；黄山学院谢歆（2000.02-2001.01）；广西大学范英梅（2002.09-2003.07）；淮南技术学院徐利民（2005.09-2006.02）。他们在进修期间都完成了多篇学术论文，其中谢歆获得本专业硕士学位。现在，他们都成为本单位的学术骨干，教授或者副教授。

1999年，潘永亮博士毕业留校，2004年1月晋升副教授。2005年，他主持的国家自然科学基金项目《图谱理论中的若干专题》（2005-2007）获得批准。2004年，潘永亮开始招生研究生梁浩、孔伟和王健。梁浩和王健现已转为博士研究生。潘永亮和他的研究生继续组合矩阵理论和图谱理论研究。

2004年6月，侯新民博士后出站留校，同时晋升副教授。2008年，他主持的国家自然科学基金项目《图的控制理论及其应用研究》（2008-2010）获得批准。指导硕士研究生曹永昌、江璠、丁逸、陆由和李宁，其中曹永昌转为博士研究生。

现在，科大组合与图论专业由徐俊明、潘永亮和侯新民组成。在读博士研究生7名，硕士研究生8名。研究方向为组合矩阵论、组合网络理论和图论。

四、本科生的培养

1985年，科大数学系为本科生开设《组合学》课程。起初的几年都是由李乔讲授这门课程，他的讲稿《组合学基础》于1993年由高等教育出版社出版，成为组合学经典教材。从那以后，《组合学》一直成为科大数学系本科生必修课程。除李乔外，李炯生、徐俊明和潘永亮都讲授过这门课程。

1983年，王树禾为计算机系开设《图论与算法》，一直开到1994年。以后计算机系的图论课程是他们自己的老师（也是本专业毕业的研究生）讲授。王树禾的讲稿《图论及其算法》于1990年由科大出版社出版，一直作为计算机系本科生教材，深受国内计算机专业师生的好评。

1993年，本专业为科大全校本科生开设《图论及其应用》课程，向本科生普及图论知识，并着手编写讲义。选修此课程的学生最多达150人，大多来自计算机科学系、无线电系、物理系和化学系的本科生。从1994年开始，数学系本科生增设《图论及其应用》课程。徐俊明在开设此课程的基础上编写讲义。这本讲义经三次试用修改，作为科大本科生和研究生通用教材，于1988年由科大出版社出版。2002年，该书被国家教育部推荐为全国研究生指定用书。2003年，该书的英文版《 Theory and Application of Graphs》由Kluwer科学出版社出版。2004年，该书第二版出版，现已经列为《科大校庆50周年精品教材》。2006,潘永亮与徐俊明合著的教材《组合数学》由科学出版社出版。

在开设图论课程的基础上，我们还为对图论有兴趣的本科生通过选修研究生课程、做毕业论文、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年，科大数学系被国家教育部批准为一级重点学科。组合与图论专业参与了科大数学系的发展和学科建设，也为之做出了应有的贡献。科大组合与图论专业取得的成绩，在于本专业师生的艰苦创业和苦心耕耘，在于科大数学系五十年来所形成的风清人正、严谨治学、传帮带的优良传统和自由民主的学术氛围，在于中国科学技术大学“我创新故我在”的办学理念。目前，该专业师资力量结构合理，研究生培养体系逐步走向完善。我们坚信，科大数学系组合与图论专业将会越办越好，取得更大的成绩。

借此机会，我们诚挚感谢长期关心、指导、帮助和支持科大组合与图论专业建设和发展的万哲先院士、陈国良院士以及各级领导和组合与图论界同仁；深切怀念对本专业的创立和发展做出贡献的段学复教授、曾肯成教授、陶懋颀教授、侯定丕教授、杜锡录教授和骆新华副教授。

（本文由徐俊明执笔）

第四届全国组合数学与图论会议纪要

第四届全国组合数学与图论会议纪要 为促进我国组合数学与图论学科的进一步发展，加强国内同行的学术交流与合作，第四届全国组合数学与图论大会于2010年8月21日至25日在徐州师范大学举行。会议由中国组合数学与图论学会主办，徐州师范大学承办，并得到了徐州师范大学和国家自然科学基金委天元基金的大力资助。 会议期间，来自国内外约160所大学和研究院所的约400位专家、学者和研究生共聚一堂, 积极讨论，相互交流。福州大学范更华教授、同济大学邵嘉裕教授、中科院胡晓东教授、香港大学臧文安教授、南开大学高维东教授和北京交通大学常彦勋教授等作了6个大会报告（60分钟）。另外，分四个分组进行了13个特邀报告（30分钟）以及近120个小组报告（15分钟）。报告内容涉及组合数学与图论的各个领域。其中包括结构图论、随机图论、代数图论、化学图论、图的染色、组合设计、组合优化、组合计数、组合矩阵、复杂网络、网络优化、代数组合论与应用图论等众多领域。 开幕式由徐州师范大学数学科学学院院长刘笑颖教授主持，徐州师范大学党委书记徐放鸣教授首先致开幕词，接着，中国组合数学与图论学会的理事长陈永川发表了热情洋溢的讲话。

本次会议还举行了中国组合数学与图论学会理事会的换届选举。首先由上届正副理事长陈永川教授、李学良教授和王军教授（其中宝升教授因事缺席）提出新一届理事会的候选人名单。然后经理事会充分讨论，并进行民主投票选举，产生了51位新任理事，并随后由新一届理事会选举产生了新一届常务理事会与正副理事长。 与会代表衷心感谢本次会议的东道主徐州师范大学的校、院各级领导对本次会议的大力支持，衷心感谢会务组的全体同志为本次会议的顺利召开而付出的辛勤劳动。 经新一届常务理事会讨论，决定下一届全国组合数学与图论大会于2012年在洛阳师范学院举行。

组合数学在计算机中的应用

组合数学在计算机中的应用 组合数学，又称为离散数学，但有时人们也把组合数学和图论加在一起算成是离散数学。组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。随着计算机科学的发展,组合数学也在迅猛发展,而组合数学在理论方面的推进也促进计算机科学的发展。计算机软件空前发展的今天要求有相应的数学基础,组合数学作为大多数计算机软件设计的理论基础,它的重要性也就不言而喻。 就从目前我们在学习c++等语言进行编程解决问题看，组合数学的一些知识就能得到运用。例如Hannoi塔问题。用刚刚学的递推关系分析，设h(n)为n个盘子从a柱移到c柱所需移动的盘次。显然，当n=1时，只需把a柱上的盘子直接移动到c柱就可以了，故h(1)=1。当n=2时，先将a柱上面的小盘子移动到b柱上去；然后将大盘子从a柱移到c柱；最后，将b柱上的小盘子移到c柱上，共计3个盘次，故h(2)=3。以此类推，当a柱上有n(n>=2)个盘子时，总是先借助c柱把上面的n-1个盘移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动h(n-1)+1+h(n-1)个盘次。所以：h(n)=2h(n-1)+1 （边界条件：h1=1）。而一旦得出了这个递推关系式，就很容易运用递归算法来解决这样一个问题，递归算法因为是运用栈的方式进行加深与回溯，这个栈是系统给出的，故大大减少代码量。因此利用组合数学中的知识很容易抽象出数学模型再用相应的编程技巧来解决问题。 另外，我们最近数据结构正好学到了图这一章节。图是一种非常重要的数据存储结构，而在图的建立，遍历，生成树等问题的解决算法上基本都运用了组合数学中的知识。例如在最小生成树算法中间需要判断是否有环的问题，中间算法思想中就包含了欧拉图判定定理，(1) 无向连通图G是欧拉图=>G不含奇数度的结点(即G的所有结点的度均为偶数(0视为偶数))；(定理1) (2) 非0平凡图G有欧拉通路=>G最多有两个奇数度的结点；(定理1的推论) (3) 有向图D是欧拉图=>D连通且D的所有结点的入度等于出度。有向连通图有欧拉通路=>除两个结点外，其余结点的出度均等于入度，且这两点deg-(v)-deg+(v)=±1。(定理2) 除此之外，在那些我们还没有接触的计算机领域中，处处也有组合数学的身影。如：信息检索是计算机科学中一个基本而又重要的问题。如何组织数据,使用什么样的查找方法,对检索的效率有很大的影响。所熟知的在有序表结构上的二分搜索算法是一种很有效的方法,那么二分搜索是最好的算法吗?Yao利用Ramsey数对这一问题作了肯定的回答。 具体地讲,假设一个表有n个不同的项,其元素取自键空间M={1,2,,, m } ,希望找到在表中存储M的任意n元子集S的方法,使得容易回答下述询问: X在S中吗?如何存储M的n元子集的规则称为一个表结构或( m , n)-表结构。最简单的表结构是有序表结构,它是按上升序列出S中的元素。更一般的是按置换排序的表结构,其方法是固定{1,2,,, n}的一个置换,根据比置换的次序列出S中的元素。 信息检索的计算复杂性依赖于表结构和搜索策略。复杂性的度量是最坏情形下确定x 是否在S中所需要的询问次数。例如,对有序表结构,如果用二分搜索,所需要的询问次数是[log2( n+ 1) ]。复杂性f ( m , n )定义为所有的( m , n)-表结构和搜索策略下的复杂性的最小值。关于f ( m , n ), Yao证明了: 定理1 对每个n ,存在数N ( n) 使得f ( m , n) = [log2 ( n +1 ) ]对所有m>=N ( n) 成立。据此定理,对充分大的m ,就信息检索来说,用有序表结构是最有效的方法。 利用下述两个引理,立即可得此定理的证明。 引理1 若m >=2 n -1 , n >=2 ,对于按置换排序的表结构。无论采用何种策略,在最坏情形

组合数学在生活中的应用

组合数学在生活中的应用

组合数学在生活中的应用

组合数学在生活中的应用 数计学院姓名：廖梓文班别： 11数本3班学号：2011224323 摘要本文从对组合数学的一些基本概念和方法入手,结合具体的应用举例和数学史上的著名故事作为论题进行研究,进行了较全面的资料搜集.使人们加深对组合数学的理解,并应用于生活. 关键词:组合数学;数学游戏 1 引言 本文通过具体的应用实例和数学史上的一些故事和难题,介绍了组合数学是如何在生活中应用的.在研究了一些典型的例子和趣味性的故事的基础上,系统的查阅了相关文献，并结合生活中涉及组合数学的相关知识进行阐述,具体说明了组合数学的基本方法及其在生活中的应用.这样就使组合数学显得更加形象,也使抽象的理论概念变得浅显具体,更易被初学者理解和接受,以至于可以激发人们在生活中应用组合数学的意识. 2 组合数学的历史 组合数学是一门既古老又年轻的数学分支。随着计算机的普及推广,组合数学这门古老的学科焕发出蓬勃的生机. 组合数学不仅在基础数学研究中具有极其重要的地位，在其他的学科中也有重要的应用，如在计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。 我国古人在《河图》《洛书》中便已经对一些有趣的组合问题给出了正确的解答。中国最早的组合数学理论可追溯到宋朝时期的”贾宪三角”, 后来被杨辉引用, 所以普遍称之为“杨辉三角”, 这在西方是1654年由帕斯卡提出，但比中国晚了400多年。近代，由于计算机的出现，组合数学这门学科得以迅猛发展，成为了一个重要的数学分支。近代图论的历史可追溯到18世纪的七桥问题—穿过K?nigsberg城的七座桥，要求每座桥通过一次且仅通过一次。Euler1736年证明了不可能存在这样的路线。 4.组合数学的基本解题方法

组合数学与图论复习题与参考答案

组合数学与图论复习题及答案 1．Show that if n+1 integers are chosen form the set {1,2, …,2n},then there are always two which differ by at most 2. 从{1,2, …,2n}中选出n+1个数，在这n+1个数中，一定存在两个数，其中一个整数能整除另外一个整数。 任何一个数都可以写成2k*L，其中k是非负数，L是正奇数。现在从1到2n 之间只有n个奇数。由于有n+1个数都能表示成2k*L，而L的取值只有n中，所以有鸽子洞原理知道，至少有两个数的L是一样的，于是对应k小的那个就可以整除k大的另一个数。 2．Show that for any given 52 integers there are exist two of them whose sum, or else difference, is divisible 100. 设52个整数a 1，a 2 ，…，a 52 被100除的余数分别是r 1 ,r 2 ,…,r 52 ，而任意一 个数被100除余数为0，1，2，…，99，一共100个。他们可以分为51个类{0},{1,99},{2,98},…,{49,51},{50}。将这51个集合视为鸽笼，则将 r 1,r 2 ,…,r 52 放入51个笼子中，至少有两个属于同一个笼子，所以要么有ri＝rj， 要么有ri＋rj＝100，也就是说ai－aj|100或者ai＋aj|100。 3．从1，2，3，…，2n中任选n+1个数，证明在这n+1个数中至少有一对数互质。 鸽子洞原理，必有两个数相邻，相邻的两个数互质 4．Prove that Ramsey number R(p,q)≤R(p,q-1)+R(p-1,q). 令N＝R(p,q-1)+R(p-1,q)，从N个人中中随意选取一个a，F表示与a相识的人，S表示与a不相识的人。 在剩下的R(p,q-1)+R(p-1,q)－2＋1个人中，由鸽子洞原理有，或者F中有R(p,q-1)人，或者S中有R(p-1,q)人。如果F中有R(p,q-1)人，则与a相识的人为p个；如果S中有R(p-1,q)人，则与a不相识的人有p个。所以有R(p,q)≤R(p,q-1)+R(p-1,q) 5．There are 10 people, either there are 3 each pair of whom are acquainted, or there are 4 each pair of whom are unacquainted。 从10人中随意选一个人p，F表示与p相识的人，S表示与p不相识的人若F中至少有4人，如果至少有4人不相识，则满足题设；如果有2人相识，则加上p有3人相识，也满足题设。 若F中至多有3人，则S中至少有6人，6人中至少有3人相识，或者不相识。如果相识则满足题设，如果不相识加上p不相识的人就有4个，也满足题设。6．In how many ways can six men and six ladies be seated at round table if the men and ladies to sit in alternate seats? 6个男的先进行圆排列，然后6个女的插入空位。 7．In how many ways can 15 people be seated at round table if B refuses to sit next to A? What if B only refuses to sit on A right?

经典图论问题

5经典图论问题 5.1 一笔画问题 一笔画算法即是从起点a开始选择关联边（第一这条边不是往回倒，第二这条边在前面延伸路上没有出现过）向前延伸，如果到达终点b，得到a—b迹，判断路上的的边数是否为图的总边数，是就终止，否则选择迹上某个关联边没有用完的顶点v，用同样方式再搜索v—v的闭迹，添加到a—b迹上，即得到a—v---v—b迹，如果这个迹的边数还没有达到总边数，则再选择迹上某个关联边没有用完的顶点。。。。。。逐步扩展即可。

二、弗罗莱（Fleury ）算法 任取v 0∈V(G)，令P 0=v 0； 设P i =v 0e 1v 1e 2…e i v i 已经行遍，按下面方法从中选取e i+1： （a ）e i+1与v i 相关联； （b ）除非无别的边可供行遍，否则e i+1不应该为G i =G-{e 1,e 2, …, e i }中的桥（所谓桥是一条删除后使连通图不再连通的边）； （c ）当（b ）不能再进行时，算法停止。 5.2 中国邮递员问题（CPP ） 规划模型： 设ij x 为经过边j i v v 的次数，则得如下模型。 ∑∈= E v v ij ij j i x z ?min ∑ ∑ E ∈E ∈∈=j i i k v v i v v ki ij V v x x , E ∈∈≤j i ij v v N x ,1 ..t s

5.3旅行推销员问题（TSP，货郎担问题）（NPC问题） 定义：包含图G的所有定点的路（圈）称为哈密顿路（圈），含有哈密顿圈得图称为哈密顿图。 分析：从一个哈密顿圈出发， 算法一：（哈密顿圈的充要条件：一包含所有顶点的连通子图，二每个顶点度数为2） 象求最小生成树一样，从最小权边加边，顶点度数大于3以及形成小回路的边去掉。 算法二： 算法三：

图论与组合数学期末复习题含答案

组合数学部分 第1章 排列与组合 例1： 1)、求小于10000的含1的正整数的个数； 2、)求小于10000的含0的正整数的个数； 解：1)、小于10000的不含1的正整数可看做4位数,但0000除外.故有9×9×9×9－1＝6560个.含1的有：9999－6560=3439个 2)、“含0”和“含1”不可直接套用。0019含1但不含0。在组合的习题中有许多类似的隐含的规定，要特别留神。不含0的1位数有19个，2位数有29个，3位数有39个，4位数有49个 不含0小于10000的正整数有() ()73801919999954321=--=+++个含0小于10000的正整数9999－7380=2619个。 例2： 从[1,300]中取3个不同的数，使这3个数的和能被3整除，有多少种方案？ 解：将[1,300]分成3类： A={i|i ≡1(mod 3)}={1,4,7,…,298}, B={i|i ≡2(mod 3)}={2,5,8,…,299}, C={i|i ≡0(mod 3)}={3,6,9,…,300}. 要满足条件，有四种解法： 1)、3个数同属于A; 2)、3个数同属于B ； 3)、3个数同属于C; 4)、A,B,C 各取一数；故共有3C(100,3)+1003=485100+1000000=1485100。 例3：（Cayley 定理：过n 个有标志顶点的数的数目等于2-n n ） 1）、写出右图所对应的序列； 2）、写出序列22314所对应的序列； 解： 1）、按照叶子节点从小到大的顺序依次去掉节点（包含与此叶子 节点相连接的线），而与这个去掉的叶子节点相邻的另外一个点值则记入序列。如上图所示，先去掉最小的叶子节点②，与其相邻的点为⑤，然后去掉叶子节点③，与其相邻的点为①，直到只剩下两个节点相邻为止，则最终序列为51155.。 2）、首先依据给定序列写出（序列长度+2）个递增序列，即1234567，再将给出序列按从小到大顺序依次排列并插入递增序列得到：7。我们再将给出序列22314写在第一行，插入后的递增序列写在第二行。如下图第一行所示： ??→????? ??--②⑤67112223344522314??→???? ? ??--②⑥11223344672314 ??→????? ??--③②11233447314??→???? ? ??--①③11344714

组合数学

组合数学论文 现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好像是有思维的。组合数学不仅在软件技术中有重要的应用价值，在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软件。 广义的组合数学就是离散数学，离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别。总之，组合数学是一门研究离散对象的科学。随着计算机科学的日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据。 狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化等。 组合数学中有几个著名的问题： 地图着色问题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？这是图论的问题。 船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？ 这是线性规划的问题。 中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。这也是图论的问题。 货郎问题：一个货郎要去若干城镇卖货，然后会到出发地，给定各个城镇之间的旅行时间，应怎么样计划他的路线，使他可以去每个城镇而且所用的时间最短。这个问题至今都没有有效的算法。 这几个问题将组合数学研究的问题具体表现出来，同时也可以看出他在我们生活中有着很重要的地位。 组合数学中主要可以分成以下几个部分：排列组合与容斥原理、二项式定理、递推关系与生成函数、polya定理。下面我将以这四个部分分别介绍组合数学的各方面问题。 1、排列组合与容斥原理： 排列组合里面的4个重要的基本原理：加法原理、乘法原理、减法原理、除法原理 前面两个最为基本，后面两个是根据前两个派生出来的。乘法原理有的时候的应用很巧妙，可以作为一种打开思路的办法。

组合数学及其图论试题库

组合数学及其图论 1、一个图G 是指一个有序三元组（V （G ），E （G ），G ?），其中G ?是：________________. 关联函数 2、 是有40个点的简单图且 中任两个点之间有且只有1条路，则 。 39 3、只有一个顶点所构成的图称为：________________ 平凡图 4、如果H 是G 的子图，其中V （H ）=V （G ）和E （G ）=E （H ）至少有一个不成立，就称H 是G 的：_____________. 真子图 5、设G 是p 阶简单图，则__________________等号成立当且仅当G 是完全图。 q(G)≤p(p-1)/2 6、如果一条途径的_________与___________相同，就称这条途径为闭途径。 起点 终点 7、如果对图G=（V ，E ）的任何两个顶点u 与v ，G 中存在一条（u-v ）路，则称G 是___________否则称为是______________ 连通图、 非连通图 8、设G 是P 阶连通图，则__________________. q(G)≥p-1 9、若二分图 有Hamilton 回路，则 与 满足 。 10、若G 是2-边连通图，则G 有强连通的________________. 定向图 11、边数最少的连通图是 。

树 12、没有回路的连通图称为_______________. 树 13、的图是图或图。 平凡图，不连通图 14、树T的每一个非悬挂点都是T的 __________. 割点 15、二分图中若与满足，则必有完美对集。 16、给定一个图G，如果图G的一个生成子图T是一棵树，则称T是G的一个_______________. 生成树 17、设G是无环图，e是G的一条边，则 τ(G)=___________________________. τ （G－e）+τ (G·e) 18、是阶简单图，则，等号成立当且仅当是图。 ，完全图 2、 19、___________________________的生成树称为最优生成树。 连通赋权图中具有最小权 20、的一个对集是最大对集的充要条件是。 中无可扩路 21、一个有向图D，如果略去每条弧的方向时所得无向图是一棵树，就称D为_____________________. 有向树 22、经过G的每条边的迹称为G的Euler迹，如果这条迹是闭的，则称这条闭迹为G的 ________________. Euler环游 23、是简单图且，则。

组合数学前沿介绍

组
合
数
学
Combinatorics
马昱春 MA Yuchun myc@https://www.wendangku.net/doc/6c11160357.html,
1

组
合
数
学
Combinatorics
组合数学:有人认为广义的组合数学就是离散数学，也有人认 为离散数学是狭义的组合数学和图论、代数结构、数理逻辑 等的总称。但这只是不同学者在叫法上的区别。总之，组合 数学是一门研究离散对象的科学。
https://www.wendangku.net/doc/6c11160357.html,/zh-cn/%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6
Combinatorics: Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. It is related to many other areas of mathematics, such as algebra, probability theory, ergodic theory and geometry, as well as to applied subjects in computer science and statistical physics.
https://www.wendangku.net/doc/6c11160357.html,/wiki/Combinatorics 2

组合数学与离散数学
? 狭义的组合数学主要研究满足一定条件的组态（ 也称组合模型）的存在、计数以及构造等方面的 问题。
– 组合数学的主要内容有组合计数、组合设计、组合矩 阵、组合优化等。
? 离散数学(Discrete mathematics)是数学的几个分 支的总称，以研究离散量的结构和相互间的关系 为主要目标，其研究对象一般地是有限个或可数 无穷个元素；因此它充分描述了计算机科学离散 性的特点。
– 离散数学通常研究的领域包括：数理逻辑、集合论、 关系论、函数论、组合学、代数系统与图论。 。
3

离散数学图论部分经典试题及答案

离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝，则下列结论成立的是 ( )． A ．deg(V )=2∣E ∣ B ．deg(V )=∣E ∣ C ．E v V v 2)deg(=∑∈ D ．E v V v =∑∈)deg( 4．图G 如图一所示，以下说法正确的是 ( ) ． A ．{(a , d )}是割边 B ．{(a , d )}是边割集 C ．{(d , e )}是边割集 D ．{(a, d ) ,(a, c )}是边割集 5．如图二所示，以下说法正确的是 ( )． A ．e 是割点 B ．{a, e }是点割集 C ．{b , e }是点割集 D ．{d }是点割集 6．如图三所示，以下说法正确的是 ( ) ． A ．{(a, e )}是割边 B ．{(a, e )}是边割集 C ．{(a, e ) ,(b, c )}是边割集 D ．{(d , e )}是边割集 ο ο ο ο ο c a b e d ο f 图一 图二

图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( ) ． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ο ο ο ο c a b f

组合数学学习心得

组合数学学习心得 在进入研究生学习的第一个学期就开设了组合数学这门课程，我感到很庆幸和开心，因为我在学完这门课程之后学到了很多东西，不仅仅是课本上的，还有许多在课本上是学不到了！ 组合数学，对大多数学生来说是一门十分困难的课程，由于自己本科学的是数学，所以学起来还好，也比较喜欢这门课程。组合数学可以一般描述为：组合数学是研究离散结构的存在，计数，分析，和优化等问题的一门学科。经验证发现的组合数学最有力的工具之一为数学归纳法。归纳是一个强有力的过程，在组合数学中尤其是如此。用数学归纳法证明一个结果常常比证明一个弱结果更容易。许多组合问题的解决常常需要某些特别的例证，而且有时需要结合使用一般的理论。我们必须学会建立数学模型，研究模型，抓住问题的要害，灵活的应用智慧来解决问题。“图论”是组合数学课程中比较重要的一部分。在刚接触到“图”这一章的时候我是抱着好奇之心去学习的，因为这章都是关于“图” ，想了解一下和几何图形的差别，所以觉得善长几何的我应该能够把它学好。但是不可否认，随着知识的深入，这一章一定会比前面的更难理解，更难学。因此上课的时候听得格外认真，课后还找了一些相关书籍阅览。在看过这些书籍以后，我才真正了解到它并不是枯燥乏味的，它的用途非常广泛，并且应用于我们整个日常生活中。比如：怎样布线才能使每一部电话互相连通，并且花费最小？从首府到每州州府的最短路线是什么？n 项任务怎样才能最有效地由 n 个人完成？管道网络中从源点到集汇点的单位时间最大流是多少？一个计算机芯片需要多少层才能使得同一层的路线互不相交？怎样安排一个体育联盟季度赛的日程表使其在最少的周数内完成？我们能用4种颜色来为每张地图的各个区域着色并使得相邻的区域具有不同的颜色吗？这些问题以及其他一些实际问题都涉及“图论” 。这里所说的图并不是几何学中的图形，而是客观世界中某些具体事物间联系的一个数学抽象，用顶点代表事物，用边表示各式物间的二元关系，如果所讨论的事物之间有某种二元关系，我们就把相应的顶点练成一条边。这种由顶点及连接这些顶点的边所组成的图就是图论中所研究的图。由于它关系着客观世界的事物，所以对于解决实际问题是相当有效的。总之，图论是数学科学的一个分支，而四色问题是典型的图论课题。通过对图论的初步理解和认识，我深深地认识到，图论的概念虽然有其直观、通俗的方面，但是这许多日常生活用语被引入图论后就都有了其严格、确切的含义。我们既要学会通过术语的通俗含义更快、更好地理解图论概念，又要注意保持术语起码的严格。 学习数学重要的是理解，而不是像其它科目一样死背下来，数学有一个特点,那就是”举一反三”。做会了一道题目，就可以总结这道题目所包含的方法和原理,再用总结的原理去解决这类题，收效就会更好.学习数学还有一点很重要，那就是从基本的下手，稳稳当当的去练，不求全部题都会做，只求做过的题不会忘，会用就行了。在做题的过程中，学习是一生的事情，不要过于着急，一步一个脚印的来,就一定会取得一想不到的效果。数学的学习是一个积累和运用的过程，因此，学好数学的一个必要前提便是要注重平时的积累和运用。而在日常时对于数学的学习还是有许多方法的。数学学习做题是极为必要的，因此做题之后的总结工作也是极为重要的，否则只能是杂而不精，无法将知识融会贯通，合理运用。 组合数学是一门既古老又年轻的数学分支。组合数学不仅在基础数学研究中具有极其重要的地位，在其他的学科中也有重要的应用，如在计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。如果说微积分和近代数学

图论与组合数学 教学大纲 2016 修改版

《图论与组合数学》教学大纲 一、课程名称：图论与组合数学 二、课程代码：021********* 三、课程英文名称：Graph Theory and Combinatorics 四、课程负责人：刘任任，肖芬，曹春红 五、学时与学分：48学时（理论40学时，实验8学时），3.0学分 六、课程性质：必修 七、适用专业：工科本科计算机科学与技术专业 八、选课对象：计算机科学与技术专业 九、预修课程：集合论与数理逻辑、C语言程序设计I、数据结构 十、课程教材与参考书目： 课程教材： 1.刘任任编著，《离散数学》，中国铁道出版社，2009年12月； 2.刘任任主编，《离散数学题解与分析》，中国铁道出版社，2010年10月。 参考书目： 1.Kneneth H. Rosen, Discete Mathematics and Its Applications, Fifth Edition,2003年； 2.Richard Johnsonbaugh, Discrete Mathematics, Prentice Hall Inc., 2000年； 3.Kolman B., etc., Discrete Mathematical Structures，Prentice Hall Inc., 2001； 4.Brualdi, R.A. (美)，组合数学(第四版)，北京机械工业出版社，2005年2月； 5.卢开澄，组合数学，清华大学出版社， 6.孙吉贵等编著，《离散数学》，高等教育出版社，2002年； 7.陈莉等编著，《离散数学》，高等教育出版社，2002年。 十一、开课单位：信息工程学院 十二、课程与能力培养中的对应关系 1、能力1.2: 掌握计算机科学与技术专业所要求的数学和自然科学基本知识，能将其用于计算机复杂工程问题的分析与建模； 2、能力2.1：掌握文献检索、资料查询的基本方法，能够运用现代技术获取相关文献，具有资料阅读和文献研究能力，并用于计算机科学与技术相关的复杂工程问题的分析和推理； 3、能力2.2：通过理论与实践相结合的系统学习，能够识别复杂工程问题中所涉及的数学、自然科学及计算机科学与技术专业的相关理论知识。 十三、课程的目标 图论和组合数学是现代数学的重要分支，是研究离散结构的存在、计数、分析和优化等问题的一门科学，是计算机科学与技术专业的基础理论课程。通过本课程的学习，使学生掌握图论与组合数学的基本原理和方法，了解和掌握无向图、有向图、连通图、排列与组合、容斥原理、递推关系和生成函数等基本知识，灵活运用所学知识对一些简单问题进行建模并编程求解。

组合数学与数论1

第一部分：组合数学 第一章计数的基本原则 一．组合数学的历史和内容 1.历史：组合数学最早起源于中世纪的印度，在漫长的历史中，一 直发展缓慢。随着上一世纪计算机的出现，组合数学开始快速地发展。近几年，由于计算机安全领域受到重视以及组合数学在计算机安全领域的应用，组合数学受到越来越多的重视。 2.内容：组合数学主要包括以下几个内容： (1)组合分析（也称为组合计数理论） (2)组合优化（包括线性规划，整数规划等） (3)组合设计（包括区组设计等） (4)组合算法（例如：搜索算法，DFS算法与分支定界法，动态规 划等） *图论本是组合数学这个家族的一个主要成员，但它已成长壮大，独立成一门学科。 3. 本课程介绍的主要内容：组合计数理论 二．加法原则与乘法原则 1. 加法原则： 设事件A有m种产生方式，事件B有n种产生方式，则“事件A 或事件B”有m+n种产生方式。 例子：大于0而小于10的偶数有4个，即：{2，4，6，8}，大于0而小于10的奇数有5个，即：{1，3，5，7，9}。则大于0而小于10

的整数有：4+5=9个，即：{1，2，3，4，5，6，7，8，9}。 *如果A1,A2,?,A n是互不相交的有穷集，那么 |A1∪A2∪?∪A n|=|A1|+|A2|+?+|A n| 2.乘法原则： 若事件A有m种产生方式，事件B有n种产生方式，则“事件A 与事件B”有mn种产生方式。 例1：设一个符号由两个字符组成，第一个字符有a,b,c,d,e五种方式，第二个字符有1,2,3三种方式。则根据乘法原则，该符号具有5×3= 15种方式，即 a1,b1,c1,d1,e1;a2,b2,c2,d2,e2;a3,b3,c3,d3,e3. 例2：从A到B有3条不同的道路，从B到C有2条不同的道路，从A经B到C共有n=3×2=6条不同的道路。 例3：求比10000小的正整数中含有数字1的数的个数。 解：先求所有4位数中不含有数字1的个数，即求由{0，2，3，4，5，6，7，8，9} 9个数字组成的4位数的个数。每一位都有9种出现方式，根据乘法原则，由9个数字组成的4位数个数为：9×9×9×9= 6561，其中包含0000不是正整数。故比10000小不含数字1的4位正整数的个数=6561?1=6560. 所以小于10000含有数字1的4位数个数=9999?6560=3439.

组合数学在计算机中的应用

目录 摘要 (1) 1.组合数学概述 (1) 2.组合数学在生活中的应用 (1) 3.组合数学与计算机软件 (1) 3.1 信息时代的组合数学 (2) 3.2 组合数学在计算机软件的应用 (2) 3.3组合数学与计算机软件的关系 (2) 3.4组合数学在国外软件业的发展状况 (2) 4 Ramsey 数在计算机科学中的应用 (3) 4.1Ramsey 定理和Ramsey 数 (3) 4.2信息检索 (3) 参考文献 (5)

组合数学在计算机中的应用 摘要：介绍了组合数学的概念、起源与研究的主要内容,分析了组合数学的特点以及其在生活中的应用,阐述了组合数学与计算机软件的联系,并着重通过两个例子说明了Ramsey 数在计算机科学的信息检索中的重要应用。 关键词：组合数学;组合算法;Ramsey 数;信息检索; 1：组合数学概述 组合数学，又称为离散数学，但有时人们也把组合数学和图论加在一起算成是离散数学。组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。组合数学的发展改变了传统数学中分析和代数占统治地位的局面。现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好象是有思维的。 2：组合数学在生活中的应用 在日常生活中我们常常遇到组合数学的问题。如果你仔细留心一张世界地图，你会发现用一种颜色对一个国家着色，那么一共只需要四种颜色就能保证每两个相邻的国家的颜色不同。这样的着色效果能使每一个国家都能清楚地显示出来。但要证明这个结论确是一个著名的世界难题，最终借助计算机才得以解决，最近人们才发现了一个更简单的证明。 当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往往需要做些调整。从理论上讲，装箱问题是一个很难的组合数学问题，即使用计算机也是不容易解决的。航空调度和航班的设定也是组合数学的问题。怎样确定各个航班以满足不同旅客转机的需要，同时也使得每个机场的航班起落分布合理。此外，在一些航班有延误等特殊情况下，怎样作最合理的调整，这些都是组合数学的问题。 组合数学在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软件。最近，德国一位著名组合数学家利用组合数学方法研究药物结构，为制药公司节省了大量的费用，引起了制药业的关注。 总之，组合数学无处不在，它的主要应用就是在各种复杂关系中找出最优的方案。所以组合数学完全可以看成是一门量化的关系学，一门量化了的运筹学，一门量化了的管理学。 3：组合数学与计算机软件 随着计算机网络的发展，计算机的使用已经影响到了人们的工作，生活，学习，社会活动以及商业活动，而计算机的应用根本上是通过软件来实现的。

图论经典问题

常见问题： 1、图论的历史 图论以图为研究对象的数学分支。图论中的图指的是一些点以及连接这些点的线的总体。通常用点代表事物，用连接两点的线代表事物间的关系。图论则是研究事物对象在上述表示法中具有的特征与性质的学科。 在自然界和人类社会的实际生活中，用图形来描述和表示某些事物之间的关系既方便又直观。例如，国家用点表示，有外交关系的国家用线连接代表这两个国家的点，于是世界各国之间的外交关系就被一个图形描述出来了。另外我们常用工艺流程图来描述某项工程中各工序之间的先后关系，用网络图来描述某通讯系统中各通讯站之间信息传递关系，用开关电路图来描述IC中各元件电路导线连接关系等等。 事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟。由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点之间连接与否最重要，而连接线的曲直长短则无关紧要。由此经数学抽象产生了图的概念。研究图的基本概念和性质、图的理论及其应用构成了图论的主要内容。 图论的产生和发展经历了二百多年的历史，大体上可分为三个阶段： 第一阶段是从1736年到19世纪中叶。当时的图论问题是盛行的迷宫问题和游戏问题。最有代表性的工作是著名数学家L.Euler于1736年解决的哥尼斯堡七桥问题(Konigsberg Seven Bridges Problem)。 东普鲁士的哥尼斯堡城(现今是俄罗斯的加里宁格勒，在波罗的海南岸）位于普雷格尔(Pregel)河的两岸，河中有一个岛，于是城市被河的分支和岛分成了四个部分，各部分通过7座桥彼此相通。如同德国其他城市的居民一样，该城的居民喜欢在星期日绕城散步。于是产生了这样一个问题：从四部分陆地任一块出发，按什么样的路线能做到每座桥经过一次且仅一次返回出发点。这就是有名的哥尼斯堡七桥问题。 哥尼斯堡七桥问题看起来不复杂，因此立刻吸引所有人的注意，但是实际上很难解决。 瑞士数学家(Leonhard Euler)在1736年发表的“哥尼斯堡七桥问题”的文章中解决了这个问题。这篇论文被公认为是图论历史上的第一篇论文，Euler也因此被誉为图论之父。 欧拉把七桥问题抽象成数学问题---一笔画问题，并给出一笔画问题的判别准则，从而判定七桥问题不存在解。Euler是这样解决这个问题的：将四块陆地表示成四个点，桥看成是对应结点之间的连线，则哥尼斯堡七桥问题就变成了：从A，B，C，D任一点出发，通过每边一次且仅一次返回原出发点的路线(回路)是否存在？Euler证明这样的回路是不存在的。 第二阶段是从19世纪中叶到1936年。图论主要研究一些游戏问题：迷宫问题、博弈问题、棋盘上马的行走线路问题。一些图论中的著名问题如四色问题(1852年)和Hamilton环游世界问题(1856年)也大量出现。同时出现了以图为工具去解决其它领域中一些问题的成果。1847年德国的克希霍夫(G.R.Kirchoff)将树

组合数学-浅谈组合数学与计算机科学

浅谈组合数学与计算机科学 摘要：组合数学，又称为离散数学，是一门研究离散对象的科学。组合数学是计算机出现以后迅速发展起来的一门数学分支，随着计算机科学的日益发展，组合数学的重要性也日渐凸显。 关键词：组合数学计算机欧拉回路 Abstract: The combination of mathematics, also known as discrete mathematics, is a study of discrete objects. A combination of computer mathematics is a branch of mathematics developed rapidly since, with the increasing importance of the development of computer science, combinatorial mathematics has become more prominent. Key words: Combinatorics Computer Euler circuit 1.组合数学简述 组合数学是一门古老而又新兴的数学分支。我国古人早在《河图》、《洛书》中已对一些有趣的组合问题给出了正确的解答。近代随着计算机的出现,组合数学这门学科得到了迅猛的发展,成为了一个重要的数学分支。组合数学的发展改变了传统数学中分析和代数占统治地位的局面。 组合数学主要研究符合一定条件的组态对象、计数及构造等方面的问题。离散构形问题是组合数学的主要研究内容，主要包括：①构形构形的存在性问题；②构形的构造性问题；③构形的计数问题；④构形的最优化问题。 现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等; 另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如在计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。 电子计算机处理的信息，都是仅用“0”与“1”两个简单数字表示的信息，或者是用这种数字进行了编码的信息。所以离散对象的处理就成了计算机科学的核心，而组合数学是一门研究离散对象的科学。现代数学的研究内容主要包括两个方面：一方面类是研究连续对象的，如分析、代数等，另一方面就是研究离散对象的组合数学。