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

浅谈组合数学与计算机科学摘要：组合数学，又称为离散数学，是一门研究离散对象的科学。组合数学是计算机出现以后迅速发展起来的一门数学分支，随着计算机科学的日益发展，组合数学的重要性也日渐凸显。关键词：组合数学 计算机 欧拉回路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 circuit1.组合数学简述组合数学是一门古老而又新兴的数学分支。我国古人早在河图、洛书中已对一些有趣的组合问题给出了正确的解答。 近代随着计算机的出现,组合数学这门学科得到了迅猛的发展,成为了一个重要的数学分支。 组合数学的发展改变了传统数学中分析和代数占统治地位的局面。组合数学主要研究符合一定条件的组态对象、计数及构造等方面的问题。离散构形问题是组合数学的主要研究内容，主要包括：构形构形的存在性问题；构形的构造性问题；构形的计数问题；构形的最优化问题。现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等; 另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如在计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。电子计算机处理的信息，都是仅用“0”与“1”两个简单数字表示的信息，或者是用这种数字进行了编码的信息。所以离散对象的处理就成了计算机科学的核心，而组合数学是一门研究离散对象的科学。现代数学的研究内容主要包括两个方面：一方面类是研究连续对象的，如分析、代数等，另一方面就是研究离散对象的组合数学。2.组合数学的几种基本思想方法除了各种形式的数学归纳法之外, 那就是 映射原则 ,( 2) 递归原则,( 3) 序化原则, ( 4) 反演原则。这四大原则在处理各类组合学问题时又进一步具体化为种种技巧, 因此又可叫作映射技巧( 包括双射技巧、变换技巧、生成函数技巧等), 递归技巧, 序化技巧( 包括偏序化技巧、良序化技巧) 及嵌入反演技巧等。无论是组合计数问题或是结构分析问题, 映射法是最常用也是最有效的方法。但如何引用合适的映射去解决间题往往需要洞察力和技巧。递归原则常用于处理“ 应用组合学” 问题, 它是一种特殊的数学模型方法, 因为由递归分析导出的差分方程及初始条件往往可以看成为原型间题的数学模型。序化原则( P r i n e ip l e o f o r d e r i n g ) 是“ 计算组合学” ( C o m p u t a t i o n a l 。o m b i n a t o r i e s ) 中最基本的方法原则。事实上, 任何组合计算对象只有经过适当的序化后, 即经过良序化或者偏序化之后才能上机去计算。嵌入反演技巧是发现和证明各种代数组合恒等式的重要方法, 有时也可用来求解包含未知函数的代数组合方程。以上所述只是经典组合数学中的常见方法, 是属于组合学内部体系中的方法。事实上, 现代组合学还借用了其他学科的许多方法, 例如代数学诸分支中的方法、解析函数论方法、渐近分析方法、数论方法、概率论及统计数学方法等。 近年以来, 非标准分析方法也已开始进入组合数学领域, 但成果还不多, 正待继续发展。3.组合数学中经典问题组合数学中的经典问题主要包括：棋盘完美覆盖；切割立方体；幻方；四色问题；36 军官问题；最短路径；NIM取子问题；羊狼菜过河问题；中国邮递员问题；稳定婚姻问题。以下重点介绍四色问题和中国邮递员问题。3.1 四色问题四色问题即使用四种不同的颜色对世界地图着色，要求相邻国家的颜色相异。采用数学语言对本问题进行形式化描述如下：将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4 这4 个数字之一来标记，而不会使相邻的两个区域得到相同的数字。一个多世纪以来，在四色问题的研究证明过程中，由于对象问题复杂且缺乏数学通常的解题规范，人工直接验证不可行。本世纪70 年代，电子计算机的迅速发展和广泛应用使四色问题的研究出现了转机。美国伊利诺斯大学的阿佩尔、哈肯等人在研究了前人各种证明方法和思想的基础后，从1972 年起，开始了用计算机证明四色问题的研究工作。终于在1976 年彻底解决了四色问题，整个证明过程在计算机上花费了1200 个小时。地图四色问题是第一个主要由计算机完成证明的数学难题。科学家们在研究和解决四色问题的过程中，还由此产生不少新的数学理论，发展了很多数学计算方法，刺激了拓扑学与图论的发展。3.2 中国邮递员问题一个邮递员的工作是：按一定路线递送他所负责的街区的各条街道的邮件，最后返回邮局，要求邮递员必须走过他负责的街区的每一条街道至少一次，并希望选择一条总路程最短的递送路线。寻找这样的一条最短递送路线的问题，在国际学术界称之为中国邮递员问题，因为它首先是由中国数学家管梅谷教授在1962 年首次提出并加以研究的。3.2.1 欧拉回路设G（V，E）为一个图，图G 中一个回路，若它恰通过G 中每条边一次,则称该回路为欧拉(Euler)回路，并称图G 为欧拉图。欧拉回路与哥尼斯堡7 桥问题相联系的，在哥尼斯堡7 桥问题中，欧拉证明了不存在这样的回路。在一个图中，连接一个节点的边数称为该节点的度数。对欧拉图，有下列结果：定理1 对连通图G（V，E），其中V 表示图中的节点集，E 表示边集，则下列条件是相互等价的：G 是一个欧拉图；G 的每一个节点的度数都是偶数；G 的边集合E 可以分解为若干个回路的并。证明： 已知G 为欧拉图，则必存在一个欧拉回路。回路中的节点都是偶度数。 设G 中每一个节点的度数均为偶数。若能找到一个回路C1 使G=C1，则结论成立。否则，令G1=GC1，由C1 上每个节点的度数均为偶数，则G1 中的每个节点的度数亦均为偶数。于是在G1 必存在另一个回路C2。令G2=G1C2，。由于G 为有限图，上述过程经过有限步，最后必得一个回路Cr使Gr=Gr-1Cr 上各节点的度数均为零，即Cr=Gr-1。这样就得到G 的一个分解G=C1C2Cr。 设G=C1C2Cr，其中Ci（i=1,2,r）均为回路。由于G 为连通图，对任意回路Ci,必存在另一个回路Cj与之相连，即Ci与Cj存在共同的节点。现在我们从图G 的任意节点出发，沿着所在的回路走，每走到一个共同的节点处，就转向另一个回路，这样一直走下去就可走遍G 的每条边且只走过一次,最后回到原出发节点，即G 为一个欧拉图。利用定理1 去判断一个连通图是否为欧拉图比较容易，但要找出欧拉回路，当连通图比较复杂时就不太容易了。下面介绍欧拉回路的求解。3.2.2 欧拉回路的求解循环的找到出发点。从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。求解欧拉回路的弗罗莱算法算法步骤如下：任取起始点v0,v0R；设路R=e1(v0,vi1),e2(vi1,vi2),er(vir-1,vir)已选出，则从E(e1,e2,er)中选出边er+1，使er+1与vir相连，除非没有其它选择，Grer+1仍应为连通的。重复步骤，直至不能进行下去为止。定理2 连通的有向图存在欧拉回路的充分必要条件是对任意节点，进入该节点边数（进数）与离开该点的边数（出数）相等。3.2.3 邮差问题求解用图论的述语，在一个连通的赋权图G（V，E）中，要寻找一条回路，使该回路包含G 中的每条边至少一次，且该回路的权数最小。也就是说要从包含G 的每条边的回路中找一条权数最小的回路。如果G 是欧拉图，若图中有欧拉回路，因为欧拉回路通过所有的边，因此任何一个欧拉回路即为此问题的解，则很容易由3.2.2节中描述弗罗莱算法求出一个欧拉回路求出一个欧拉回路，但是若G 不是欧拉图，即存在奇度数的节点，则中国由递员问题的解决要困难得多。有兴趣的读者可以参考文献。在现实生活中，很多问题都可以转化为中国邮递员问题，例如道路清扫时如何使开空车的总时间最少的问题等等。上面例题所用的求最优邮路的方法叫“奇偶点图上作业法”。4.计算机科学与组合数学随着计算机技术的深入发展，特别是计算机网络的广泛使用，计算机的使用已经深入到科学研究和人们日常生活的各个领域。计算机要向更加智能化的方向发展，其出路仍然是数学的算法和数学的机械化。算法研究是计算机科学的重要研究领域，组合数学家在20 世纪70 年代初建立的算法复杂性NP 理论为计算机算法复杂性的研究提供了重要的理论基础。组合数学是计算机产业的基础，开发高层次的软件产品离不开组合数学。组合数学在国外早已成为十分重要的学科，甚至可以说是计算机科学的基础，当今计算机科学界的权威人士很多都是研究组合数学出身的。美国和印度之所以能在软件行业处于世界领先的地位，与这两个国家在基础数学，特别是组合数学方面的人才储备分不开的，但在国内仍有一部人对组合数学的认识不够，认为组合数学只是一门纯粹的基础学科，对经济发展实际意义不大，可实际情况是软件产业、网络算法和分析、信息压缩、网络安全、编码技术、系统软件都离不开组合数学的理论和方法上的支持。以基础数学为代表的基础理论研究已成为我国软件业发展的瓶颈，中国要想能成为一个软件大国，就应加强组合数学教学和人才培养等工作。当前，有识之士也已充分认识到组合数学等基础数学的重要性，南开大学于1997 年成立了南开大学组合数学中心，主要从事组合数学理论研究，如今已经成为一个具有国际影响力的组合数学研究机构9，并创办了我国第一份组合数学国际刊物组合年刊。另外，清华大学、中国科技大学、同济大学等重点大学也建立了研究组合数学的重点实验室。总之，近几年来，我国的组合数学基础研究工作受到各高校及广大科学工作者越来越多的关注，特别是在高校学生间开展的数学建模竞赛活动，提高了学生用计算机技术解决实际问题的能力，也大大刺激了学生对组合数学的求知需求，激发了学习组合数学的热潮。5. 结论随着计算机的普及推广，组合数学这门古老的学科焕发出蓬勃的生机。组合数学是一门研究内容丰富、应用广泛的学科，同时它也是一门讲究方法，讲究技巧的学科。组合数学的魅力在于一个组合数学问题的能否得到完善的解决往往取决于能否找到巧妙的解法，计算机强大的计算能力为寻求组合数学问题的巧妙解法提供了无限的可能，同时组合数学也反过来有效地推动了计算机科学的发展。参考文献1 陈永川.话说组合数学J.科学中国人,2003(5).2 孙怡东.计数组合学中若干问题的研究D.大连理工大学,2006.3 邓明立.有限域思想的历史演变D.河北师范大学,2004.4 侯庆虎.组合数学中的