[科普中国]-组合数学

简介

现代数学可以分为两大类：一类是研究连续对象的，如分析学、方程等，另一类就是研究离散对象的数学。

有人认为广义的组合数学就是离散数学，也有人认为离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别，随着计算机科学的日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据2。

组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物学等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在做数值计算。确切地说，组合数学是计算机出现以后迅速发展起来的一门数学分支，主要研究离散对象的存在、计数以及构造等方面问题。由于计算机软件的促进和需求，组合数学已成为一门既广博又深奥的学科，其发展奠定了本世纪的计算机革命的基础，并且改变了传统数学中分析和代数占统治地位的局面。正是因为有了组合算法才使人感到，计算机好像是有思维的。

组合数学不仅在软件技术中有重要的应用价值，在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合数学。用组合数学的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软件。

国内现状1985年9月，中国数学会组合数学与图论专业委员会成立，标记着中国组合数学学科的形成和创立，并于2001年正式成为中国组合数学与图论学会。随着近年来组合数学理论体系的逐步完善和发展，越来越多的学者更加关注这一计算机与数学结合学科的发展。中国数学会组合数学与图论专业委员会是中国数学会的分支机构，成立于1985年5月。专业委员会的成立得到吴文俊先生的直接关心与支持。首届专业委员会由25人组成，主任为徐利治。专业委员会成立后，原有的全国组合数学研究会和全国图论研究会继续独立存在，各自组织活动。直到2001年，两研究会正式合并成立中国组合数学与图论学会，同时完成了专业委员会的调整和换届。专业委员会委员即学会常务理事；专业委员会主任，副主任即学会理事长，副理事长。第一届专业委员会（学会常务理事会）由26人组成，主任（理事长）为范更华。专业委员会于2004年在新疆乌鲁木齐组织召开了首届全国组合数学与图论大会（首次以专业委员会的名义将各自举办了二十多年的全国性系列会议合二为一），200多位代表参加了这次会议。专业委员会于2004年在福州举办了为期三个月的全国性研究生班(由福州大学离散数学研究中心承办)，邀请海外留学人员利用学术休假回国开设完整的研究生课程，有50多位来自国内14所院校的研究生参加了这期研究生班。专业委员会于2005年在福州举办了为期一个月的全国性青年教师研讨班(由福州大学离散数学研究中心承办)，旨在为组合数学与图论培养后继人才。2005年3月在南京师范大学召开的理事长会议上草拟了学会的章程和关于举办学术会议的办法及工作程序，2005年6月在金华召开的第三届海峡两岸图论与组合数学会议上通过了这两个文件。2006年8月学会在南开大学召开了第二届全国组合数学与图论大会，有400多位代表参加了此次会议。由于第一届理事会四年任期已满，会议期间，学会根据章程进行了换届选举，南开大学陈永川当选为理事长（专业委员会主任）。

国外状况组合数学在国外早已成为十分重要的学科，甚至可以说是计算机科学的基础。一些大公司，如IBM，AT&T都有全世界最强的组合研究中心。Microsoft的Bill Gates近来也在提倡和支持计算机科学的基础研究。例如，Bell实验室的有关线性规划算法的实现，以及有关计算机网络的算法，由于有明显的商业价值，显然是没有对外公开的。美国已经有一种趋势，就是与新的算法有关的软件是可以申请专利的。如果照这种趋势发展，世界各国对组合数学和计算机算法的投入和竞争必然日趋激烈。美国政府也成立了离散数学及理论计算机科学中心DIMACS（与Princeton大学，Rutgers大学，AT&T 联合创办的，设在Rutgers大学），该中心已是组合数学及理论计算机科学的重要研究阵地。美国国家数学科学研究所（Mathematical Sciences Research Institute，由陈省身先生创立）在1997年选择了组合数学作为研究专题，组织了为期一年的研究活动。日本的NEC公司还在美国的设立了研究中心，理论计算机科学和组合数学已是他们重要的研究课题，该中心主任R. Tarjan即是组合数学的权威。美国重要的国家实际室（Los Alamos国家实验室，以造出第一颗原子弹著称于世），从曼哈顿计划以来一直重视应用数学的研究，包括组合数学的研究。不仅如此，该实验室最近还在积极充实组合数学方面的研究实力。美国另外一个重要的国家实验室Sandia国家实验室有一个专门研究组合数学和计算机科学的机构，主要从事组合编码理论和密码学的研究，在美国政府以及国际学术界都具有很高的地位。

由于生物学中的DNA的结构和生物现象与组合数学有密切的联系，各国对生物信息学的研究都很重视，这也是组合数学可以发挥作用的一个重要领域。由于DNA就是组合数学中的一个序列结构，美国科学院院士，近代组合数学的奠基人Rota教授预言，生物学中的组合问题将成为组合数学的一个前沿领域。

传统的计算机算法可以分为两大类，一类是组合算法，一类是数值算法（包括计算数学和与处理各种信息数据有关的信息学）。近年来计算机算法又多了一类：那就是符号计算算法。吴文俊院士开创的机器证明方法就属于符号计算，引起了国际上的高度评价，被称为吴方法。而国际上还有专门的符号计算杂志。符号算法和吴方法跟代数组合学也有十分密切的联系。组合数学，数值计算（包括计算数学，科学计算，非线性科学，和与处理各种信息数据有关的信息学）和统计学可能是应用最广的数学分支，而组合数学的价值甚至不亚于统计学和数值计算。由于数学机械化近年来的发展和在计算机科学中的重要性，把数学机械化，科学计算和组合数学组合起来，就可以说是中国信息产业的基础。组合数学家H. Wilf和D. Zeilberger1998因为在组合恒等式的机械化证明方面的成果，获得1998年美国数学会的Steele奖。

Thomson Science公司创刊的一份电子刊物《离散数学和理论计算机科学》即是一个很好的说明。它的内容涉及离散数学和计算机科学的众多方面。由于计算机软件的促进和需求，组合数学已成为一门既广博又深奥的学科，需要很深的数学基础，逐渐成为了数学的主流分支。

除上述以外，欧洲也在积极发展组合数学，英国、法国、德国、荷兰、丹麦、奥地利、瑞典、意大利、西班牙等国家都建立了各种形式的组合数学研究中心。近几年，南美国家也在积极推动组合数学的研究。澳大利亚，新西兰也组建了很强的组合数学研究机构。值得一提的是亚洲的发达国家也十分重视组合数学的研究。日本有组合数学研究中心，并且从美国引进人才，不仅支持日本国内的研究，还出资支持美国的有关课题的研究，这样使日本的组合数学这几年的发展极为迅速。台湾、香港两地也从美国引进人才，大力发展组合数学。新加坡，韩国，马来西亚也在积极推动组合数学的研究和人才培养。台湾的数学研究中心也正在考虑把组合数学作为重点方向来发展。

主要学术会议

|| ||

问题四色问题如果你仔细留心一张世界地图，你会发现用一种颜色对一个国家着色，那么一共只需要四种颜色就能保证每两个相邻的国家的颜色不同。这样的着色效果能使每一个国家都能清楚地显示出来。但要证明这个结论确是一个著名的世界难题，1976年数学家通过计算机运算得到证明而成为四色定理，最近人们才发现了一个更简单的证明。

中国邮差问题由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题。由中国组合数学家管梅谷教授提出，著名组合数学家，J. Edmonds和他的合作者给出了一个解答。

任务分配问题（也称婚配问题）有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少？

河洛图我国古代的河洛图上记载了三阶幻方，即把从一到九这九个数按三行三列的队行排列，使得每行，每列，以及两条对角线上的三个数之和都是一十五。组合数学中有许多像幻方这样精巧的结构。1977年美国旅行者1号、2号宇宙飞船就带上了幻方以作为人类智慧的信号。（题图）

装箱问题当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往往需要做些调整。从理论上讲，装箱问题是一个很难的组合数学问题，即使用计算机也是不容易解决的。

过河问题在中小学的数学游戏中，有这样一个问题，一个船夫要把一只狼，一只羊和一棵白菜运过河。问题是当人不在场时，狼要吃羊，羊要吃白菜，而他的船每趟只能运其中的一个。他怎样才能把三者都运过河呢？这就是一个很典型、很简单的组合数学问题。

是否存在稳定婚姻的问题假如能找到两对夫妇（如张（男）--李（女）和赵（男）--王（女）），如果张（男）更喜欢王（女），而王（女）也更喜欢张（男），那么这样就可能有潜在的不稳定性。组合数学的方法可以找到一种婚姻的安排方法，使得没有上述的不稳定情况出现（当然这只是理论上的结论）。这种组合数学的方法却有一个实际的用途：美国的医院在确定录取住院医生时，他们将考虑申请者的志愿的先后次序，同时也给申请排序。按这样的次序考虑出的总的方案将没有医院和申请者两者同时后悔的情况。 实际上，高考学生的最后录取方案也可以用这种方法。

管理调度问题我们还会遇到更复杂的调度和安排问题。例如，在生产原子弹的曼哈顿计划中，涉及到很多工序，许多人员的安排，很多元件的生产，怎样安排各种人员的工作，以及各种工序间的衔接，从而使整个工期的时间尽可能短？这些都是组合数学典型例子。又比如，假日饭店的管理中，也严格规定了有关的工序，如清洁工的第一步是换什么，清洗什么，第二步又做什么，总之，他进出房间的次数应该最少。既然，这样一个简单的工作都需要讲究工序，那么一个复杂的工程就更不用说了。

库房和运输的管理问题怎样安排运输使得库房充分发挥作用，进一步来说，货物放在什么地方最便于存取（如存储时间短的应该放在容易存取的地方）。

铺地砖问题我们知道，用形状相同的方型砖块可以把一个地面铺满（不考虑边缘的情况），但是如果用不同形状，而又非方型的砖块来铺一个地面，能否铺满呢？这不仅是一个与实际相关的问题，也涉及到很深的组合数学问题。

组合数学还可用于金融分析组合数学还可用于金融分析，投资方案的确定，怎样找出好的投资组合以降低投资风险。南开大学组合数学研究中心开发出了"金沙股市风险分析系统"现已投放市场，为短线投资者提供了有效的风险防范工具。

总之，组合数学无处不在，它的主要应用就是在各种复杂关系中找出最优的方案。所以组合数学完全可以看成是一门量化的关系学，一门量化了的运筹学，一门量化了的管理学。